typedef struct {

PyObject *str; /* borrowed reference */

Py_ssize_t start, end;

} SubString;

typedef enum {

ANS_INIT,

ANS_AUTO,

ANS_MANUAL

} AutoNumberState; /* Keep track if we're auto-numbering fields */

typedef struct {

AutoNumberState an_state;

int an_field_number;

} AutoNumber;

static PyObject *

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

int recursion_depth, AutoNumber *auto_number);

static void

AutoNumber_Init(AutoNumber *auto_number)

{

auto_number->an_state = ANS_INIT;

auto_number->an_field_number = 0;

}

Py_LOCAL_INLINE(void)

SubString_init(SubString *str, PyObject *s, Py_ssize_t start, Py_ssize_t end)

{

str->str = s;

str->start = start;

str->end = end;

}

Py_LOCAL_INLINE(PyObject *)

SubString_new_object(SubString *str)

{

if (str->str == NULL)

Py_RETURN_NONE;

return PyUnicode_Substring(str->str, str->start, str->end);

}

Py_LOCAL_INLINE(PyObject *)

SubString_new_object_or_empty(SubString *str)

{

if (str->str == NULL) {

return PyUnicode_New(0, 0);

}

return SubString_new_object(str);

}

static int

autonumber_state_error(AutoNumberState state, int field_name_is_empty)

{

if (state == ANS_MANUAL) {

if (field_name_is_empty) {

PyErr_SetString(PyExc_ValueError, "cannot switch from "

"manual field specification to "

"automatic field numbering");

return 1;

}

}

else {

if (!field_name_is_empty) {

PyErr_SetString(PyExc_ValueError, "cannot switch from "

"automatic field numbering to "

"manual field specification");

return 1;

}

}

return 0;

}

static Py_ssize_t

get_integer(const SubString *str)

{

Py_ssize_t accumulator = 0;

Py_ssize_t digitval;

Py_ssize_t i;

/* empty string is an error */

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

return -1;

for (i = str->start; i < str->end; i++) {

digitval = Py_UNICODE_TODECIMAL(PyUnicode_READ_CHAR(str->str, i));

if (digitval < 0)

return -1;

/*

if (accumulator > (PY_SSIZE_T_MAX - digitval) / 10) {

PyErr_Format(PyExc_ValueError,

"Too many decimal digits in format string");

return -1;

}

accumulator = accumulator * 10 + digitval;

}

return accumulator;

}

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;

}

static PyObject *

getitem_sequence(PyObject *obj, Py_ssize_t idx)

{

return PySequence_GetItem(obj, idx);

}

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;

}

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

SubString str;

/* index to where we are inside field_name */

Py_ssize_t index;

} FieldNameIterator;

static int

FieldNameIterator_init(FieldNameIterator *self, PyObject *s,

Py_ssize_t start, Py_ssize_t end)

{

SubString_init(&self->str, s, start, end);

self->index = start;

return 1;

}

static int

_FieldNameIterator_attr(FieldNameIterator *self, SubString *name)

{

Py_UCS4 c;

name->str = self->str.str;

name->start = self->index;

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

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

c = PyUnicode_READ_CHAR(self->str.str, self->index++);

switch (c) {

case '[':

case '.':

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

self->index--;

break;

default:

continue;

}

break;

}

/* end of string is okay */

name->end = self->index;

return 1;

}

static int

_FieldNameIterator_item(FieldNameIterator *self, SubString *name)

{

int bracket_seen = 0;

Py_UCS4 c;

name->str = self->str.str;

name->start = self->index;

/* return everything until ']' */

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

c = PyUnicode_READ_CHAR(self->str.str, self->index++);

switch (c) {

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->index-1;

return 1;

}

static int

FieldNameIterator_next(FieldNameIterator *self, int *is_attribute,

Py_ssize_t *name_idx, SubString *name)

{

/* check at end of input */

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

return 1;

switch (PyUnicode_READ_CHAR(self->str.str, self->index++)) {

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);

if (*name_idx == -1 && PyErr_Occurred())

return 0;

break;

default:

/* Invalid character follows ']' */

PyErr_SetString(PyExc_ValueError, "Only '.' or '[' may "

"follow ']' in format field specifier");

return 0;

}

/* empty string is an error */

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

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

return 0;

}

return 2;

}

static int

field_name_split(PyObject *str, Py_ssize_t start, Py_ssize_t end, SubString *first,

Py_ssize_t *first_idx, FieldNameIterator *rest,

AutoNumber *auto_number)

