/*
**  VAR - OSSP variable expression library.
**  Copyright (c) 2001 The OSSP Project (http://www.ossp.org/)
**  Copyright (c) 2001 Cable & Wireless Deutschland (http://www.cw.com/de/)
**
**  This file is part of OSSP VAR, an extensible data serialization
**  library which can be found at http://www.ossp.org/pkg/var/.
**
**  Permission to use, copy, modify, and distribute this software for
**  any purpose with or without fee is hereby granted, provided that
**  the above copyright notice and this permission notice appear in all
**  copies.
**
**  THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED 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 AUTHORS AND COPYRIGHT HOLDERS AND THEIR
**  CONTRIBUTORS 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.
**
**  var.c: VAR library implementation.
*/

#include <ctype.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
#include <sys/types.h>
#if defined(HAVE_PCREPOSIX)
#  include <pcreposix.h>
#else
#  include <regex.h>
#endif
#include "var.h"

/* The default configuration for the parser. */

const var_config_t var_config_default = {
    '$',                        /* varinit */
    '{',                        /* startdelim */
    '}',                        /* enddelim */
    '\\',                       /* escape */
    "a-zA-Z0-9_"                /* namechars */
};

/* Routines for manipulation of token buffers. */

#define TOKENBUF_INITIAL_BUFSIZE 64

typedef struct {
    const char *begin;
    const char *end;
    size_t buffer_size;
} tokenbuf_t;

static void tokenbuf_init(tokenbuf_t *buf)
{
    buf->begin = NULL;
    buf->end = NULL;
    buf->buffer_size = 0;
    return;
}

static void tokenbuf_move(tokenbuf_t *src, tokenbuf_t *dst)
{
    dst->begin = src->begin;
    dst->end = src->end;
    dst->buffer_size = src->buffer_size;
    tokenbuf_init(src);
    return;
}

static int tokenbuf_assign(tokenbuf_t *buf, const char *data, size_t len)
{
    char *p;

    if ((p = malloc(len + 1)) == NULL)
        return 0;
    memcpy(p, data, len);
    buf->begin = p;
    buf->end = p + len;
    buf->buffer_size = len + 1;
    *((char *)(buf->end)) = '\0';
    return 1;
}

static int tokenbuf_append(tokenbuf_t *output, const char *data, size_t len)
{
    char *new_buffer;
    size_t new_size;
    char *tmp;

    /* Is the tokenbuffer initialized at all? If not, allocate a
       standard-sized buffer to begin with. */
    if (output->begin == NULL) {
        if ((output->begin = output->end = malloc(TOKENBUF_INITIAL_BUFSIZE)) == NULL)
            return 0;
        output->buffer_size = TOKENBUF_INITIAL_BUFSIZE;
    }

    /* Does the token contain text, but no buffer has been allocated yet? */
    if (output->buffer_size == 0) {
        /* Check whether data borders to output. If, we can append
           simly by increasing the end pointer. */
        if (output->end == data) {
            output->end += len;
            return 1;
        }
        /* OK, so copy the contents of output into an allocated buffer
           so that we can append that way. */
        if ((tmp = malloc(output->end - output->begin + len + 1)) == NULL)
            return 0;
        memcpy(tmp, output->begin, output->end - output->begin);
        output->buffer_size = output->end - output->begin;
        output->begin = tmp;
        output->end = tmp + output->buffer_size;
        output->buffer_size += len + 1;
    }

    /* Does the token fit into the current buffer? If not, realloc a
       larger buffer that fits. */
    if ((output->buffer_size - (output->end - output->begin)) <= len) {
        new_size = output->buffer_size;
        do {
            new_size *= 2;
        } while ((new_size - (output->end - output->begin)) <= len);
        if ((new_buffer = realloc((char *)output->begin, new_size)) == NULL)
            return 0;
        output->end = new_buffer + (output->end - output->begin);
        output->begin = new_buffer;
        output->buffer_size = new_size;
    }

    /* Append the data at the end of the current buffer. */
    memcpy((char *)output->end, data, len);
    output->end += len;
    *((char *)output->end) = '\0';
    return 1;
}

static void tokenbuf_free(tokenbuf_t *buf)
{
    if (buf->begin != NULL && buf->buffer_size > 0)
        free((char *)buf->begin);
    buf->begin = buf->end = NULL;
    buf->buffer_size = 0;
    return;
}

static size_t tokenbuf_toint(tokenbuf_t *number)
{
    const char *p;
    size_t num;

    num = 0;
    for (p = number->begin; p != number->end; ++p) {
        num *= 10;
        num += *p - '0';
    }
    return num;
}

/* Routines for the expansion of quoted-pair expressions. */

typedef char char_class_t[256]; /* 256 == 2 ^ sizeof(unsigned char)*8 */

static void expand_range(char a, char b, char_class_t class)
{
    do {
        class[(int)a] = 1;
    }
    while (++a <= b);
}

static var_rc_t expand_character_class(const char *desc, char_class_t class)
{
    size_t i;

    /* Clear the class array. */

    for (i = 0; i < 256; ++i)
        class[i] = 0;
        //FIXME THL: shouldn't we use a "libvar" context and do this and the consistency checks only once? This is like a delay-loop ...

    /* Walk through the class description and set the appropriate
       entries in the array. */

    while (*desc != '\0') {
        if (desc[1] == '-' && desc[2] != '\0') {
            if (desc[0] > desc[2])
                return VAR_ERR_INCORRECT_CLASS_SPEC;
            expand_range(desc[0], desc[2], class);
            desc += 3;
        } else {
            class[(int) *desc] = 1;
            ++desc;
        }
    }

    return VAR_OK;
}

