/*

    string_format.h -- implementation of string.format().

    It uses the Objects/stringlib conventions, so that it can be

    compiled for both unicode and string objects.

*/

/* Defines for Python 2.6 compatability */

#if PY_VERSION_HEX < 0x03000000

#define PyLong_FromSsize_t _PyLong_FromSsize_t

#endif

/* Defines for more efficiently reallocating the string buffer */

#define INITIAL_SIZE_INCREMENT 100

#define SIZE_MULTIPLIER 2

#define MAX_SIZE_INCREMENT  3200

/************************************************************************/

/***********   Global data structures and forward declarations  *********/

/************************************************************************/

/*

   A SubString consists of the characters between two string or

   unicode pointers.

*/

typedef struct {

    STRINGLIB_CHAR *ptr;

    STRINGLIB_CHAR *end;

} SubString;

/* forward declaration for recursion */

static PyObject *

build_string(SubString *input, PyObject *args, PyObject *kwargs,

             int recursion_depth);

/************************************************************************/

/**************************  Utility  functions  ************************/

/************************************************************************/

/* fill in a SubString from a pointer and length */

Py_LOCAL_INLINE(void)

SubString_init(SubString *str, STRINGLIB_CHAR *p, Py_ssize_t len)

{

    str->ptr = p;

    if (p == NULL)

        str->end = NULL;

    else

        str->end = str->ptr + len;

}

/* return a new string.  if str->ptr is NULL, return None */

Py_LOCAL_INLINE(PyObject *)

SubString_new_object(SubString *str)

{

    if (str->ptr == NULL) {

        Py_INCREF(Py_None);

        return Py_None;

    }

    return STRINGLIB_NEW(str->ptr, str->end - str->ptr);

}

/* return a new string.  if str->ptr is NULL, return None */

Py_LOCAL_INLINE(PyObject *)

SubString_new_object_or_empty(SubString *str)

{

    if (str->ptr == NULL) {

        return STRINGLIB_NEW(NULL, 0);

    }

    return STRINGLIB_NEW(str->ptr, str->end - str->ptr);

}

/************************************************************************/

/***********    Output string management functions       ****************/

/************************************************************************/

typedef struct {

    STRINGLIB_CHAR *ptr;

    STRINGLIB_CHAR *end;

    PyObject *obj;

    Py_ssize_t size_increment;

} OutputString;

/* initialize an OutputString object, reserving size characters */

static int

output_initialize(OutputString *output, Py_ssize_t size)

{

    output->obj = STRINGLIB_NEW(NULL, size);

    if (output->obj == NULL)

        return 0;

    output->ptr = STRINGLIB_STR(output->obj);

    output->end = STRINGLIB_LEN(output->obj) + output->ptr;

    output->size_increment = INITIAL_SIZE_INCREMENT;

    return 1;

}

/*

    output_extend reallocates the output string buffer.

    It returns a status:  0 for a failed reallocation,

    1 for success.

*/

static int

output_extend(OutputString *output, Py_ssize_t count)

{

    STRINGLIB_CHAR *startptr = STRINGLIB_STR(output->obj);

    Py_ssize_t curlen = output->ptr - startptr;

    Py_ssize_t maxlen = curlen + count + output->size_increment;

    if (STRINGLIB_RESIZE(&output->obj, maxlen) < 0)

        return 0;

    startptr = STRINGLIB_STR(output->obj);

    output->ptr = startptr + curlen;

    output->end = startptr + maxlen;

    if (output->size_increment < MAX_SIZE_INCREMENT)

        output->size_increment *= SIZE_MULTIPLIER;

    return 1;

}

/*

    output_data dumps characters into our output string

    buffer.

    In some cases, it has to reallocate the string.

    It returns a status:  0 for a failed reallocation,

    1 for success.

*/

static int

output_data(OutputString *output, const STRINGLIB_CHAR *s, Py_ssize_t count)

{

    if ((count > output->end - output->ptr) && !output_extend(output, count))

        return 0;

    memcpy(output->ptr, s, count * sizeof(STRINGLIB_CHAR));

    output->ptr += count;

    return 1;

}

/************************************************************************/

/***********  Format string parsing -- integers and identifiers *********/

/************************************************************************/

static Py_ssize_t

get_integer(const SubString *str)

{

    Py_ssize_t accumulator = 0;

    Py_ssize_t digitval;

    Py_ssize_t oldaccumulator;

    STRINGLIB_CHAR *p;

    /* empty string is an error */

    if (str->ptr >= str->end)

        return -1;

    for (p = str->ptr; p < str->end; p++) {

        digitval = STRINGLIB_TODECIMAL(*p);

        if (digitval < 0)

            return -1;

        /*

           This trick was copied from old Unicode format code.  It's cute,

           but would really suck on an old machine with a slow divide

           implementation.  Fortunately, in the normal case we do not

           expect too many digits.

        */

        oldaccumulator = accumulator;

        accumulator *= 10;

        if ((accumulator+10)/10 != oldaccumulator+1) {

            PyErr_Format(PyExc_ValueError,

                         "Too many decimal digits in format string");

            return -1;

        }

        accumulator += digitval;

    }

    return accumulator;

}