{

Py_UCS4 c;

Py_ssize_t i = start;

int field_name_is_empty;

int using_numeric_index;

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

while (i < end) {

switch (c = PyUnicode_READ_CHAR(str, i++)) {

case '[':

case '.':

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

i--;

break;

default:

continue;

}

break;

}

/* set up the return values */

SubString_init(first, str, start, i);

FieldNameIterator_init(rest, str, i, end);

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

*first_idx = get_integer(first);

if (*first_idx == -1 && PyErr_Occurred())

return 0;

field_name_is_empty = first->start >= first->end;

/* If the field name is omitted or if we have a numeric index

using_numeric_index = field_name_is_empty || *first_idx != -1;

/* We always get here exactly one time for each field we're

/* Check if we need to do the auto-numbering. It's not needed if

if (auto_number) {

/* Initialize our auto numbering state if this is the first

if (auto_number->an_state == ANS_INIT && using_numeric_index)

auto_number->an_state = field_name_is_empty ?

ANS_AUTO : ANS_MANUAL;

/* Make sure our state is consistent with what we're doing

if (using_numeric_index)

if (autonumber_state_error(auto_number->an_state,

field_name_is_empty))

return 0;

/* Zero length field means we want to do auto-numbering of the

if (field_name_is_empty)

*first_idx = (auto_number->an_field_number)++;

}

return 1;

}

static PyObject *

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

AutoNumber *auto_number)

{

PyObject *obj = NULL;

int ok;

int is_attribute;

SubString name;

SubString first;

Py_ssize_t index;

FieldNameIterator rest;

if (!field_name_split(input->str, input->start, input->end, &first,

&index, &rest, auto_number)) {

goto error;

}

if (index == -1) {

/* look up in kwargs */

PyObject *key = SubString_new_object(&first);

if (key == NULL) {

goto error;

}

if (kwargs == NULL) {

PyErr_SetObject(PyExc_KeyError, key);

Py_DECREF(key);

goto error;

}

/* Use PyObject_GetItem instead of PyDict_GetItem because this

obj = PyObject_GetItem(kwargs, key);

Py_DECREF(key);

if (obj == NULL) {

goto error;

}

}

else {

/* If args is NULL, we have a format string with a positional field

if (args == NULL) {

PyErr_SetString(PyExc_ValueError, "Format string contains "

"positional fields");

goto error;

}

/* 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;

}

static int

render_field(PyObject *fieldobj, SubString *format_spec, _PyUnicodeWriter *writer)

{

int ok = 0;

PyObject *result = NULL;

PyObject *format_spec_object = NULL;

int (*formatter) (_PyUnicodeWriter*, PyObject *, PyObject *, Py_ssize_t, Py_ssize_t) = NULL;

int err;

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

if (PyUnicode_CheckExact(fieldobj))

formatter = _PyUnicode_FormatAdvancedWriter;

else if (PyLong_CheckExact(fieldobj))

formatter = _PyLong_FormatAdvancedWriter;

else if (PyFloat_CheckExact(fieldobj))

formatter = _PyFloat_FormatAdvancedWriter;

else if (PyComplex_CheckExact(fieldobj))

formatter = _PyComplex_FormatAdvancedWriter;

if (formatter) {

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

err = formatter(writer, fieldobj, format_spec->str,

format_spec->start, format_spec->end);

return (err == 0);

}

else {

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

if (format_spec->str)

format_spec_object = PyUnicode_Substring(format_spec->str,

format_spec->start,

format_spec->end);

else

format_spec_object = PyUnicode_New(0, 0);

if (format_spec_object == NULL)

goto done;

result = PyObject_Format(fieldobj, format_spec_object);

}

if (result == NULL)

goto done;

if (_PyUnicodeWriter_WriteStr(writer, result) == -1)

goto done;

ok = 1;

done:

Py_XDECREF(format_spec_object);

Py_XDECREF(result);

return ok;

}

static int

parse_field(SubString *str, SubString *field_name, SubString *format_spec,

int *format_spec_needs_expanding, Py_UCS4 *conversion)

{

/* Note this function works if the field name is zero length,

Py_UCS4 c = 0;

/* initialize these, as they may be empty */

*conversion = '\0';

SubString_init(format_spec, NULL, 0, 0);

/* Search for the field name. it's terminated by the end of

field_name->str = str->str;

field_name->start = str->start;

while (str->start < str->end) {

switch ((c = PyUnicode_READ_CHAR(str->str, str->start++))) {

case '{':

PyErr_SetString(PyExc_ValueError, "unexpected '{' in field name");

return 0;

case '[':

for (; str->start < str->end; str->start++)

if (PyUnicode_READ_CHAR(str->str, str->start) == ']')

break;

continue;

case '}':

case ':':

case '!':

break;

default:

continue;

}

break;

}

field_name->end = str->start - 1;

if (c == '!' || c == ':') {

Py_ssize_t count;

/* we have a format specifier and/or a conversion */

/* don't include the last character */

/* see if there's a conversion specifier */

if (c == '!') {

/* there must be another character present */

if (str->start >= str->end) {

PyErr_SetString(PyExc_ValueError,

"end of string while looking for conversion "

"specifier");

return 0;

}

*conversion = PyUnicode_READ_CHAR(str->str, str->start++);

if (str->start < str->end) {

c = PyUnicode_READ_CHAR(str->str, str->start++);

if (c == '}')

return 1;

if (c != ':') {

PyErr_SetString(PyExc_ValueError,

"expected ':' after conversion specifier");

return 0;

}

}

}

format_spec->str = str->str;

format_spec->start = str->start;

count = 1;

while (str->start < str->end) {

switch ((c = PyUnicode_READ_CHAR(str->str, str->start++))) {

case '{':

*format_spec_needs_expanding = 1;

count++;

break;

case '}':

count--;

if (count == 0) {

format_spec->end = str->start - 1;

return 1;

}

break;

default:

break;

}

}

PyErr_SetString(PyExc_ValueError, "unmatched '{' in format spec");

return 0;

}