static int isoct(char c)
{
    if (c >= '0' && c <= '7')
        return 1;
    else
        return 0;
}

static var_rc_t expand_octal(const char **src, char **dst, const char *end)
{
    unsigned char c;

    if (end - *src < 3)
        return VAR_ERR_INCOMPLETE_OCTAL;
    if (!isoct(**src) || !isoct((*src)[1]) || !isoct((*src)[2]))
        return VAR_ERR_INVALID_OCTAL;

    c = **src - '0';
    if (c > 3)
        return VAR_ERR_OCTAL_TOO_LARGE;
    c *= 8;
    ++(*src);

    c += **src - '0';
    c *= 8;
    ++(*src);

    c += **src - '0';

    **dst = (char) c;
    ++(*dst);
    return VAR_OK;
}

static int ishex(char c)
{
    if ((c >= '0' && c <= '9') ||
        (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F'))
        return 1;
    else
        return 0;
}

static var_rc_t expand_simple_hex(const char **src, char **dst,
                                  const char *end)
{
    unsigned char c = 0;

    if (end - *src < 2)
        return VAR_ERR_INCOMPLETE_HEX;
    if (!ishex(**src) || !ishex((*src)[1]))
        return VAR_ERR_INVALID_HEX;

    if (**src >= '0' && **src <= '9')
        c = **src - '0';
    else if (c >= 'a' && c <= 'f')
        c = **src - 'a' + 10;
    else if (c >= 'A' && c <= 'F')
        c = **src - 'A' + 10;

    c = c << 4;
    ++(*src);

    if (**src >= '0' && **src <= '9')
        c += **src - '0';
    else if (**src >= 'a' && **src <= 'f')
        c += **src - 'a' + 10;
    else if (**src >= 'A' && **src <= 'F')
        c += **src - 'A' + 10;

    **dst = (char) c;
    ++(*dst);
    return VAR_OK;
}

static var_rc_t expand_grouped_hex(const char **src, char **dst,
                                   const char *end)
{
    var_rc_t rc;

    while (*src < end && **src != '}') {
        if ((rc = expand_simple_hex(src, dst, end)) != VAR_OK)
            return rc;
        ++(*src);
    }
    if (*src == end)
        return VAR_ERR_INCOMPLETE_GROUPED_HEX;

    return VAR_OK;
}

static var_rc_t expand_hex(const char **src, char **dst, const char *end)
{
    if (*src == end)
        return VAR_ERR_INCOMPLETE_HEX;
    if (**src == '{') {
        ++(*src);
        return expand_grouped_hex(src, dst, end);
    } else
        return expand_simple_hex(src, dst, end);
}

var_rc_t var_unescape(const char *src, size_t len, char *dst,
                      int unescape_all)
{
    const char *end = src + len;
    var_rc_t rc;

    while (src < end) {
        if (*src == '\\') {
            if (++src == end)
                return VAR_ERR_INCOMPLETE_NAMED_CHARACTER;
            switch (*src) {
            case '\\':
                if (!unescape_all) {
                    *dst++ = '\\';
                }
                *dst++ = '\\';
                break;
            case 'n':
                *dst++ = '\n';
                break;
            case 't':
                *dst++ = '\t';
                break;
            case 'r':
                *dst++ = '\r';
                break;
            case 'x':
                ++src;
                if ((rc = expand_hex(&src, &dst, end)) != VAR_OK)
                    return rc;
                break;
            case '0':
            case '1':
            case '2':
            case '3':
            case '4':
            case '5':
            case '6':
            case '7':
            case '8':
            case '9':
                if (end - src >= 3 && isdigit((int)src[1]) && isdigit((int)src[2])) {
                    if ((rc = expand_octal(&src, &dst, end)) != 0)
                        return rc;
                    break;
                }
            default:
                if (!unescape_all) {
                    *dst++ = '\\';
                }
                *dst++ = *src;
            }
            ++src;
        } else
            *dst++ = *src++;
    }
    *dst = '\0';
    return VAR_OK;
}

/* The recursive-descent parser for variable expressions. */

static int variable(const char *, const char *, const var_config_t *,
                    const char_class_t, var_cb_t, void *, int, tokenbuf_t *);
static int command(const char *, const char *, const var_config_t *,
                   const char_class_t, var_cb_t, void *, int, tokenbuf_t *);

static int text(const char *begin, const char *end, char varinit,
                char escape)
{
    const char *p;
    for (p = begin; p != end && *p != varinit; ++p) {
        if (*p == escape) {
            if (p + 1 == end)
                return VAR_ERR_INCOMPLETE_QUOTED_PAIR;
            else
                ++p;
        }
    }
    return p - begin;
}

static int varname(const char *begin, const char *end,
                   const char_class_t nameclass)
{
    const char *p;
    for (p = begin; p != end && nameclass[(int) *p]; ++p);
    return p - begin;
}

static int number(const char *begin, const char *end)
{
    const char *p;
    for (p = begin; p != end && isdigit((int)*p); ++p);
    return p - begin;
}

static int substext(const char *begin, const char *end,
                    const var_config_t *config)
{
    const char *p;
    for (p = begin; p != end && *p != config->varinit && *p != '/'; ++p) {
        if (*p == config->escape) {
            if (p + 1 == end)
                return VAR_ERR_INCOMPLETE_QUOTED_PAIR;
            else
                ++p;
        }
    }
    return p - begin;
}

static int exptext(const char *begin, const char *end,
                   const var_config_t *config)
{
    const char *p;
    for (p = begin;
         p != end && *p != config->varinit && *p != config->enddelim
         && *p != ':'; ++p) {
        if (*p == config->escape) {
            if (p + 1 == end)
                return VAR_ERR_INCOMPLETE_QUOTED_PAIR;
            else
                ++p;
        }
    }
    return p - begin;
}


static int expression(const char *begin, const char *end,
                      const var_config_t *config,
                      const char_class_t nameclass, var_cb_t lookup,
                      void *lookup_context, int force_expand,
                      tokenbuf_t *result)
{
    const char *p = begin;
    const char *data;
    size_t len, buffer_size;
    int failed = 0;
    int rc;
    tokenbuf_t name;
    tokenbuf_t tmp;

    /* Clear the tokenbufs to make sure we have a defined state. */

    tokenbuf_init(&name);
    tokenbuf_init(&tmp);
    tokenbuf_init(result);

    /* Expect STARTDELIM. */

    if (p == end || *p != config->startdelim)
        return 0;

    if (++p == end)
        return VAR_ERR_INCOMPLETE_VARIABLE_SPEC;

    /* Get the name of the variable to expand. The name may consist of
       an arbitrary number of VARNAMEs and VARIABLEs. */

    do {
        rc = varname(p, end, nameclass);
        if (rc < 0)
            goto error_return;
        else if (rc > 0) {
            if (!tokenbuf_append(&name, p, rc)) {
                rc = VAR_ERR_OUT_OF_MEMORY;
                goto error_return;
            } else
                p += rc;
        }

        rc = variable(p, end, config, nameclass, lookup, lookup_context,
                      force_expand, &tmp);
        if (rc < 0)
            goto error_return;
        else if (rc > 0) {
            if (!tokenbuf_append(&name, tmp.begin, tmp.end - tmp.begin)) {
                rc = VAR_ERR_OUT_OF_MEMORY;
                goto error_return;
            } else
                p += rc;
        }
    }
    while (rc > 0);

    /* We must have the complete variable name now, so make sure we
       do. */

    if (name.begin == name.end) {
        rc = VAR_ERR_INCOMPLETE_VARIABLE_SPEC;
        goto error_return;
    }

    /* Now we have the name of the variable stored in "name". We
       expect an ENDDELIM here. */

    if (p == end || (*p != config->enddelim && *p != ':')) {
        rc = VAR_ERR_INCOMPLETE_VARIABLE_SPEC;
        goto error_return;
    } else
        ++p;

    /* Use the lookup callback to get the variable's contents. */

    rc = (*lookup) (lookup_context, name.begin, name.end - name.begin,
                    &data, &len, &buffer_size);
    if (rc < 0)
        goto error_return;
    else if (rc == 0) {
        /* The variable is undefined. What we'll do now depends on the
           force_expand flag. */

        if (force_expand) {
            rc = VAR_ERR_UNDEFINED_VARIABLE;
            goto error_return;
        } else {
            /* Initialize result to point back to the original text in
               the buffer. */

            result->begin = begin - 1;
            result->end = p;
            result->buffer_size = 0;
            failed = 1;
        }
    } else {
        /* The preliminary result is the contents of the variable.
           This may be modified by the commands that may follow. */

        result->begin = data;
        result->end = data + len;
        result->buffer_size = buffer_size;
    }

    if (p[-1] == ':') {
        /* Parse and execute commands. */

        tokenbuf_free(&tmp);
        --p;
        while (p != end && *p == ':') {
            ++p;
            if (!failed)
                rc = command(p, end, config, nameclass, lookup,
                             lookup_context, force_expand, result);
            else
                rc = command(p, end, config, nameclass, lookup,
                             lookup_context, force_expand, &tmp);
            if (rc < 0)
                goto error_return;
            p += rc;
            if (failed)
                result->end += rc;
        }

        if (p == end || *p != config->enddelim) {
            rc = VAR_ERR_INCOMPLETE_VARIABLE_SPEC;
            goto error_return;
        }
        ++p;
        if (failed)
            ++result->end;
    }

    /* Exit gracefully. */

    tokenbuf_free(&name);
    tokenbuf_free(&tmp);
    return p - begin;

    /* Exit in case of an error. */

  error_return:
    tokenbuf_free(&name);
    tokenbuf_free(&tmp);
    tokenbuf_free(result);
    return rc;
}

static int variable(const char *begin, const char *end,
                    const var_config_t *config, const char_class_t nameclass,
                    var_cb_t lookup, void *lookup_context,
                    int force_expand, tokenbuf_t *result)
{
    const char *p = begin;
    const char *data;
    size_t len, buffer_size;
    int rc, rc2;

    /* Clear the result tokenbuf to make sure we're in a defined
       state. */

    tokenbuf_init(result);

    /* Expect VARINIT. */

    if (p == end || *p != config->varinit)
        return 0;

    if (++p == end)
        return VAR_ERR_INCOMPLETE_VARIABLE_SPEC;

    /* Try to read the variable name. If that fails, we're parsing a
       complex expression. */

    rc = varname(p, end, nameclass);
    if (rc < 0)
        return rc;
    if (rc > 0) {
        rc2 = (*lookup) (lookup_context, p, rc, &data, &len, &buffer_size);
        if (rc2 < 0)
            return rc2;
        if (rc2 == 0) {
            if (force_expand)
                return VAR_ERR_UNDEFINED_VARIABLE;
            result->begin = begin;
            result->end = begin + 1 + rc;
            result->buffer_size = 0;
            return 1 + rc;
        }
        result->begin = data;
        result->end = data + len;
        result->buffer_size = buffer_size;
        return 1 + rc;
    }

    /* OK, we're dealing with a complex expression here. */

    rc = expression(p, end, config, nameclass, lookup, lookup_context,
                    force_expand, result);
    if (rc > 0)
        ++rc;
    return rc;
}

static int exptext_or_variable(const char *begin, const char *end,
                               const var_config_t *config,
                               const char_class_t nameclass, var_cb_t lookup,
                               void *lookup_context, int force_expand,
                               tokenbuf_t *result)
{
    const char *p = begin;
    tokenbuf_t tmp;
    int rc;

    tokenbuf_init(result);
    tokenbuf_init(&tmp);

    if (begin == end)
        return 0;

    do {
        rc = exptext(p, end, config);
        if (rc < 0)
            goto error_return;
        else if (rc > 0) {
            if (!tokenbuf_append(result, p, rc)) {
                rc = VAR_ERR_OUT_OF_MEMORY;
                goto error_return;
            } else
                p += rc;
        }

        rc = variable(p, end, config, nameclass, lookup, lookup_context,
                      force_expand, &tmp);
        if (rc < 0)
            goto error_return;
        else if (rc > 0) {
            p += rc;
            if (!tokenbuf_append
                (result, tmp.begin, tmp.end - tmp.begin)) {
                rc = VAR_ERR_OUT_OF_MEMORY;
                goto error_return;
            }
        }
    }
    while (rc > 0);

    tokenbuf_free(&tmp);
    return p - begin;

  error_return:
    tokenbuf_free(&tmp);
    tokenbuf_free(result);
    return rc;
}

static int substext_or_variable(const char *begin, const char *end,
                                const var_config_t *config,
                                const char_class_t nameclass, var_cb_t lookup,
                                void *lookup_context, int force_expand,
                                tokenbuf_t *result)
{
    const char *p = begin;
    tokenbuf_t tmp;
    int rc;

    tokenbuf_init(result);
    tokenbuf_init(&tmp);

    if (begin == end)
        return 0;

    do {
        rc = substext(p, end, config);
        if (rc < 0)
            goto error_return;
        else if (rc > 0) {
            if (!tokenbuf_append(result, p, rc)) {
                rc = VAR_ERR_OUT_OF_MEMORY;
                goto error_return;
            } else
                p += rc;
        }

        rc = variable(p, end, config, nameclass, lookup, lookup_context,
                      force_expand, &tmp);
        if (rc < 0)
            goto error_return;
        else if (rc > 0) {
            p += rc;
            if (!tokenbuf_append
                (result, tmp.begin, tmp.end - tmp.begin)) {
                rc = VAR_ERR_OUT_OF_MEMORY;
                goto error_return;
            }
        }
    }
    while (rc > 0);

    tokenbuf_free(&tmp);
    return p - begin;

  error_return:
    tokenbuf_free(&tmp);
    tokenbuf_free(result);
    return rc;
}


static int expand_class_description(tokenbuf_t *src, tokenbuf_t *dst)
{
    unsigned char c, d;
    const char *p = src->begin;
    while (p != src->end) {
        if ((src->end - p) >= 3 && p[1] == '-') {
            if (*p > p[2])
                return VAR_ERR_INCORRECT_TRANSPOSE_CLASS_SPEC;
            for (c = *p, d = p[2]; c <= d; ++c) {
                if (!tokenbuf_append(dst, (char *) &c, 1))
                    return VAR_ERR_OUT_OF_MEMORY;
            }
            p += 3;
        } else {
            if (!tokenbuf_append(dst, p, 1))
                return VAR_ERR_OUT_OF_MEMORY;
            else
                ++p;
        }
    }
    return VAR_OK;
}

static int transpose(tokenbuf_t *data, tokenbuf_t *search,
                     tokenbuf_t *replace)
{
    tokenbuf_t srcclass, dstclass;
    const char *p;
    int rc;
    size_t i;

    tokenbuf_init(&srcclass);
    tokenbuf_init(&dstclass);

    if ((rc = expand_class_description(search, &srcclass)) != VAR_OK)
        goto error_return;
    if ((rc = expand_class_description(replace, &dstclass)) != VAR_OK)
        goto error_return;

    if (srcclass.begin == srcclass.end) {
        rc = VAR_ERR_EMPTY_TRANSPOSE_CLASS;
        goto error_return;
    }
    if ((srcclass.end - srcclass.begin) != (dstclass.end - dstclass.begin)) {
        rc = VAR_ERR_TRANSPOSE_CLASSES_MISMATCH;
        goto error_return;
    }

    if (data->buffer_size == 0) {
        tokenbuf_t tmp;
        if (!tokenbuf_assign
            (&tmp, data->begin, data->end - data->begin)) {
            rc = VAR_ERR_OUT_OF_MEMORY;
            goto error_return;
        }
        tokenbuf_move(&tmp, data);
    }

    for (p = data->begin; p != data->end; ++p) {
        for (i = 0; i <= (srcclass.end - srcclass.begin); ++i) {
            if (*p == srcclass.begin[i]) {
                *((char *) p) = dstclass.begin[i];
                break;
            }
        }
    }

    tokenbuf_free(&srcclass);
    tokenbuf_free(&dstclass);
    return VAR_OK;

  error_return:
    tokenbuf_free(search);
    tokenbuf_free(replace);
    tokenbuf_free(&srcclass);
    tokenbuf_free(&dstclass);
    return rc;
}

static int cut_out_offset(tokenbuf_t *data, tokenbuf_t *number1,
                          tokenbuf_t *number2, int isrange)
{
    tokenbuf_t res;
    const char *p;
    size_t num1 = tokenbuf_toint(number1);
    size_t num2 = tokenbuf_toint(number2);

    /* Determine begin of result string. */

    if ((data->end - data->begin) < num1)
        return VAR_ERR_OFFSET_OUT_OF_BOUNDS;
    else
        p = data->begin + num1;

    /* If num2 is zero, we copy the rest from there. */

    if (num2 == 0) {
        if (!tokenbuf_assign(&res, p, data->end - p))
            return VAR_ERR_OUT_OF_MEMORY;
    } else {                    /* OK, then use num2. */

        if (isrange) {
            if ((p + num2) > data->end)
                return VAR_ERR_RANGE_OUT_OF_BOUNDS;
            if (!tokenbuf_assign(&res, p, num2))
                return VAR_ERR_OUT_OF_MEMORY;
        } else {
            if (num2 < num1)
                return VAR_ERR_OFFSET_LOGIC;
            if ((data->begin + num2) > data->end)
                return VAR_ERR_RANGE_OUT_OF_BOUNDS;
            if (!tokenbuf_assign(&res, p, (data->begin + num2) - p))
                return VAR_ERR_OUT_OF_MEMORY;
        }
    }
    tokenbuf_free(data);
    tokenbuf_move(&res, data);
    return VAR_OK;
}

static int expand_regex_replace(const char *data, tokenbuf_t *orig,
                                regmatch_t *pmatch, tokenbuf_t *expanded)
{
    const char *p = orig->begin;
    size_t i;

    tokenbuf_init(expanded);

    while (p != orig->end) {
        if (*p == '\\') {
            if (orig->end - p <= 1) {
                tokenbuf_free(expanded);
                return VAR_ERR_INCOMPLETE_QUOTED_PAIR;
            } else
                ++p;
            if (*p == '\\') {
                if (!tokenbuf_append(expanded, p, 1)) {
                    tokenbuf_free(expanded);
                    return VAR_ERR_OUT_OF_MEMORY;
                }
                ++p;
                continue;
            }
            if (!isdigit((int)*p)) {
                tokenbuf_free(expanded);
                return VAR_ERR_UNKNOWN_QUOTED_PAIR_IN_REPLACE;
            }
            i = *p - '0';
            ++p;
            if (pmatch[i].rm_so == -1) {
                tokenbuf_free(expanded);
                return VAR_ERR_SUBMATCH_OUT_OF_RANGE;
            }
            if (!tokenbuf_append(expanded, data + pmatch[i].rm_so,
                                    pmatch[i].rm_eo - pmatch[i].rm_so)) {
                tokenbuf_free(expanded);
                return VAR_ERR_OUT_OF_MEMORY;
            }
        } else {
            if (!tokenbuf_append(expanded, p, 1)) {
                tokenbuf_free(expanded);
                return VAR_ERR_OUT_OF_MEMORY;
            }
            ++p;
        }
    }

    return VAR_OK;
}

static int search_and_replace(tokenbuf_t *data, tokenbuf_t *search,
                              tokenbuf_t *replace, tokenbuf_t *flags)
{
    const char *p;
    int case_insensitive = 0;
    int global = 0;
    int no_regex = 0;
    int rc;

    if (search->begin == search->end)
        return VAR_ERR_EMPTY_SEARCH_STRING;

    for (p = flags->begin; p != flags->end; ++p) {
        switch (tolower(*p)) {
        case 'i':
            case_insensitive = 1;
            break;
        case 'g':
            global = 1;
            break;
        case 't':
            no_regex = 1;
            break;
        default:
            return VAR_ERR_UNKNOWN_REPLACE_FLAG;
        }
    }

    if (no_regex) {
        tokenbuf_t tmp;
        tokenbuf_init(&tmp);

        for (p = data->begin; p != data->end;) {
            if (case_insensitive)
                rc = strncasecmp(p, search->begin,
                                 search->end - search->begin);
            else
                rc = strncmp(p, search->begin,
                             search->end - search->begin);
            if (rc != 0) {      /* no match, copy character */
                if (!tokenbuf_append(&tmp, p, 1)) {
                    tokenbuf_free(&tmp);
                    return VAR_ERR_OUT_OF_MEMORY;
                }
                ++p;
            } else {
                tokenbuf_append(&tmp, replace->begin,
                                   replace->end - replace->begin);
                p += search->end - search->begin;
                if (!global) {
                    if (!tokenbuf_append(&tmp, p, data->end - p)) {
                        tokenbuf_free(&tmp);
                        return VAR_ERR_OUT_OF_MEMORY;
                    }
                    break;
                }
            }
        }

        tokenbuf_free(data);
        tokenbuf_move(&tmp, data);
    } else {
        tokenbuf_t tmp;
        tokenbuf_t mydata;
        tokenbuf_t myreplace;
        regex_t preg;
        regmatch_t pmatch[10];
        int regexec_flag;

        /* Copy the pattern and the data to our own buffer to make
           sure they're terminated with a null byte. */

        if (!tokenbuf_assign
            (&tmp, search->begin, search->end - search->begin))
            return VAR_ERR_OUT_OF_MEMORY;
        if (!tokenbuf_assign
            (&mydata, data->begin, data->end - data->begin)) {
            tokenbuf_free(&tmp);
            return VAR_ERR_OUT_OF_MEMORY;
        }

        /* Compile the pattern. */

        rc = regcomp(&preg, tmp.begin,
                     REG_EXTENDED | ((case_insensitive) ? REG_ICASE : 0));
        tokenbuf_free(&tmp);
        if (rc != 0) {
            tokenbuf_free(&mydata);
            return VAR_ERR_INVALID_REGEX_IN_REPLACE;
        }

        /* Match the pattern and create the result string in the tmp
           buffer. */

        for (p = mydata.begin; p != mydata.end;) {
            if (p == mydata.begin || p[-1] == '\n')
                regexec_flag = 0;
            else
                regexec_flag = REG_NOTBOL;
            if (regexec
                (&preg, p, sizeof(pmatch) / sizeof(regmatch_t), pmatch,
                 regexec_flag) == REG_NOMATCH) {
                tokenbuf_append(&tmp, p, mydata.end - p);
                break;
            } else {
                rc = expand_regex_replace(p, replace, pmatch, &myreplace);
                if (rc != VAR_OK) {
                    regfree(&preg);
                    tokenbuf_free(&tmp);
                    tokenbuf_free(&mydata);
                    return rc;
                }
                if (!tokenbuf_append(&tmp, p, pmatch[0].rm_so) ||
                    !tokenbuf_append(&tmp, myreplace.begin,
                                        myreplace.end - myreplace.begin)) {
                    regfree(&preg);
                    tokenbuf_free(&tmp);
                    tokenbuf_free(&mydata);
                    tokenbuf_free(&myreplace);
                    return VAR_ERR_OUT_OF_MEMORY;
                } else {
                    p += (pmatch[0].rm_eo > 0) ? pmatch[0].rm_eo : 1;
                    tokenbuf_free(&myreplace);
                }
                if (!global) {
                    tokenbuf_append(&tmp, p, mydata.end - p);
                    break;
                }
            }
        }

        regfree(&preg);
        tokenbuf_free(data);
        tokenbuf_move(&tmp, data);
        tokenbuf_free(&mydata);
    }

    return VAR_OK;
}

static int padding(tokenbuf_t *data, tokenbuf_t *widthstr, tokenbuf_t *fill,
                   char position)
{
    tokenbuf_t result;
    size_t width = tokenbuf_toint(widthstr);
    int i;

    if (fill->begin == fill->end)
        return VAR_ERR_EMPTY_PADDING_FILL_STRING;

    tokenbuf_init(&result);

    if (position == 'l') {
        i = width - (data->end - data->begin);
        if (i > 0) {
            i = i / (fill->end - fill->begin);
            while (i > 0) {
                if (!tokenbuf_append
                    (data, fill->begin, fill->end - fill->begin))
                    return VAR_ERR_OUT_OF_MEMORY;
                --i;
            }
            i = (width - (data->end - data->begin)) % (fill->end -
                                                       fill->begin);
            if (!tokenbuf_append(data, fill->begin, i))
                return VAR_ERR_OUT_OF_MEMORY;
        }
    } else if (position == 'r') {
        i = width - (data->end - data->begin);
        if (i > 0) {
            i = i / (fill->end - fill->begin);
            while (i > 0) {
                if (!tokenbuf_append
                    (&result, fill->begin, fill->end - fill->begin)) {
                    tokenbuf_free(&result);
                    return VAR_ERR_OUT_OF_MEMORY;
                }
                --i;
            }
            i = (width - (data->end - data->begin)) % (fill->end -
                                                       fill->begin);
            if (!tokenbuf_append(&result, fill->begin, i)) {
                tokenbuf_free(&result);
                return VAR_ERR_OUT_OF_MEMORY;
            }
            if (!tokenbuf_append
                (&result, data->begin, data->end - data->begin)) {
                tokenbuf_free(&result);
                return VAR_ERR_OUT_OF_MEMORY;
            }

            tokenbuf_free(data);
            tokenbuf_move(&result, data);
        }
    } else if (position == 'c') {
        i = (width - (data->end - data->begin)) / 2;
        if (i > 0) {
            /* Create the prefix. */

            i = i / (fill->end - fill->begin);
            while (i > 0) {
                if (!tokenbuf_append
                    (&result, fill->begin, fill->end - fill->begin)) {
                    tokenbuf_free(&result);
                    return VAR_ERR_OUT_OF_MEMORY;
                }
                --i;
            }
            i = ((width - (data->end - data->begin)) / 2) % (fill->end -
                                                             fill->begin);
            if (!tokenbuf_append(&result, fill->begin, i)) {
                tokenbuf_free(&result);
                return VAR_ERR_OUT_OF_MEMORY;
            }

            /* Append the actual data string. */

            if (!tokenbuf_append
                (&result, data->begin, data->end - data->begin)) {
                tokenbuf_free(&result);
                return VAR_ERR_OUT_OF_MEMORY;
            }

            /* Append the suffix. */

            i = width - (result.end - result.begin);
            i = i / (fill->end - fill->begin);
            while (i > 0) {
                if (!tokenbuf_append
                    (&result, fill->begin, fill->end - fill->begin)) {
                    tokenbuf_free(&result);
                    return VAR_ERR_OUT_OF_MEMORY;
                }
                --i;
            }
            i = width - (result.end - result.begin);
            if (!tokenbuf_append(&result, fill->begin, i)) {
                tokenbuf_free(&result);
                return VAR_ERR_OUT_OF_MEMORY;
            }

            /* Move string from temporary buffer to data buffer. */

            tokenbuf_free(data);
            tokenbuf_move(&result, data);
        }
    }

    return VAR_OK;
}

static int command(const char *begin, const char *end,
                   const var_config_t *config, const char_class_t nameclass,
                   var_cb_t lookup, void *lookup_context, int force_expand,
                   tokenbuf_t *data)
{
    const char *p = begin;
    tokenbuf_t tmptokbuf;
    tokenbuf_t search, replace, flags;
    tokenbuf_t number1, number2;
    int isrange;
    int rc;

    tokenbuf_init(&tmptokbuf);
    tokenbuf_init(&search);
    tokenbuf_init(&replace);
    tokenbuf_init(&flags);
    tokenbuf_init(&number1);
    tokenbuf_init(&number2);

    if (begin == end)
        return 0;

    switch (tolower(*p)) {
    case 'l':                   /* Turn data to lowercase. */
        if (data->begin) {
            char *ptr;
            /* If the buffer does not life in an allocated buffer,
               we have to copy it before modifying the contents. */

            if (data->buffer_size == 0) {
                if (!tokenbuf_assign
                    (data, data->begin, data->end - data->begin)) {
                    rc = VAR_ERR_OUT_OF_MEMORY;
                    goto error_return;
                }
            }
            for (ptr = (char *) data->begin; ptr != data->end; ++ptr)
                *ptr = tolower(*ptr);
        }
        ++p;
        break;

    case 'u':                   /* Turn data to uppercase. */
        if (data->begin) {
            char *ptr;
            if (data->buffer_size == 0) {
                if (!tokenbuf_assign
                    (data, data->begin, data->end - data->begin)) {
                    rc = VAR_ERR_OUT_OF_MEMORY;
                    goto error_return;
                }
            }
            for (ptr = (char *) data->begin; ptr != data->end; ++ptr)
                *ptr = toupper(*ptr);
        }
        ++p;
        break;

    case 'o':                   /* Cut out substrings. */
        ++p;
        rc = number(p, end);
        if (rc == 0) {
            rc = VAR_ERR_MISSING_START_OFFSET;
            goto error_return;
        } else {
            number1.begin = p;
            number1.end = p + rc;
            number1.buffer_size = 0;
            p += rc;
        }

        if (*p == ',') {
            isrange = 0;
            ++p;
        } else if (*p == '-') {
            isrange = 1;
            ++p;
        } else {
            rc = VAR_ERR_INVALID_OFFSET_DELIMITER;
            goto error_return;
        }

        rc = number(p, end);
        number2.begin = p;
        number2.end = p + rc;
        number2.buffer_size = 0;
        p += rc;
        if (data->begin) {
            rc = cut_out_offset(data, &number1, &number2, isrange);
            if (rc < 0)
                goto error_return;
        }
        break;

    case '#':                   /* Substitute length of the string. */
        if (data->begin) {
            char buf[1024];
            sprintf(buf, "%d", data->end - data->begin);
            tokenbuf_free(data);
            if (!tokenbuf_assign(data, buf, strlen(buf))) {
                rc = VAR_ERR_OUT_OF_MEMORY;
                goto error_return;
            }
        }
        ++p;
        break;

    case '-':                   /* Substitute parameter if data is empty. */
        ++p;
        rc = exptext_or_variable(p, end, config, nameclass, lookup,
                                 lookup_context, force_expand, &tmptokbuf);
        if (rc < 0)
            goto error_return;
        else if (rc == 0) {
            rc = VAR_ERR_MISSING_PARAMETER_IN_COMMAND;
            goto error_return;
        } else
            p += rc;
        if (data->begin != NULL && data->begin == data->end) {
            tokenbuf_free(data);
            tokenbuf_move(&tmptokbuf, data);
        }
        break;

    case '*':                   /* Return "" if data is not empty, parameter otherwise. */
        ++p;
        rc = exptext_or_variable(p, end, config, nameclass, lookup,
                                 lookup_context, force_expand, &tmptokbuf);
        if (rc < 0)
            goto error_return;
        else if (rc == 0) {
            rc = VAR_ERR_MISSING_PARAMETER_IN_COMMAND;
            goto error_return;
        } else
            p += rc;
        if (data->begin != NULL) {
            if (data->begin == data->end) {
                tokenbuf_free(data);
                tokenbuf_move(&tmptokbuf, data);
            } else {
                tokenbuf_free(data);
                data->begin = data->end = "";
                data->buffer_size = 0;
            }
        }
        break;

    case '+':                   /* Substitute parameter if data is not empty. */
        ++p;
        rc = exptext_or_variable(p, end, config, nameclass, lookup,
                                 lookup_context, force_expand, &tmptokbuf);
        if (rc < 0)
            goto error_return;
        else if (rc == 0) {
            rc = VAR_ERR_MISSING_PARAMETER_IN_COMMAND;
            goto error_return;
        } else
            p += rc;
        if (data->begin != NULL) {
            if (data->begin != data->end) {
                tokenbuf_free(data);
                tokenbuf_move(&tmptokbuf, data);
            }
        }
        break;

    case 's':                   /* Search and replace. */
        ++p;

        if (*p != '/')
            return VAR_ERR_MALFORMATTED_REPLACE;
        else
            ++p;

        rc = substext_or_variable(p, end, config, nameclass, lookup,
                                  lookup_context, force_expand, &search);
        if (rc < 0)
            goto error_return;
        else
            p += rc;

        if (*p != '/') {
            rc = VAR_ERR_MALFORMATTED_REPLACE;
            goto error_return;
        } else
            ++p;

        rc = substext_or_variable(p, end, config, nameclass, lookup,
                                  lookup_context, force_expand, &replace);
        if (rc < 0)
            goto error_return;
        else
            p += rc;

        if (*p != '/') {
            rc = VAR_ERR_MALFORMATTED_REPLACE;
            goto error_return;
        } else
            ++p;

        rc = exptext(p, end, config);
        if (rc < 0)
            goto error_return;
        else {
            flags.begin = p;
            flags.end = p + rc;
            flags.buffer_size = 0;
            p += rc;
        }

        if (data->begin) {
            rc = search_and_replace(data, &search, &replace, &flags);
            if (rc < 0)
                goto error_return;
        }
        break;

    case 'y':                   /* Transpose characters from class A to class B. */
        ++p;

        if (*p != '/')
            return VAR_ERR_MALFORMATTED_TRANSPOSE;
        else
            ++p;

        rc = substext_or_variable(p, end, config, nameclass, lookup,
                                  lookup_context, force_expand, &search);
        if (rc < 0)
            goto error_return;
        else
            p += rc;

        if (*p != '/') {
            rc = VAR_ERR_MALFORMATTED_TRANSPOSE;
            goto error_return;
        } else
            ++p;

        rc = substext_or_variable(p, end, config, nameclass, lookup,
                                  lookup_context, force_expand, &replace);
        if (rc < 0)
            goto error_return;
        else
            p += rc;

        if (*p != '/') {
            rc = VAR_ERR_MALFORMATTED_TRANSPOSE;
            goto error_return;
        } else
            ++p;

        if (data->begin) {
            rc = transpose(data, &search, &replace);
            if (rc < 0)
                goto error_return;
        }
        break;


    case 'p':                   /* Padding. */
        ++p;

        if (*p != '/')
            return VAR_ERR_MALFORMATTED_PADDING;
        else
            ++p;

        rc = number(p, end);
        if (rc == 0) {
            rc = VAR_ERR_MISSING_PADDING_WIDTH;
            goto error_return;
        } else {
            number1.begin = p;
            number1.end = p + rc;
            number1.buffer_size = 0;
            p += rc;
        }

        if (*p != '/') {
            rc = VAR_ERR_MALFORMATTED_PADDING;
            goto error_return;
        } else
            ++p;

        rc = substext_or_variable(p, end, config, nameclass, lookup,
                                  lookup_context, force_expand, &replace);
        if (rc < 0)
            goto error_return;
        else
            p += rc;

        if (*p != '/') {
            rc = VAR_ERR_MALFORMATTED_PADDING;
            goto error_return;
        } else
            ++p;

        if (*p != 'l' && *p != 'c' && *p != 'r') {
            rc = VAR_ERR_MALFORMATTED_PADDING;
            goto error_return;
        } else
            ++p;

        if (data->begin) {
            rc = padding(data, &number1, &replace, p[-1]);
            if (rc < 0)
                goto error_return;
        }
        break;

    default:
        return VAR_ERR_UNKNOWN_COMMAND_CHAR;
    }

    /* Exit gracefully. */

    tokenbuf_free(&tmptokbuf);
    tokenbuf_free(&search);
    tokenbuf_free(&replace);
    tokenbuf_free(&flags);
    tokenbuf_free(&number1);
    tokenbuf_free(&number2);
    return p - begin;

  error_return:
    tokenbuf_free(data);
    tokenbuf_free(&tmptokbuf);
    tokenbuf_free(&search);
    tokenbuf_free(&replace);
    tokenbuf_free(&flags);
    tokenbuf_free(&number1);
    tokenbuf_free(&number2);
    return rc;
}

static var_rc_t input(const char *begin, const char *end,
                      const var_config_t *config,
                      const char_class_t nameclass, var_cb_t lookup,
                      void *lookup_context, int force_expand,
                      tokenbuf_t *output)
{
    const char* p = begin;
    int rc;
    tokenbuf_t result;

    tokenbuf_init(&result);

    do {
        rc = text(begin, end, config->varinit, config->escape);
        if (rc > 0) {
            if (!tokenbuf_append(output, begin, rc)) {
                rc = VAR_ERR_OUT_OF_MEMORY;
                goto error_return;
            }
            begin += rc;
        } else if (rc < 0)
            goto error_return;

        rc = variable(begin, end, config, nameclass, lookup,
                      lookup_context, force_expand, &result);
        if (rc > 0) {
            if (!tokenbuf_append
                (output, result.begin, result.end - result.begin)) {
                rc = VAR_ERR_OUT_OF_MEMORY;
                goto error_return;
            }
            begin += rc;
        }
        if (rc < 0)
            goto error_return;
    }
    while (rc > 0);

    if (begin != end) {
        rc = VAR_ERR_INPUT_ISNT_TEXT_NOR_VARIABLE;
        goto error_return;
    }

    return VAR_OK;

  error_return:
    tokenbuf_free(output);
    tokenbuf_free(&result);
    output->begin = p;
    output->end = begin;
    output->buffer_size = 0;
    return rc;
}

var_rc_t var_expand(const char *input_buf, size_t input_len,
                    char **result, size_t *result_len,
                    var_cb_t lookup, void *lookup_context,
                    const var_config_t *config, int force_expand)
{
    char_class_t nameclass;
    var_rc_t rc;
    tokenbuf_t output;

    /* Argument sanity checks */
    if (input_buf == NULL || input_len == 0 ||
        result == NULL || result_len == NULL ||
        lookup == NULL)
        return VAR_ERR_INVALID_ARGUMENT;

    /* Optionally use default configuration */
    if (config == NULL)
        config = &var_config_default;

    /* Set the result pointer to the begining of the input buffer so
       that it is correctly initialized in case we fail with an error. */
    *result = (char *)input_buf;

    /* Expand the class description for valid variable names. */
    if ((rc = expand_character_class(config->namechars, nameclass)) != VAR_OK)
        return rc;

    /* Make sure that the specials defined in the configuration do not
       appear in the character name class. */
    if (nameclass[(int)config->varinit] ||
        nameclass[(int)config->startdelim] ||
        nameclass[(int)config->enddelim] ||
//FIXME THL: if(config->varinit == ':' ...any must not be colon > ERROR, varname() will fail
        nameclass[(int)config->escape])
        return VAR_ERR_INVALID_CONFIGURATION;

//FIXME THL: if(config->varinit == config->startdelimit || ...any with any...

    /* Call the parser. */
    tokenbuf_init(&output);
    rc = input(input_buf, input_buf + input_len, config, nameclass,
               lookup, lookup_context, force_expand, &output);
    *result = (char *)output.begin;
    *result_len = output.end - output.begin;
    return rc;
}