/************************************************************************/

/******** Functions to get field objects and specification strings ******/

/************************************************************************/

/* do the equivalent of obj.name */

static PyObject *

getattr(PyObject *obj, SubString *name)

{

    PyObject *newobj;

    PyObject *str = SubString_new_object(name);

    if (str == NULL)

        return NULL;

    newobj = PyObject_GetAttr(obj, str);

    Py_DECREF(str);

    return newobj;

}

/* do the equivalent of obj[idx], where obj is a sequence */

static PyObject *

getitem_sequence(PyObject *obj, Py_ssize_t idx)

{

    return PySequence_GetItem(obj, idx);

}

/* do the equivalent of obj[idx], where obj is not a sequence */

static PyObject *

getitem_idx(PyObject *obj, Py_ssize_t idx)

{

    PyObject *newobj;

    PyObject *idx_obj = PyLong_FromSsize_t(idx);

    if (idx_obj == NULL)

        return NULL;

    newobj = PyObject_GetItem(obj, idx_obj);

    Py_DECREF(idx_obj);

    return newobj;

}

/* do the equivalent of obj[name] */

static PyObject *

getitem_str(PyObject *obj, SubString *name)

{

    PyObject *newobj;

    PyObject *str = SubString_new_object(name);

    if (str == NULL)

        return NULL;

    newobj = PyObject_GetItem(obj, str);

    Py_DECREF(str);

    return newobj;

}

typedef struct {

    /* the entire string we're parsing.  we assume that someone else

       is managing its lifetime, and that it will exist for the

       lifetime of the iterator.  can be empty */

    SubString str;

    /* pointer to where we are inside field_name */

    STRINGLIB_CHAR *ptr;

} FieldNameIterator;

static int

FieldNameIterator_init(FieldNameIterator *self, STRINGLIB_CHAR *ptr,

                       Py_ssize_t len)

{

    SubString_init(&self->str, ptr, len);

    self->ptr = self->str.ptr;

    return 1;

}

static int

_FieldNameIterator_attr(FieldNameIterator *self, SubString *name)

{

    STRINGLIB_CHAR c;

    name->ptr = self->ptr;

    /* return everything until '.' or '[' */

    while (self->ptr < self->str.end) {

        switch (c = *self->ptr++) {

        case '[':

        case '.':

            /* backup so that we this character will be seen next time */

            self->ptr--;

            break;

        default:

            continue;

        }

        break;

    }

    /* end of string is okay */

    name->end = self->ptr;

    return 1;

}

static int

_FieldNameIterator_item(FieldNameIterator *self, SubString *name)

{

    int bracket_seen = 0;

    STRINGLIB_CHAR c;

    name->ptr = self->ptr;

    /* return everything until ']' */

    while (self->ptr < self->str.end) {

        switch (c = *self->ptr++) {

        case ']':

            bracket_seen = 1;

            break;

        default:

            continue;

        }

        break;

    }

    /* make sure we ended with a ']' */

    if (!bracket_seen) {

        PyErr_SetString(PyExc_ValueError, "Missing ']' in format string");

        return 0;

    }

    /* end of string is okay */

    /* don't include the ']' */

    name->end = self->ptr-1;

    return 1;

}

/* returns 0 on error, 1 on non-error termination, and 2 if it returns a value */

static int

FieldNameIterator_next(FieldNameIterator *self, int *is_attribute,

                       Py_ssize_t *name_idx, SubString *name)

{

    /* check at end of input */

    if (self->ptr >= self->str.end)

        return 1;

    switch (*self->ptr++) {

    case '.':

        *is_attribute = 1;

        if (_FieldNameIterator_attr(self, name) == 0)

            return 0;

        *name_idx = -1;

        break;

    case '[':

        *is_attribute = 0;

        if (_FieldNameIterator_item(self, name) == 0)

            return 0;

        *name_idx = get_integer(name);

        break;

    default:

        /* interal error, can't get here */

        assert(0);

        return 0;

    }

    /* empty string is an error */

    if (name->ptr == name->end) {

        PyErr_SetString(PyExc_ValueError, "Empty attribute in format string");

        return 0;

    }

    return 2;

}

/* input: field_name

   output: 'first' points to the part before the first '[' or '.'

           'first_idx' is -1 if 'first' is not an integer, otherwise

                       it's the value of first converted to an integer

           'rest' is an iterator to return the rest

*/

static int

field_name_split(STRINGLIB_CHAR *ptr, Py_ssize_t len, SubString *first,

                 Py_ssize_t *first_idx, FieldNameIterator *rest)