else if (c != '}') {

PyErr_SetString(PyExc_ValueError, "expected '}' before end of string");

return 0;

}

return 1;

}

typedef struct {

SubString str;

} MarkupIterator;

static int

MarkupIterator_init(MarkupIterator *self, PyObject *str,

Py_ssize_t start, Py_ssize_t end)

{

SubString_init(&self->str, str, start, end);

return 1;

}

static int

MarkupIterator_next(MarkupIterator *self, SubString *literal,

int *field_present, SubString *field_name,

SubString *format_spec, Py_UCS4 *conversion,

int *format_spec_needs_expanding)

{

int at_end;

Py_UCS4 c = 0;

Py_ssize_t start;

Py_ssize_t len;

int markup_follows = 0;

/* initialize all of the output variables */

SubString_init(literal, NULL, 0, 0);

SubString_init(field_name, NULL, 0, 0);

SubString_init(format_spec, NULL, 0, 0);

*conversion = '\0';

*format_spec_needs_expanding = 0;

*field_present = 0;

/* No more input, end of iterator. This is the normal exit

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

return 1;

start = self->str.start;

/* First read any literal text. Read until the end of string, an

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

switch (c = PyUnicode_READ_CHAR(self->str.str, self->str.start++)) {

case '{':

case '}':

markup_follows = 1;

break;

default:

continue;

}

break;

}

at_end = self->str.start >= self->str.end;

len = self->str.start - start;

if ((c == '}') && (at_end ||

(c != PyUnicode_READ_CHAR(self->str.str,

self->str.start)))) {

PyErr_SetString(PyExc_ValueError, "Single '}' encountered "

"in format string");

return 0;

}

if (at_end && c == '{') {

PyErr_SetString(PyExc_ValueError, "Single '{' encountered "

"in format string");

return 0;

}

if (!at_end) {

if (c == PyUnicode_READ_CHAR(self->str.str, self->str.start)) {

/* escaped } or {, skip it in the input. there is no

self->str.start++;

markup_follows = 0;

}

else

len--;

}

/* record the literal text */

literal->str = self->str.str;

literal->start = start;

literal->end = start + len;

if (!markup_follows)

return 2;

/* this is markup; parse the field */

*field_present = 1;

if (!parse_field(&self->str, field_name, format_spec,

format_spec_needs_expanding, conversion))

return 0;

return 2;

}

static PyObject *

do_conversion(PyObject *obj, Py_UCS4 conversion)

