1 /*

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

     3 

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

     5     compiled for both unicode and string objects.

     6 */

     7 

     8 

     9 /* Defines for Python 2.6 compatability */

    10 #if PY_VERSION_HEX < 0x03000000

    11 #define PyLong_FromSsize_t _PyLong_FromSsize_t

    12 #endif

    13 

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

    15 #define INITIAL_SIZE_INCREMENT 100

    16 #define SIZE_MULTIPLIER 2

    17 #define MAX_SIZE_INCREMENT  3200

    18 

    19 

    20 /************************************************************************/

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

    22 /************************************************************************/

    23 

    24 /*

    25    A SubString consists of the characters between two string or

    26    unicode pointers.

    27 */

    28 typedef struct {

    29     STRINGLIB_CHAR *ptr;

    30     STRINGLIB_CHAR *end;

    31 } SubString;

    32 

    33 

    34 /* forward declaration for recursion */

    35 static PyObject *

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

    37              int recursion_depth);

    38 

    39 

    40 

    41 /************************************************************************/

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

    43 /************************************************************************/

    44 

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

    46 Py_LOCAL_INLINE(void)

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

    48 {

    49     str->ptr = p;

    50     if (p == NULL)

    51         str->end = NULL;

    52     else

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

    54 }

    55 

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

    57 Py_LOCAL_INLINE(PyObject *)

    58 SubString_new_object(SubString *str)

    59 {

    60     if (str->ptr == NULL) {

    61         Py_INCREF(Py_None);

    62         return Py_None;

    63     }

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

    65 }

    66 

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

    68 Py_LOCAL_INLINE(PyObject *)

    69 SubString_new_object_or_empty(SubString *str)

    70 {

    71     if (str->ptr == NULL) {

    72         return STRINGLIB_NEW(NULL, 0);

    73     }

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

    75 }

    76 

    77 /************************************************************************/

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

    79 /************************************************************************/

    80 

    81 typedef struct {

    82     STRINGLIB_CHAR *ptr;

    83     STRINGLIB_CHAR *end;

    84     PyObject *obj;

    85     Py_ssize_t size_increment;

    86 } OutputString;

    87 

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

    89 static int

    90 output_initialize(OutputString *output, Py_ssize_t size)

    91 {

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

    93     if (output->obj == NULL)

    94         return 0;

    95 

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

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

    98     output->size_increment = INITIAL_SIZE_INCREMENT;

    99 

   100     return 1;

   101 }

   102 

   103 /*

   104     output_extend reallocates the output string buffer.

   105     It returns a status:  0 for a failed reallocation,

   106     1 for success.

   107 */

   108 

   109 static int

   110 output_extend(OutputString *output, Py_ssize_t count)

   111 {

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

   113     Py_ssize_t curlen = output->ptr - startptr;

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

   115 

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

   117         return 0;

   118     startptr = STRINGLIB_STR(output->obj);

   119     output->ptr = startptr + curlen;

   120     output->end = startptr + maxlen;

   121     if (output->size_increment < MAX_SIZE_INCREMENT)

   122         output->size_increment *= SIZE_MULTIPLIER;

   123     return 1;

   124 }

   125 

   126 /*

   127     output_data dumps characters into our output string

   128     buffer.

   129 

   130     In some cases, it has to reallocate the string.

   131 

   132     It returns a status:  0 for a failed reallocation,

   133     1 for success.

   134 */

   135 static int

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

   137 {

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

   139         return 0;

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

   141     output->ptr += count;

   142     return 1;

   143 }

   144 

   145 /************************************************************************/

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

   147 /************************************************************************/

   148 

   149 static Py_ssize_t

   150 get_integer(const SubString *str)

   151 {

   152     Py_ssize_t accumulator = 0;

   153     Py_ssize_t digitval;

   154     Py_ssize_t oldaccumulator;

   155     STRINGLIB_CHAR *p;

   156 

   157     /* empty string is an error */

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

   159         return -1;

   160 

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

   162         digitval = STRINGLIB_TODECIMAL(*p);

   163         if (digitval < 0)

   164             return -1;

   165         /*

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

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

   168            implementation.  Fortunately, in the normal case we do not

   169            expect too many digits.

   170         */

   171         oldaccumulator = accumulator;

   172         accumulator *= 10;

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

   174             PyErr_Format(PyExc_ValueError,

   175                          "Too many decimal digits in format string");

   176             return -1;

   177         }

   178         accumulator += digitval;

   179     }

   180     return accumulator;

   181 }

   182 

   183 /************************************************************************/

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

   185 /************************************************************************/

   186 

   187 /* do the equivalent of obj.name */

   188 static PyObject *

   189 getattr(PyObject *obj, SubString *name)

   190 {

   191     PyObject *newobj;

   192     PyObject *str = SubString_new_object(name);

   193     if (str == NULL)

   194         return NULL;

   195     newobj = PyObject_GetAttr(obj, str);

   196     Py_DECREF(str);

   197     return newobj;

   198 }

   199 

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

   201 static PyObject *

   202 getitem_sequence(PyObject *obj, Py_ssize_t idx)

   203 {

   204     return PySequence_GetItem(obj, idx);

   205 }

   206 

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

   208 static PyObject *

   209 getitem_idx(PyObject *obj, Py_ssize_t idx)

   210 {

   211     PyObject *newobj;

   212     PyObject *idx_obj = PyLong_FromSsize_t(idx);

   213     if (idx_obj == NULL)

   214         return NULL;

   215     newobj = PyObject_GetItem(obj, idx_obj);

   216     Py_DECREF(idx_obj);

   217     return newobj;

   218 }

   219 

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

   221 static PyObject *

   222 getitem_str(PyObject *obj, SubString *name)

   223 {

   224     PyObject *newobj;

   225     PyObject *str = SubString_new_object(name);

   226     if (str == NULL)

   227         return NULL;

   228     newobj = PyObject_GetItem(obj, str);

   229     Py_DECREF(str);

   230     return newobj;

   231 }

   232 

   233 typedef struct {

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

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

   236        lifetime of the iterator.  can be empty */

   237     SubString str;

   238 

   239     /* pointer to where we are inside field_name */

   240     STRINGLIB_CHAR *ptr;

   241 } FieldNameIterator;

   242 

   243 

   244 static int

   245 FieldNameIterator_init(FieldNameIterator *self, STRINGLIB_CHAR *ptr,

   246                        Py_ssize_t len)

   247 {

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

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

   250     return 1;

   251 }

   252 

   253 static int

   254 _FieldNameIterator_attr(FieldNameIterator *self, SubString *name)

   255 {

   256     STRINGLIB_CHAR c;

   257 

   258     name->ptr = self->ptr;

   259 

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

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

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

   263         case '[':

   264         case '.':

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

   266             self->ptr--;

   267             break;

   268         default:

   269             continue;

   270         }

   271         break;

   272     }

   273     /* end of string is okay */

   274     name->end = self->ptr;

   275     return 1;

   276 }

   277 

   278 static int

   279 _FieldNameIterator_item(FieldNameIterator *self, SubString *name)

   280 {

   281     int bracket_seen = 0;

   282     STRINGLIB_CHAR c;

   283 

   284     name->ptr = self->ptr;

   285 

   286     /* return everything until ']' */

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

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

   289         case ']':

   290             bracket_seen = 1;

   291             break;

   292         default:

   293             continue;

   294         }

   295         break;

   296     }

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

   298     if (!bracket_seen) {

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

   300         return 0;

   301     }

   302 

   303     /* end of string is okay */

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

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

   306     return 1;

   307 }

   308 

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

   310 static int

   311 FieldNameIterator_next(FieldNameIterator *self, int *is_attribute,

   312                        Py_ssize_t *name_idx, SubString *name)

   313 {

   314     /* check at end of input */

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

   316         return 1;

   317 

   318     switch (*self->ptr++) {

   319     case '.':

   320         *is_attribute = 1;

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

   322             return 0;

   323         *name_idx = -1;

   324         break;

   325     case '[':

   326         *is_attribute = 0;

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

   328             return 0;

   329         *name_idx = get_integer(name);

   330         break;

   331     default:

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

   333         assert(0);

   334         return 0;

   335     }

   336 

   337     /* empty string is an error */

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

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

   340         return 0;

   341     }

   342 

   343     return 2;

   344 }

   345 

   346 

   347 /* input: field_name

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

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

   350                        it's the value of first converted to an integer

   351            'rest' is an iterator to return the rest

   352 */

   353 static int

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

   355                  Py_ssize_t *first_idx, FieldNameIterator *rest)

   356 {

   357     STRINGLIB_CHAR c;

   358     STRINGLIB_CHAR *p = ptr;

   359     STRINGLIB_CHAR *end = ptr + len;

   360 

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

   362     while (p < end) {

   363         switch (c = *p++) {

   364         case '[':

   365         case '.':

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

   367                "rest" iterator */

   368             p--;

   369             break;

   370         default:

   371             continue;

   372         }

   373         break;

   374     }

   375 

   376     /* set up the return values */

   377     SubString_init(first, ptr, p - ptr);

   378     FieldNameIterator_init(rest, p, end - p);

   379 

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

   381     *first_idx = get_integer(first);

   382 

   383     /* zero length string is an error */

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

   385         PyErr_SetString(PyExc_ValueError, "empty field name");

   386         goto error;

   387     }

   388 

   389     return 1;

   390 error:

   391     return 0;

   392 }

   393 

   394 

   395 /*

   396     get_field_object returns the object inside {}, before the

   397     format_spec.  It handles getindex and getattr lookups and consumes

   398     the entire input string.

   399 */

   400 static PyObject *

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

   402 {

   403     PyObject *obj = NULL;

   404     int ok;

   405     int is_attribute;

   406     SubString name;

   407     SubString first;

   408     Py_ssize_t index;

   409     FieldNameIterator rest;

   410 

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

   412                           &index, &rest)) {

   413         goto error;

   414     }

   415 

   416     if (index == -1) {

   417         /* look up in kwargs */

   418         PyObject *key = SubString_new_object(&first);

   419         if (key == NULL)

   420             goto error;

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

   422             PyErr_SetObject(PyExc_KeyError, key);

   423             Py_DECREF(key);

   424             goto error;

   425         }

   426         Py_DECREF(key);

   427         Py_INCREF(obj);

   428     }

   429     else {

   430         /* look up in args */

   431         obj = PySequence_GetItem(args, index);

   432         if (obj == NULL)

   433             goto error;

   434     }

   435 

   436     /* iterate over the rest of the field_name */

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

   438                                         &name)) == 2) {

   439         PyObject *tmp;

   440 

   441         if (is_attribute)

   442             /* getattr lookup "." */

   443             tmp = getattr(obj, &name);

   444         else

   445             /* getitem lookup "[]" */

   446             if (index == -1)

   447                 tmp = getitem_str(obj, &name);

   448             else

   449                 if (PySequence_Check(obj))

   450                     tmp = getitem_sequence(obj, index);

   451                 else

   452                     /* not a sequence */

   453                     tmp = getitem_idx(obj, index);

   454         if (tmp == NULL)

   455             goto error;

   456 

   457         /* assign to obj */

   458         Py_DECREF(obj);

   459         obj = tmp;

   460     }

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

   462     if (ok == 1)

   463         return obj;

   464 error:

   465     Py_XDECREF(obj);

   466     return NULL;

   467 }

   468 

   469 /************************************************************************/

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

   471 /************************************************************************/

   472 

   473 /*

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

   475     field object and field specification string generated by

   476     get_field_and_spec, and renders the field into the output string.

   477 

   478     render_field calls fieldobj.__format__(format_spec) method, and

   479     appends to the output.

   480 */

   481 static int

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

   483 {

   484     int ok = 0;

   485     PyObject *result = NULL;

   486     PyObject *format_spec_object = NULL;

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

   488     STRINGLIB_CHAR* format_spec_start = format_spec->ptr ?

   489 	    format_spec->ptr : NULL;

   490     Py_ssize_t format_spec_len = format_spec->ptr ?

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

   492 

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

   494        call the formatter directly. */

   495 #if STRINGLIB_IS_UNICODE

   496     if (PyUnicode_CheckExact(fieldobj))

   497 	formatter = _PyUnicode_FormatAdvanced;

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

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

   500        formatters expect string format_spec args.  For now, just skip

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

   502        hassle. */

   503 #else

   504     if (PyString_CheckExact(fieldobj))

   505 	formatter = _PyBytes_FormatAdvanced;

   506     else if (PyInt_CheckExact(fieldobj))

   507 	formatter =_PyInt_FormatAdvanced;

   508     else if (PyLong_CheckExact(fieldobj))

   509 	formatter =_PyLong_FormatAdvanced;

   510     else if (PyFloat_CheckExact(fieldobj))

   511 	formatter = _PyFloat_FormatAdvanced;

   512 #endif

   513 

   514     if (formatter) {

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

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

   517 	result = formatter(fieldobj, format_spec_start, format_spec_len);

   518     }

   519     else {

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

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

   522 	format_spec_object = STRINGLIB_NEW(format_spec_start,

   523 					   format_spec_len);

   524 	if (format_spec_object == NULL)

   525 	    goto done;

   526 

   527 	result = PyObject_Format(fieldobj, format_spec_object);

   528     }

   529     if (result == NULL)

   530         goto done;

   531 

   532 #if PY_VERSION_HEX >= 0x03000000

   533     assert(PyUnicode_Check(result));

   534 #else

   535     assert(PyString_Check(result) || PyUnicode_Check(result));

   536 

   537     /* Convert result to our type.  We could be str, and result could

   538        be unicode */

   539     {

   540 	PyObject *tmp = STRINGLIB_TOSTR(result);

   541 	if (tmp == NULL)

   542 	    goto done;

   543 	Py_DECREF(result);

   544 	result = tmp;

   545     }

   546 #endif

   547 

   548     ok = output_data(output,

   549                      STRINGLIB_STR(result), STRINGLIB_LEN(result));

   550 done:

   551     Py_XDECREF(format_spec_object);

   552     Py_XDECREF(result);

   553     return ok;

   554 }

   555 

   556 static int

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

   558             STRINGLIB_CHAR *conversion)

   559 {

   560     STRINGLIB_CHAR c = 0;

   561 

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

   563     *conversion = '\0';

   564     SubString_init(format_spec, NULL, 0);

   565 

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

   567        string, or a ':' or '!' */

   568     field_name->ptr = str->ptr;

   569     while (str->ptr < str->end) {

   570         switch (c = *(str->ptr++)) {

   571         case ':':

   572         case '!':

   573             break;

   574         default:

   575             continue;

   576         }

   577         break;

   578     }

   579 

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

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

   582         /* don't include the last character */

   583         field_name->end = str->ptr-1;

   584 

   585         /* the format specifier is the rest of the string */

   586         format_spec->ptr = str->ptr;

   587         format_spec->end = str->end;

   588 

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

   590         if (c == '!') {

   591             /* there must be another character present */

   592             if (format_spec->ptr >= format_spec->end) {

   593                 PyErr_SetString(PyExc_ValueError,

   594                                 "end of format while looking for conversion "

   595                                 "specifier");

   596                 return 0;

   597             }

   598             *conversion = *(format_spec->ptr++);

   599 

   600             /* if there is another character, it must be a colon */

   601             if (format_spec->ptr < format_spec->end) {

   602                 c = *(format_spec->ptr++);

   603                 if (c != ':') {

   604                     PyErr_SetString(PyExc_ValueError,

   605                                     "expected ':' after format specifier");

   606                     return 0;

   607                 }

   608             }

   609         }

   610 

   611         return 1;

   612 

   613     }

   614     else {

   615         /* end of string, there's no format_spec or conversion */

   616         field_name->end = str->ptr;

   617         return 1;

   618     }

   619 }

   620 

   621 /************************************************************************/

   622 /******* Output string allocation and escape-to-markup processing  ******/

   623 /************************************************************************/

   624 

   625 /* MarkupIterator breaks the string into pieces of either literal

   626    text, or things inside {} that need to be marked up.  it is

   627    designed to make it easy to wrap a Python iterator around it, for

   628    use with the Formatter class */

   629 

   630 typedef struct {

   631     SubString str;

   632 } MarkupIterator;

   633 

   634 static int

   635 MarkupIterator_init(MarkupIterator *self, STRINGLIB_CHAR *ptr, Py_ssize_t len)

   636 {

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

   638     return 1;

   639 }

   640 

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

   642    string (or something to be expanded) */

   643 static int

   644 MarkupIterator_next(MarkupIterator *self, SubString *literal,

   645                     SubString *field_name, SubString *format_spec,

   646                     STRINGLIB_CHAR *conversion,

   647                     int *format_spec_needs_expanding)

   648 {

   649     int at_end;

   650     STRINGLIB_CHAR c = 0;

   651     STRINGLIB_CHAR *start;

   652     int count;

   653     Py_ssize_t len;

   654     int markup_follows = 0;

   655 

   656     /* initialize all of the output variables */

   657     SubString_init(literal, NULL, 0);

   658     SubString_init(field_name, NULL, 0);

   659     SubString_init(format_spec, NULL, 0);

   660     *conversion = '\0';

   661     *format_spec_needs_expanding = 0;

   662 

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

   664        path. */

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

   666         return 1;

   667 

   668     start = self->str.ptr;

   669 

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

   671        escaped '{' or '}', or an unescaped '{'.  In order to never

   672        allocate memory and so I can just pass pointers around, if

   673        there's an escaped '{' or '}' then we'll return the literal

   674        including the brace, but no format object.  The next time

   675        through, we'll return the rest of the literal, skipping past

   676        the second consecutive brace. */

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

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

   679         case '{':

   680         case '}':

   681             markup_follows = 1;

   682             break;

   683         default:

   684             continue;

   685         }

   686         break;

   687     }

   688 

   689     at_end = self->str.ptr >= self->str.end;

   690     len = self->str.ptr - start;

   691 

   692     if ((c == '}') && (at_end || (c != *self->str.ptr))) {

   693         PyErr_SetString(PyExc_ValueError, "Single '}' encountered "

   694                         "in format string");

   695         return 0;

   696     }

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

   698         PyErr_SetString(PyExc_ValueError, "Single '{' encountered "

   699                         "in format string");

   700         return 0;

   701     }

   702     if (!at_end) {

   703         if (c == *self->str.ptr) {

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

   705                markup object following us, just this literal text */

   706             self->str.ptr++;

   707             markup_follows = 0;

   708         }

   709         else

   710             len--;

   711     }

   712 

   713     /* record the literal text */

   714     literal->ptr = start;

   715     literal->end = start + len;

   716 

   717     if (!markup_follows)

   718         return 2;

   719 

   720     /* this is markup, find the end of the string by counting nested

   721        braces.  note that this prohibits escaped braces, so that

   722        format_specs cannot have braces in them. */

   723     count = 1;

   724 

   725     start = self->str.ptr;

   726 

   727     /* we know we can't have a zero length string, so don't worry

   728        about that case */

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

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

   731         case '{':

   732             /* the format spec needs to be recursively expanded.

   733                this is an optimization, and not strictly needed */

   734             *format_spec_needs_expanding = 1;

   735             count++;

   736             break;

   737         case '}':

   738             count--;

   739             if (count <= 0) {

   740                 /* we're done.  parse and get out */

   741                 SubString s;

   742 

   743                 SubString_init(&s, start, self->str.ptr - 1 - start);

   744                 if (parse_field(&s, field_name, format_spec, conversion) == 0)

   745                     return 0;

   746 

   747                 /* a zero length field_name is an error */

   748                 if (field_name->ptr == field_name->end) {

   749                     PyErr_SetString(PyExc_ValueError, "zero length field name "

   750                                     "in format");

   751                     return 0;

   752                 }

   753 

   754                 /* success */

   755                 return 2;

   756             }

   757             break;

   758         }

   759     }

   760 

   761     /* end of string while searching for matching '}' */

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

   763     return 0;

   764 }

   765 

   766 

   767 /* do the !r or !s conversion on obj */

   768 static PyObject *

   769 do_conversion(PyObject *obj, STRINGLIB_CHAR conversion)

   770 {

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

   772        might have returned a string? */

   773     switch (conversion) {

   774     case 'r':

   775         return PyObject_Repr(obj);

   776     case 's':

   777         return STRINGLIB_TOSTR(obj);

   778     default:

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

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

   781 		   (assuming the execution character set is an ASCII

   782 		   superset). */

   783         	PyErr_Format(PyExc_ValueError,

   784                      "Unknown conversion specifier %c",

   785                      (char)conversion);

   786 	} else

   787 		PyErr_Format(PyExc_ValueError,

   788 		     "Unknown conversion specifier \\x%x",

   789 		     (unsigned int)conversion);

   790         return NULL;

   791     }

   792 }

   793 

   794 /* given:

   795 

   796    {field_name!conversion:format_spec}

   797 

   798    compute the result and write it to output.

   799    format_spec_needs_expanding is an optimization.  if it's false,

   800    just output the string directly, otherwise recursively expand the

   801    format_spec string. */

   802 

   803 static int

   804 output_markup(SubString *field_name, SubString *format_spec,

   805               int format_spec_needs_expanding, STRINGLIB_CHAR conversion,

   806               OutputString *output, PyObject *args, PyObject *kwargs,

   807               int recursion_depth)

   808 {

   809     PyObject *tmp = NULL;

   810     PyObject *fieldobj = NULL;

   811     SubString expanded_format_spec;

   812     SubString *actual_format_spec;

   813     int result = 0;

   814 

   815     /* convert field_name to an object */

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

   817     if (fieldobj == NULL)

   818         goto done;

   819 

   820     if (conversion != '\0') {

   821         tmp = do_conversion(fieldobj, conversion);

   822         if (tmp == NULL)

   823             goto done;

   824 

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

   826         Py_DECREF(fieldobj);

   827         fieldobj = tmp;

   828         tmp = NULL;

   829     }

   830 

   831     /* if needed, recurively compute the format_spec */

   832     if (format_spec_needs_expanding) {

   833         tmp = build_string(format_spec, args, kwargs, recursion_depth-1);

   834         if (tmp == NULL)

   835             goto done;

   836 

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

   838            tmp must be kept around until after the call to

   839            render_field. */

   840         SubString_init(&expanded_format_spec,

   841                        STRINGLIB_STR(tmp), STRINGLIB_LEN(tmp));

   842         actual_format_spec = &expanded_format_spec;

   843     }

   844     else

   845         actual_format_spec = format_spec;

   846 

   847     if (render_field(fieldobj, actual_format_spec, output) == 0)

   848         goto done;

   849 

   850     result = 1;

   851 

   852 done:

   853     Py_XDECREF(fieldobj);

   854     Py_XDECREF(tmp);

   855 

   856     return result;

   857 }

   858 

   859 /*

   860     do_markup is the top-level loop for the format() method.  It

   861     searches through the format string for escapes to markup codes, and

   862     calls other functions to move non-markup text to the output,

   863     and to perform the markup to the output.

   864 */

   865 static int

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

   867           OutputString *output, int recursion_depth)

   868 {

   869     MarkupIterator iter;

   870     int format_spec_needs_expanding;

   871     int result;

   872     SubString literal;

   873     SubString field_name;

   874     SubString format_spec;

   875     STRINGLIB_CHAR conversion;

   876 

   877     MarkupIterator_init(&iter, input->ptr, input->end - input->ptr);

   878     while ((result = MarkupIterator_next(&iter, &literal, &field_name,

   879                                          &format_spec, &conversion,

   880                                          &format_spec_needs_expanding)) == 2) {

   881         if (!output_data(output, literal.ptr, literal.end - literal.ptr))

   882             return 0;

   883         if (field_name.ptr != field_name.end)

   884             if (!output_markup(&field_name, &format_spec,

   885                                format_spec_needs_expanding, conversion, output,

   886                                args, kwargs, recursion_depth))

   887                 return 0;

   888     }

   889     return result;

   890 }

   891 

   892 

   893 /*

   894     build_string allocates the output string and then

   895     calls do_markup to do the heavy lifting.

   896 */

   897 static PyObject *

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

   899              int recursion_depth)

   900 {

   901     OutputString output;

   902     PyObject *result = NULL;

   903     Py_ssize_t count;

   904 

   905     output.obj = NULL; /* needed so cleanup code always works */

   906 

   907     /* check the recursion level */

   908     if (recursion_depth <= 0) {

   909         PyErr_SetString(PyExc_ValueError,

   910                         "Max string recursion exceeded");

   911         goto done;

   912     }

   913 

   914     /* initial size is the length of the format string, plus the size

   915        increment.  seems like a reasonable default */

   916     if (!output_initialize(&output,

   917                            input->end - input->ptr +

   918                            INITIAL_SIZE_INCREMENT))

   919         goto done;

   920 

   921     if (!do_markup(input, args, kwargs, &output, recursion_depth)) {

   922         goto done;

   923     }

   924 

   925     count = output.ptr - STRINGLIB_STR(output.obj);

   926     if (STRINGLIB_RESIZE(&output.obj, count) < 0) {

   927         goto done;

   928     }

   929 

   930     /* transfer ownership to result */

   931     result = output.obj;

   932     output.obj = NULL;

   933 

   934 done:

   935     Py_XDECREF(output.obj);

   936     return result;

   937 }

   938 

   939 /************************************************************************/

   940 /*********** main routine ***********************************************/

   941 /************************************************************************/

   942 

   943 /* this is the main entry point */

   944 static PyObject *

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

   946 {

   947     SubString input;

   948 

   949     /* PEP 3101 says only 2 levels, so that

   950        "{0:{1}}".format('abc', 's')            # works

   951        "{0:{1:{2}}}".format('abc', 's', '')    # fails

   952     */

   953     int recursion_depth = 2;

   954 

   955     SubString_init(&input, STRINGLIB_STR(self), STRINGLIB_LEN(self));

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

   957 }

   958 

   959 

   960 

   961 /************************************************************************/

   962 /*********** formatteriterator ******************************************/

   963 /************************************************************************/

   964 

   965 /* This is used to implement string.Formatter.vparse().  It exists so

   966    Formatter can share code with the built in unicode.format() method.

   967    It's really just a wrapper around MarkupIterator that is callable

   968    from Python. */

   969 

   970 typedef struct {

   971     PyObject_HEAD

   972 

   973     STRINGLIB_OBJECT *str;

   974 

   975     MarkupIterator it_markup;

   976 } formatteriterobject;

   977 

   978 static void

   979 formatteriter_dealloc(formatteriterobject *it)

   980 {

   981     Py_XDECREF(it->str);

   982     PyObject_FREE(it);

   983 }

   984 

   985 /* returns a tuple:

   986    (literal, field_name, format_spec, conversion)

   987 

   988    literal is any literal text to output.  might be zero length

   989    field_name is the string before the ':'.  might be None

   990    format_spec is the string after the ':'.  mibht be None

   991    conversion is either None, or the string after the '!'

   992 */

   993 static PyObject *

   994 formatteriter_next(formatteriterobject *it)

   995 {

   996     SubString literal;

   997     SubString field_name;

   998     SubString format_spec;

   999     STRINGLIB_CHAR conversion;

  1000     int format_spec_needs_expanding;

  1001     int result = MarkupIterator_next(&it->it_markup, &literal, &field_name,

  1002                                      &format_spec, &conversion,

  1003                                      &format_spec_needs_expanding);

  1004 

  1005     /* all of the SubString objects point into it->str, so no

  1006        memory management needs to be done on them */

  1007     assert(0 <= result && result <= 2);

  1008     if (result == 0 || result == 1)

  1009         /* if 0, error has already been set, if 1, iterator is empty */

  1010         return NULL;

  1011     else {

  1012         PyObject *literal_str = NULL;

  1013         PyObject *field_name_str = NULL;

  1014         PyObject *format_spec_str = NULL;

  1015         PyObject *conversion_str = NULL;

  1016         PyObject *tuple = NULL;

  1017         int has_field = field_name.ptr != field_name.end;

  1018 

  1019         literal_str = SubString_new_object(&literal);

  1020         if (literal_str == NULL)

  1021             goto done;

  1022 

  1023         field_name_str = SubString_new_object(&field_name);

  1024         if (field_name_str == NULL)

  1025             goto done;

  1026 

  1027         /* if field_name is non-zero length, return a string for

  1028            format_spec (even if zero length), else return None */

  1029         format_spec_str = (has_field ?

  1030                            SubString_new_object_or_empty :

  1031                            SubString_new_object)(&format_spec);

  1032         if (format_spec_str == NULL)

  1033             goto done;

  1034 

  1035         /* if the conversion is not specified, return a None,

  1036            otherwise create a one length string with the conversion

  1037            character */

  1038         if (conversion == '\0') {

  1039             conversion_str = Py_None;

  1040             Py_INCREF(conversion_str);

  1041         }

  1042         else

  1043 	    conversion_str = STRINGLIB_NEW(&conversion, 1);

  1044         if (conversion_str == NULL)

  1045             goto done;

  1046 

  1047         tuple = PyTuple_Pack(4, literal_str, field_name_str, format_spec_str,

  1048                              conversion_str);

  1049     done:

  1050         Py_XDECREF(literal_str);

  1051         Py_XDECREF(field_name_str);

  1052         Py_XDECREF(format_spec_str);

  1053         Py_XDECREF(conversion_str);

  1054         return tuple;

  1055     }

  1056 }

  1057 

  1058 static PyMethodDef formatteriter_methods[] = {

  1059     {NULL,		NULL}		/* sentinel */

  1060 };

  1061 

  1062 static PyTypeObject PyFormatterIter_Type = {

  1063     PyVarObject_HEAD_INIT(&PyType_Type, 0)

  1064     "formatteriterator",		/* tp_name */

  1065     sizeof(formatteriterobject),	/* tp_basicsize */

  1066     0,					/* tp_itemsize */

  1067     /* methods */

  1068     (destructor)formatteriter_dealloc,	/* tp_dealloc */

  1069     0,					/* tp_print */

  1070     0,					/* tp_getattr */

  1071     0,					/* tp_setattr */

  1072     0,					/* tp_compare */

  1073     0,					/* tp_repr */

  1074     0,					/* tp_as_number */

  1075     0,					/* tp_as_sequence */

  1076     0,					/* tp_as_mapping */

  1077     0,					/* tp_hash */

  1078     0,					/* tp_call */

  1079     0,					/* tp_str */

  1080     PyObject_GenericGetAttr,		/* tp_getattro */

  1081     0,					/* tp_setattro */

  1082     0,					/* tp_as_buffer */

  1083     Py_TPFLAGS_DEFAULT,			/* tp_flags */

  1084     0,					/* tp_doc */

  1085     0,					/* tp_traverse */

  1086     0,					/* tp_clear */

  1087     0,					/* tp_richcompare */

  1088     0,					/* tp_weaklistoffset */

  1089     PyObject_SelfIter,			/* tp_iter */

  1090     (iternextfunc)formatteriter_next,	/* tp_iternext */

  1091     formatteriter_methods,		/* tp_methods */

  1092     0,

  1093 };

  1094 

  1095 /* unicode_formatter_parser is used to implement

  1096    string.Formatter.vformat.  it parses a string and returns tuples

  1097    describing the parsed elements.  It's a wrapper around

  1098    stringlib/string_format.h's MarkupIterator */

  1099 static PyObject *

  1100 formatter_parser(STRINGLIB_OBJECT *self)

  1101 {

  1102     formatteriterobject *it;

  1103 

  1104     it = PyObject_New(formatteriterobject, &PyFormatterIter_Type);

  1105     if (it == NULL)

  1106         return NULL;

  1107 

  1108     /* take ownership, give the object to the iterator */

  1109     Py_INCREF(self);

  1110     it->str = self;

  1111 

  1112     /* initialize the contained MarkupIterator */

  1113     MarkupIterator_init(&it->it_markup,

  1114                         STRINGLIB_STR(self),

  1115                         STRINGLIB_LEN(self));

  1116 

  1117     return (PyObject *)it;

  1118 }

  1119 

  1120 

  1121 /************************************************************************/

  1122 /*********** fieldnameiterator ******************************************/

  1123 /************************************************************************/

  1124 

  1125 

  1126 /* This is used to implement string.Formatter.vparse().  It parses the

  1127    field name into attribute and item values.  It's a Python-callable

  1128    wrapper around FieldNameIterator */

  1129 

  1130 typedef struct {

  1131     PyObject_HEAD

  1132 

  1133     STRINGLIB_OBJECT *str;

  1134 

  1135     FieldNameIterator it_field;