{

    STRINGLIB_CHAR c;

    STRINGLIB_CHAR *p = ptr;

    STRINGLIB_CHAR *end = ptr + len;

    /* find the part up until the first '.' or '[' */

    while (p < end) {

        switch (c = *p++) {

        case '[':

        case '.':

            /* backup so that we this character is available to the

               "rest" iterator */

            p--;

            break;

        default:

            continue;

        }

        break;

    }

    /* set up the return values */

    SubString_init(first, ptr, p - ptr);

    FieldNameIterator_init(rest, p, end - p);

    /* see if "first" is an integer, in which case it's used as an index */

    *first_idx = get_integer(first);

    /* zero length string is an error */

    if (first->ptr >= first->end) {

        PyErr_SetString(PyExc_ValueError, "empty field name");

        goto error;

    }

    return 1;

error:

    return 0;

}

/*

    get_field_object returns the object inside {}, before the

    format_spec.  It handles getindex and getattr lookups and consumes

    the entire input string.

*/

static PyObject *

get_field_object(SubString *input, PyObject *args, PyObject *kwargs)

{

    PyObject *obj = NULL;

    int ok;

    int is_attribute;

    SubString name;

    SubString first;

    Py_ssize_t index;

    FieldNameIterator rest;

    if (!field_name_split(input->ptr, input->end - input->ptr, &first,

                          &index, &rest)) {

        goto error;

    }

    if (index == -1) {

        /* look up in kwargs */

        PyObject *key = SubString_new_object(&first);

        if (key == NULL)

            goto error;

        if ((kwargs == NULL) || (obj = PyDict_GetItem(kwargs, key)) == NULL) {

            PyErr_SetObject(PyExc_KeyError, key);

            Py_DECREF(key);

            goto error;

        }

        Py_DECREF(key);

        Py_INCREF(obj);

    }

    else {

        /* look up in args */

        obj = PySequence_GetItem(args, index);

        if (obj == NULL)

            goto error;

    }

    /* iterate over the rest of the field_name */

    while ((ok = FieldNameIterator_next(&rest, &is_attribute, &index,

                                        &name)) == 2) {

        PyObject *tmp;

        if (is_attribute)

            /* getattr lookup "." */

            tmp = getattr(obj, &name);

        else

            /* getitem lookup "[]" */

            if (index == -1)

                tmp = getitem_str(obj, &name);

            else

                if (PySequence_Check(obj))

                    tmp = getitem_sequence(obj, index);

                else

                    /* not a sequence */

                    tmp = getitem_idx(obj, index);

        if (tmp == NULL)

            goto error;

        /* assign to obj */

        Py_DECREF(obj);

        obj = tmp;

    }

    /* end of iterator, this is the non-error case */

    if (ok == 1)

        return obj;

error:

    Py_XDECREF(obj);

    return NULL;

}

/************************************************************************/

/*****************  Field rendering functions  **************************/

/************************************************************************/

/*

    render_field() is the main function in this section.  It takes the

    field object and field specification string generated by

    get_field_and_spec, and renders the field into the output string.

    render_field calls fieldobj.__format__(format_spec) method, and

    appends to the output.

*/

static int

render_field(PyObject *fieldobj, SubString *format_spec, OutputString *output)

{

    int ok = 0;

    PyObject *result = NULL;

    PyObject *format_spec_object = NULL;

    PyObject *(*formatter)(PyObject *, STRINGLIB_CHAR *, Py_ssize_t) = NULL;

    STRINGLIB_CHAR* format_spec_start = format_spec->ptr ?

	    format_spec->ptr : NULL;

    Py_ssize_t format_spec_len = format_spec->ptr ?

	    format_spec->end - format_spec->ptr : 0;

    /* If we know the type exactly, skip the lookup of __format__ and just

       call the formatter directly. */

#if STRINGLIB_IS_UNICODE

    if (PyUnicode_CheckExact(fieldobj))

	formatter = _PyUnicode_FormatAdvanced;

    /* Unfortunately, there's a problem with checking for int, long,

       and float here.  If we're being included as unicode, their

       formatters expect string format_spec args.  For now, just skip

       this optimization for unicode.  This could be fixed, but it's a

       hassle. */

#else

    if (PyString_CheckExact(fieldobj))

	formatter = _PyBytes_FormatAdvanced;

    else if (PyInt_CheckExact(fieldobj))

	formatter =_PyInt_FormatAdvanced;

    else if (PyLong_CheckExact(fieldobj))

	formatter =_PyLong_FormatAdvanced;

    else if (PyFloat_CheckExact(fieldobj))

	formatter = _PyFloat_FormatAdvanced;

#endif

    if (formatter) {

	/* we know exactly which formatter will be called when __format__ is

	   looked up, so call it directly, instead. */

	result = formatter(fieldobj, format_spec_start, format_spec_len);

    }

    else {

	/* We need to create an object out of the pointers we have, because

	   __format__ takes a string/unicode object for format_spec. */

	format_spec_object = STRINGLIB_NEW(format_spec_start,

					   format_spec_len);

	if (format_spec_object == NULL)

	    goto done;

	result = PyObject_Format(fieldobj, format_spec_object);

    }