{

/* XXX in pre-3.0, do we need to convert this to unicode, since it

switch (conversion) {

case 'r':

return PyObject_Repr(obj);

case 's':

return PyObject_Str(obj);

case 'a':

return PyObject_ASCII(obj);

default:

if (conversion > 32 && conversion < 127) {

/* It's the ASCII subrange; casting to char is safe

PyErr_Format(PyExc_ValueError,

"Unknown conversion specifier %c",

(char)conversion);

} else

PyErr_Format(PyExc_ValueError,

"Unknown conversion specifier \\x%x",

(unsigned int)conversion);

return NULL;

}

}

static int

output_markup(SubString *field_name, SubString *format_spec,

int format_spec_needs_expanding, Py_UCS4 conversion,

_PyUnicodeWriter *writer, PyObject *args, PyObject *kwargs,

int recursion_depth, AutoNumber *auto_number)

{

PyObject *tmp = NULL;

PyObject *fieldobj = NULL;

SubString expanded_format_spec;

SubString *actual_format_spec;

int result = 0;

/* convert field_name to an object */

fieldobj = get_field_object(field_name, args, kwargs, auto_number);

if (fieldobj == NULL)

goto done;

if (conversion != '\0') {

tmp = do_conversion(fieldobj, conversion);

if (tmp == NULL || PyUnicode_READY(tmp) == -1)

goto done;

/* do the assignment, transferring ownership: fieldobj = tmp */

Py_DECREF(fieldobj);

fieldobj = tmp;

tmp = NULL;

}

/* if needed, recurively compute the format_spec */

if (format_spec_needs_expanding) {

tmp = build_string(format_spec, args, kwargs, recursion_depth-1,

auto_number);

if (tmp == NULL || PyUnicode_READY(tmp) == -1)

goto done;

/* note that in the case we're expanding the format string,

SubString_init(&expanded_format_spec, tmp, 0, PyUnicode_GET_LENGTH(tmp));

actual_format_spec = &expanded_format_spec;

}

else

actual_format_spec = format_spec;

if (render_field(fieldobj, actual_format_spec, writer) == 0)

goto done;

result = 1;

done:

Py_XDECREF(fieldobj);

Py_XDECREF(tmp);

return result;

}

static int

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

_PyUnicodeWriter *writer, int recursion_depth, AutoNumber *auto_number)

{

MarkupIterator iter;

int format_spec_needs_expanding;

int result;

int field_present;

SubString literal;

SubString field_name;

SubString format_spec;

Py_UCS4 conversion;

MarkupIterator_init(&iter, input->str, input->start, input->end);

while ((result = MarkupIterator_next(&iter, &literal, &field_present,

&field_name, &format_spec,

&conversion,

&format_spec_needs_expanding)) == 2) {

if (literal.end != literal.start) {

if (!field_present && iter.str.start == iter.str.end)

writer->overallocate = 0;

if (_PyUnicodeWriter_WriteSubstring(writer, literal.str,

literal.start, literal.end) < 0)

return 0;

}

if (field_present) {

if (iter.str.start == iter.str.end)

writer->overallocate = 0;

if (!output_markup(&field_name, &format_spec,

format_spec_needs_expanding, conversion, writer,

args, kwargs, recursion_depth, auto_number))

return 0;

}

}

return result;

}

static PyObject *

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

int recursion_depth, AutoNumber *auto_number)

{

_PyUnicodeWriter writer;

/* check the recursion level */

if (recursion_depth <= 0) {

PyErr_SetString(PyExc_ValueError,

"Max string recursion exceeded");

return NULL;

}

_PyUnicodeWriter_Init(&writer);

writer.overallocate = 1;

writer.min_length = PyUnicode_GET_LENGTH(input->str) + 100;

if (!do_markup(input, args, kwargs, &writer, recursion_depth,

auto_number)) {

_PyUnicodeWriter_Dealloc(&writer);

return NULL;

}

return _PyUnicodeWriter_Finish(&writer);

}

static PyObject *

do_string_format(PyObject *self, PyObject *args, PyObject *kwargs)

{

SubString input;

/* PEP 3101 says only 2 levels, so that

int recursion_depth = 2;

AutoNumber auto_number;

if (PyUnicode_READY(self) == -1)

return NULL;

AutoNumber_Init(&auto_number);

SubString_init(&input, self, 0, PyUnicode_GET_LENGTH(self));

return build_string(&input, args, kwargs, recursion_depth, &auto_number);

}

static PyObject *

do_string_format_map(PyObject *self, PyObject *obj)

{

return do_string_format(self, NULL, obj);

}

typedef struct {

PyObject_HEAD

PyObject *str;

MarkupIterator it_markup;

} formatteriterobject;

static void

formatteriter_dealloc(formatteriterobject *it)

{

Py_XDECREF(it->str);

PyObject_FREE(it);

}

static PyObject *

formatteriter_next(formatteriterobject *it)

{

SubString literal;

SubString field_name;

SubString format_spec;

Py_UCS4 conversion;

int format_spec_needs_expanding;

int field_present;