Objects/stringobject.c

   1 /***********************************************************
   2 Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
   3 The Netherlands.
   4
   5                         All Rights Reserved
   6
   7 Permission to use, copy, modify, and distribute this software and its
   8 documentation for any purpose and without fee is hereby granted,
   9 provided that the above copyright notice appear in all copies and that
  10 both that copyright notice and this permission notice appear in
  11 supporting documentation, and that the names of Stichting Mathematisch
  12 Centrum or CWI or Corporation for National Research Initiatives or
  13 CNRI not be used in advertising or publicity pertaining to
  14 distribution of the software without specific, written prior
  15 permission.
  16
  17 While CWI is the initial source for this software, a modified version
  18 is made available by the Corporation for National Research Initiatives
  19 (CNRI) at the Internet address ftp://ftp.python.org.
  20
  21 STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
  22 REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
  23 MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
  24 CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  25 DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  26 PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  27 TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  28 PERFORMANCE OF THIS SOFTWARE.
  29
  30 ******************************************************************/
  31
  32 /* String object implementation */
  33
  34 #include "Python.h"
  35
  36 #include "mymath.h"
  37 #include <ctype.h>
  38
  39 #ifdef COUNT_ALLOCS
  40 int null_strings, one_strings;
  41 #endif
  42
  43 #ifdef HAVE_LIMITS_H
  44 #include <limits.h>
  45 #else
  46 #ifndef UCHAR_MAX
  47 #define UCHAR_MAX 255
  48 #endif
  49 #endif
  50
  51 static PyStringObject *characters[UCHAR_MAX + 1];
  52 #ifndef DONT_SHARE_SHORT_STRINGS
  53 static PyStringObject *nullstring;
  54 #endif
  55
  56 /*
  57    Newsizedstringobject() and newstringobject() try in certain cases
  58    to share string objects.  When the size of the string is zero,
  59    these routines always return a pointer to the same string object;
  60    when the size is one, they return a pointer to an already existing
  61    object if the contents of the string is known.  For
  62    newstringobject() this is always the case, for
  63    newsizedstringobject() this is the case when the first argument in
  64    not NULL.
  65    A common practice to allocate a string and then fill it in or
  66    change it must be done carefully.  It is only allowed to change the
  67    contents of the string if the obect was gotten from
  68    newsizedstringobject() with a NULL first argument, because in the
  69    future these routines may try to do even more sharing of objects.
  70 */
  71 PyObject *
  72 PyString_FromStringAndSize(str, size)
  73         const char *str;
  74         int size;
  75 {
  76         register PyStringObject *op;
  77 #ifndef DONT_SHARE_SHORT_STRINGS
  78         if (size == 0 && (op = nullstring) != NULL) {
  79 #ifdef COUNT_ALLOCS
  80                 null_strings++;
  81 #endif
  82                 Py_INCREF(op);
  83                 return (PyObject *)op;
  84         }
  85         if (size == 1 && str != NULL &&
  86             (op = characters[*str & UCHAR_MAX]) != NULL)
  87         {
  88 #ifdef COUNT_ALLOCS
  89                 one_strings++;
  90 #endif
  91                 Py_INCREF(op);
  92                 return (PyObject *)op;
  93         }
  94 #endif /* DONT_SHARE_SHORT_STRINGS */
  95         op = (PyStringObject *)
  96                 malloc(sizeof(PyStringObject) + size * sizeof(char));
  97         if (op == NULL)
  98                 return PyErr_NoMemory();
  99         op->ob_type = &PyString_Type;
 100         op->ob_size = size;
 101 #ifdef CACHE_HASH
 102         op->ob_shash = -1;
 103 #endif
 104 #ifdef INTERN_STRINGS
 105         op->ob_sinterned = NULL;
 106 #endif
 107         _Py_NewReference(op);
 108         if (str != NULL)
 109                 memcpy(op->ob_sval, str, size);
 110         op->ob_sval[size] = '\0';
 111 #ifndef DONT_SHARE_SHORT_STRINGS
 112         if (size == 0) {
 113                 nullstring = op;
 114                 Py_INCREF(op);
 115         } else if (size == 1 && str != NULL) {
 116                 characters[*str & UCHAR_MAX] = op;
 117                 Py_INCREF(op);
 118         }
 119 #endif
 120         return (PyObject *) op;
 121 }
 122
 123 PyObject *
 124 PyString_FromString(str)
 125         const char *str;
 126 {
 127         register unsigned int size = strlen(str);
 128         register PyStringObject *op;
 129 #ifndef DONT_SHARE_SHORT_STRINGS
 130         if (size == 0 && (op = nullstring) != NULL) {
 131 #ifdef COUNT_ALLOCS
 132                 null_strings++;
 133 #endif
 134                 Py_INCREF(op);
 135                 return (PyObject *)op;
 136         }
 137         if (size == 1 && (op = characters[*str & UCHAR_MAX]) != NULL) {
 138 #ifdef COUNT_ALLOCS
 139                 one_strings++;
 140 #endif
 141                 Py_INCREF(op);
 142                 return (PyObject *)op;
 143         }
 144 #endif /* DONT_SHARE_SHORT_STRINGS */
 145         op = (PyStringObject *)
 146                 malloc(sizeof(PyStringObject) + size * sizeof(char));
 147         if (op == NULL)
 148                 return PyErr_NoMemory();
 149         op->ob_type = &PyString_Type;
 150         op->ob_size = size;
 151 #ifdef CACHE_HASH
 152         op->ob_shash = -1;
 153 #endif
 154 #ifdef INTERN_STRINGS
 155         op->ob_sinterned = NULL;
 156 #endif
 157         _Py_NewReference(op);
 158         strcpy(op->ob_sval, str);
 159 #ifndef DONT_SHARE_SHORT_STRINGS
 160         if (size == 0) {
 161                 nullstring = op;
 162                 Py_INCREF(op);
 163         } else if (size == 1) {
 164                 characters[*str & UCHAR_MAX] = op;
 165                 Py_INCREF(op);
 166         }
 167 #endif
 168         return (PyObject *) op;
 169 }
 170
 171 static void
 172 string_dealloc(op)
 173         PyObject *op;
 174 {
 175         PyMem_DEL(op);
 176 }
 177
 178 int
 179 PyString_Size(op)
 180         register PyObject *op;
 181 {
 182         if (!PyString_Check(op)) {
 183                 PyErr_BadInternalCall();
 184                 return -1;
 185         }
 186         return ((PyStringObject *)op) -> ob_size;
 187 }
 188
 189 /*const*/ char *
 190 PyString_AsString(op)
 191         register PyObject *op;
 192 {
 193         if (!PyString_Check(op)) {
 194                 PyErr_BadInternalCall();
 195                 return NULL;
 196         }
 197         return ((PyStringObject *)op) -> ob_sval;
 198 }
 199
 200 /* Methods */
 201
 202 static int
 203 string_print(op, fp, flags)
 204         PyStringObject *op;
 205         FILE *fp;
 206         int flags;
 207 {
 208         int i;
 209         char c;
 210         int quote;
 211         /* XXX Ought to check for interrupts when writing long strings */
 212         if (flags & Py_PRINT_RAW) {
 213                 fwrite(op->ob_sval, 1, (int) op->ob_size, fp);
 214                 return 0;
 215         }
 216
 217         /* figure out which quote to use; single is prefered */
 218         quote = '\'';
 219         if (strchr(op->ob_sval, '\'') && !strchr(op->ob_sval, '"'))
 220                 quote = '"';
 221
 222         fputc(quote, fp);
 223         for (i = 0; i < op->ob_size; i++) {
 224                 c = op->ob_sval[i];
 225                 if (c == quote || c == '\\')
 226                         fprintf(fp, "\\%c", c);
 227                 else if (c < ' ' || c >= 0177)
 228                         fprintf(fp, "\\%03o", c & 0377);
 229                 else
 230                         fputc(c, fp);
 231         }
 232         fputc(quote, fp);
 233         return 0;
 234 }
 235
 236 static PyObject *
 237 string_repr(op)
 238         register PyStringObject *op;
 239 {
 240         /* XXX overflow? */
 241         int newsize = 2 + 4 * op->ob_size * sizeof(char);
 242         PyObject *v = PyString_FromStringAndSize((char *)NULL, newsize);
 243         if (v == NULL) {
 244                 return NULL;
 245         }
 246         else {
 247                 register int i;
 248                 register char c;
 249                 register char *p;
 250                 int quote;
 251
 252                 /* figure out which quote to use; single is prefered */
 253                 quote = '\'';
 254                 if (strchr(op->ob_sval, '\'') && !strchr(op->ob_sval, '"'))
 255                         quote = '"';
 256
 257                 p = ((PyStringObject *)v)->ob_sval;
 258                 *p++ = quote;
 259                 for (i = 0; i < op->ob_size; i++) {
 260                         c = op->ob_sval[i];
 261                         if (c == quote || c == '\\')
 262                                 *p++ = '\\', *p++ = c;
 263                         else if (c < ' ' || c >= 0177) {
 264                                 sprintf(p, "\\%03o", c & 0377);
 265                                 while (*p != '\0')
 266                                         p++;
 267                         }
 268                         else
 269                                 *p++ = c;
 270                 }
 271                 *p++ = quote;
 272                 *p = '\0';
 273                 _PyString_Resize(
 274                         &v, (int) (p - ((PyStringObject *)v)->ob_sval));
 275                 return v;
 276         }
 277 }
 278
 279 static int
 280 string_length(a)
 281         PyStringObject *a;
 282 {
 283         return a->ob_size;
 284 }
 285
 286 static PyObject *
 287 string_concat(a, bb)
 288         register PyStringObject *a;
 289         register PyObject *bb;
 290 {
 291         register unsigned int size;
 292         register PyStringObject *op;
 293         if (!PyString_Check(bb)) {
 294                 PyErr_BadArgument();
 295                 return NULL;
 296         }
 297 #define b ((PyStringObject *)bb)
 298         /* Optimize cases with empty left or right operand */
 299         if (a->ob_size == 0) {
 300                 Py_INCREF(bb);
 301                 return bb;
 302         }
 303         if (b->ob_size == 0) {
 304                 Py_INCREF(a);
 305                 return (PyObject *)a;
 306         }
 307         size = a->ob_size + b->ob_size;
 308         op = (PyStringObject *)
 309                 malloc(sizeof(PyStringObject) + size * sizeof(char));
 310         if (op == NULL)
 311                 return PyErr_NoMemory();
 312         op->ob_type = &PyString_Type;
 313         op->ob_size = size;
 314 #ifdef CACHE_HASH
 315         op->ob_shash = -1;
 316 #endif
 317 #ifdef INTERN_STRINGS
 318         op->ob_sinterned = NULL;
 319 #endif
 320         _Py_NewReference(op);
 321         memcpy(op->ob_sval, a->ob_sval, (int) a->ob_size);
 322         memcpy(op->ob_sval + a->ob_size, b->ob_sval, (int) b->ob_size);
 323         op->ob_sval[size] = '\0';
 324         return (PyObject *) op;
 325 #undef b
 326 }
 327
 328 static PyObject *
 329 string_repeat(a, n)
 330         register PyStringObject *a;
 331         register int n;
 332 {
 333         register int i;
 334         register int size;
 335         register PyStringObject *op;
 336         if (n < 0)
 337                 n = 0;
 338         size = a->ob_size * n;
 339         if (size == a->ob_size) {
 340                 Py_INCREF(a);
 341                 return (PyObject *)a;
 342         }
 343         op = (PyStringObject *)
 344                 malloc(sizeof(PyStringObject) + size * sizeof(char));
 345         if (op == NULL)
 346                 return PyErr_NoMemory();
 347         op->ob_type = &PyString_Type;
 348         op->ob_size = size;
 349 #ifdef CACHE_HASH
 350         op->ob_shash = -1;
 351 #endif
 352 #ifdef INTERN_STRINGS
 353         op->ob_sinterned = NULL;
 354 #endif
 355         _Py_NewReference(op);
 356         for (i = 0; i < size; i += a->ob_size)
 357                 memcpy(op->ob_sval+i, a->ob_sval, (int) a->ob_size);
 358         op->ob_sval[size] = '\0';
 359         return (PyObject *) op;
 360 }
 361
 362 /* String slice a[i:j] consists of characters a[i] ... a[j-1] */
 363
 364 static PyObject *
 365 string_slice(a, i, j)
 366         register PyStringObject *a;
 367         register int i, j; /* May be negative! */
 368 {
 369         if (i < 0)
 370                 i = 0;
 371         if (j < 0)
 372                 j = 0; /* Avoid signed/unsigned bug in next line */
 373         if (j > a->ob_size)
 374                 j = a->ob_size;
 375         if (i == 0 && j == a->ob_size) { /* It's the same as a */
 376                 Py_INCREF(a);
 377                 return (PyObject *)a;
 378         }
 379         if (j < i)
 380                 j = i;
 381         return PyString_FromStringAndSize(a->ob_sval + i, (int) (j-i));
 382 }
 383
 384 static PyObject *
 385 string_item(a, i)
 386         PyStringObject *a;
 387         register int i;
 388 {
 389         int c;
 390         PyObject *v;
 391         if (i < 0 || i >= a->ob_size) {
 392                 PyErr_SetString(PyExc_IndexError, "string index out of range");
 393                 return NULL;
 394         }
 395         c = a->ob_sval[i] & UCHAR_MAX;
 396         v = (PyObject *) characters[c];
 397 #ifdef COUNT_ALLOCS
 398         if (v != NULL)
 399                 one_strings++;
 400 #endif
 401         if (v == NULL) {
 402                 v = PyString_FromStringAndSize((char *)NULL, 1);
 403                 if (v == NULL)
 404                         return NULL;
 405                 characters[c] = (PyStringObject *) v;
 406                 ((PyStringObject *)v)->ob_sval[0] = c;
 407         }
 408         Py_INCREF(v);
 409         return v;
 410 }
 411
 412 static int
 413 string_compare(a, b)
 414         PyStringObject *a, *b;
 415 {
 416         int len_a = a->ob_size, len_b = b->ob_size;
 417         int min_len = (len_a < len_b) ? len_a : len_b;
 418         int cmp;
 419         if (min_len > 0) {
 420                 cmp = Py_CHARMASK(*a->ob_sval) - Py_CHARMASK(*b->ob_sval);
 421                 if (cmp == 0)
 422                         cmp = memcmp(a->ob_sval, b->ob_sval, min_len);
 423                 if (cmp != 0)
 424                         return cmp;
 425         }
 426         return (len_a < len_b) ? -1 : (len_a > len_b) ? 1 : 0;
 427 }
 428
 429 static long
 430 string_hash(a)
 431         PyStringObject *a;
 432 {
 433         register int len;
 434         register unsigned char *p;
 435         register long x;
 436
 437 #ifdef CACHE_HASH
 438         if (a->ob_shash != -1)
 439                 return a->ob_shash;
 440 #ifdef INTERN_STRINGS
 441         if (a->ob_sinterned != NULL)
 442                 return (a->ob_shash =
 443                         ((PyStringObject *)(a->ob_sinterned))->ob_shash);
 444 #endif
 445 #endif
 446         len = a->ob_size;
 447         p = (unsigned char *) a->ob_sval;
 448         x = *p << 7;
 449         while (--len >= 0)
 450                 x = (1000003*x) ^ *p++;
 451         x ^= a->ob_size;
 452         if (x == -1)
 453                 x = -2;
 454 #ifdef CACHE_HASH
 455         a->ob_shash = x;
 456 #endif
 457         return x;
 458 }
 459
 460 static int
 461 string_buffer_getreadbuf(self, index, ptr)
 462         PyStringObject *self;
 463         int index;
 464         const void **ptr;
 465 {
 466         if ( index != 0 ) {
 467                 PyErr_SetString(PyExc_SystemError,
 468                                 "accessing non-existent string segment");
 469                 return -1;
 470         }
 471         *ptr = (void *)self->ob_sval;
 472         return self->ob_size;
 473 }
 474
 475 static int
 476 string_buffer_getwritebuf(self, index, ptr)
 477         PyStringObject *self;
 478         int index;
 479         const void **ptr;
 480 {
 481         PyErr_SetString(PyExc_TypeError,
 482                         "Cannot use string as modifiable buffer");
 483         return -1;
 484 }
 485
 486 static int
 487 string_buffer_getsegcount(self, lenp)
 488         PyStringObject *self;
 489         int *lenp;
 490 {
 491         if ( lenp )
 492                 *lenp = self->ob_size;
 493         return 1;
 494 }
 495
 496 static int
 497 string_buffer_getcharbuf(self, index, ptr)
 498         PyStringObject *self;
 499         int index;
 500         const char **ptr;
 501 {
 502         if ( index != 0 ) {
 503                 PyErr_SetString(PyExc_SystemError,
 504                                 "accessing non-existent string segment");
 505                 return -1;
 506         }
 507         *ptr = self->ob_sval;
 508         return self->ob_size;
 509 }
 510
 511 static PySequenceMethods string_as_sequence = {
 512         (inquiry)string_length, /*sq_length*/
 513         (binaryfunc)string_concat, /*sq_concat*/
 514         (intargfunc)string_repeat, /*sq_repeat*/
 515         (intargfunc)string_item, /*sq_item*/
 516         (intintargfunc)string_slice, /*sq_slice*/
 517         0,              /*sq_ass_item*/
 518         0,              /*sq_ass_slice*/
 519 };
 520
 521 static PyBufferProcs string_as_buffer = {
 522         (getreadbufferproc)string_buffer_getreadbuf,
 523         (getwritebufferproc)string_buffer_getwritebuf,
 524         (getsegcountproc)string_buffer_getsegcount,
 525         (getcharbufferproc)string_buffer_getcharbuf,
 526 };
 527
 528 PyTypeObject PyString_Type = {
 529         PyObject_HEAD_INIT(&PyType_Type)
 530         0,
 531         "string",
 532         sizeof(PyStringObject),
 533         sizeof(char),
 534         (destructor)string_dealloc, /*tp_dealloc*/
 535         (printfunc)string_print, /*tp_print*/
 536         0,              /*tp_getattr*/
 537         0,              /*tp_setattr*/
 538         (cmpfunc)string_compare, /*tp_compare*/
 539         (reprfunc)string_repr, /*tp_repr*/
 540         0,              /*tp_as_number*/
 541         &string_as_sequence,    /*tp_as_sequence*/
 542         0,              /*tp_as_mapping*/
 543         (hashfunc)string_hash, /*tp_hash*/
 544         0,              /*tp_call*/
 545         0,              /*tp_str*/
 546         0,              /*tp_getattro*/
 547         0,              /*tp_setattro*/
 548         &string_as_buffer,      /*tp_as_buffer*/
 549         Py_TPFLAGS_DEFAULT,     /*tp_flags*/
 550         0,              /*tp_doc*/
 551 };
 552
 553 void
 554 PyString_Concat(pv, w)
 555         register PyObject **pv;
 556         register PyObject *w;
 557 {
 558         register PyObject *v;
 559         if (*pv == NULL)
 560                 return;
 561         if (w == NULL || !PyString_Check(*pv)) {
 562                 Py_DECREF(*pv);
 563                 *pv = NULL;
 564                 return;
 565         }
 566         v = string_concat((PyStringObject *) *pv, w);
 567         Py_DECREF(*pv);
 568         *pv = v;
 569 }
 570
 571 void
 572 PyString_ConcatAndDel(pv, w)
 573         register PyObject **pv;
 574         register PyObject *w;
 575 {
 576         PyString_Concat(pv, w);
 577         Py_XDECREF(w);
 578 }
 579
 580
 581 /* The following function breaks the notion that strings are immutable:
 582    it changes the size of a string.  We get away with this only if there
 583    is only one module referencing the object.  You can also think of it
 584    as creating a new string object and destroying the old one, only
 585    more efficiently.  In any case, don't use this if the string may
 586    already be known to some other part of the code... */
 587
 588 int
 589 _PyString_Resize(pv, newsize)
 590         PyObject **pv;
 591         int newsize;
 592 {
 593         register PyObject *v;
 594         register PyStringObject *sv;
 595         v = *pv;
 596         if (!PyString_Check(v) || v->ob_refcnt != 1) {
 597                 *pv = 0;
 598                 Py_DECREF(v);
 599                 PyErr_BadInternalCall();
 600                 return -1;
 601         }
 602         /* XXX UNREF/NEWREF interface should be more symmetrical */
 603 #ifdef Py_REF_DEBUG
 604         --_Py_RefTotal;
 605 #endif
 606         _Py_ForgetReference(v);
 607         *pv = (PyObject *)
 608                 realloc((char *)v,
 609                         sizeof(PyStringObject) + newsize * sizeof(char));
 610         if (*pv == NULL) {
 611                 PyMem_DEL(v);
 612                 PyErr_NoMemory();
 613                 return -1;
 614         }
 615         _Py_NewReference(*pv);
 616         sv = (PyStringObject *) *pv;
 617         sv->ob_size = newsize;
 618         sv->ob_sval[newsize] = '\0';
 619         return 0;
 620 }
 621
 622 /* Helpers for formatstring */
 623
 624 static PyObject *
 625 getnextarg(args, arglen, p_argidx)
 626         PyObject *args;
 627         int arglen;
 628         int *p_argidx;
 629 {
 630         int argidx = *p_argidx;
 631         if (argidx < arglen) {
 632                 (*p_argidx)++;
 633                 if (arglen < 0)
 634                         return args;
 635                 else
 636                         return PyTuple_GetItem(args, argidx);
 637         }
 638         PyErr_SetString(PyExc_TypeError,
 639                         "not enough arguments for format string");
 640         return NULL;
 641 }
 642
 643 #define F_LJUST (1<<0)
 644 #define F_SIGN  (1<<1)
 645 #define F_BLANK (1<<2)
 646 #define F_ALT   (1<<3)
 647 #define F_ZERO  (1<<4)
 648
 649 static int
 650 formatfloat(buf, flags, prec, type, v)
 651         char *buf;
 652         int flags;
 653         int prec;
 654         int type;
 655         PyObject *v;
 656 {
 657         char fmt[20];
 658         double x;
 659         if (!PyArg_Parse(v, "d;float argument required", &x))
 660                 return -1;
 661         if (prec < 0)
 662                 prec = 6;
 663         if (prec > 50)
 664                 prec = 50; /* Arbitrary limitation */
 665         if (type == 'f' && fabs(x)/1e25 >= 1e25)
 666                 type = 'g';
 667         sprintf(fmt, "%%%s.%d%c", (flags&F_ALT) ? "#" : "", prec, type);
 668         sprintf(buf, fmt, x);
 669         return strlen(buf);
 670 }
 671
 672 static int
 673 formatint(buf, flags, prec, type, v)
 674         char *buf;
 675         int flags;
 676         int prec;
 677         int type;
 678         PyObject *v;
 679 {
 680         char fmt[20];
 681         long x;
 682         if (!PyArg_Parse(v, "l;int argument required", &x))
 683                 return -1;
 684         if (prec < 0)
 685                 prec = 1;
 686         sprintf(fmt, "%%%s.%dl%c", (flags&F_ALT) ? "#" : "", prec, type);
 687         sprintf(buf, fmt, x);
 688         return strlen(buf);
 689 }
 690
 691 static int
 692 formatchar(buf, v)
 693         char *buf;
 694         PyObject *v;
 695 {
 696         if (PyString_Check(v)) {
 697                 if (!PyArg_Parse(v, "c;%c requires int or char", &buf[0]))
 698                         return -1;
 699         }
 700         else {
 701                 if (!PyArg_Parse(v, "b;%c requires int or char", &buf[0]))
 702                         return -1;
 703         }
 704         buf[1] = '\0';
 705         return 1;
 706 }
 707
 708
 709 /* fmt%(v1,v2,...) is roughly equivalent to sprintf(fmt, v1, v2, ...) */
 710
 711 PyObject *
 712 PyString_Format(format, args)
 713         PyObject *format;
 714         PyObject *args;
 715 {
 716         char *fmt, *res;
 717         int fmtcnt, rescnt, reslen, arglen, argidx;
 718         int args_owned = 0;
 719         PyObject *result;
 720         PyObject *dict = NULL;
 721         if (format == NULL || !PyString_Check(format) || args == NULL) {
 722                 PyErr_BadInternalCall();
 723                 return NULL;
 724         }
 725         fmt = PyString_AsString(format);
 726         fmtcnt = PyString_Size(format);
 727         reslen = rescnt = fmtcnt + 100;
 728         result = PyString_FromStringAndSize((char *)NULL, reslen);
 729         if (result == NULL)
 730                 return NULL;
 731         res = PyString_AsString(result);
 732         if (PyTuple_Check(args)) {
 733                 arglen = PyTuple_Size(args);
 734                 argidx = 0;
 735         }
 736         else {
 737                 arglen = -1;
 738                 argidx = -2;
 739         }
 740         if (args->ob_type->tp_as_mapping)
 741                 dict = args;
 742         while (--fmtcnt >= 0) {
 743                 if (*fmt != '%') {
 744                         if (--rescnt < 0) {
 745                                 rescnt = fmtcnt + 100;
 746                                 reslen += rescnt;
 747                                 if (_PyString_Resize(&result, reslen) < 0)
 748                                         return NULL;
 749                                 res = PyString_AsString(result)
 750                                         + reslen - rescnt;
 751                                 --rescnt;
 752                         }
 753                         *res++ = *fmt++;
 754                 }
 755                 else {
 756                         /* Got a format specifier */
 757                         int flags = 0;
 758                         int width = -1;
 759                         int prec = -1;
 760                         int size = 0;
 761                         int c = '\0';
 762                         int fill;
 763                         PyObject *v = NULL;
 764                         PyObject *temp = NULL;
 765                         char *buf;
 766                         int sign;
 767                         int len;
 768                         char tmpbuf[120]; /* For format{float,int,char}() */
 769                         fmt++;
 770                         if (*fmt == '(') {
 771                                 char *keystart;
 772                                 int keylen;
 773                                 PyObject *key;
 774                                 int pcount = 1;
 775
 776                                 if (dict == NULL) {
 777                                         PyErr_SetString(PyExc_TypeError,
 778                                                  "format requires a mapping");
 779                                         goto error;
 780                                 }
 781                                 ++fmt;
 782                                 --fmtcnt;
 783                                 keystart = fmt;
 784                                 /* Skip over balanced parentheses */
 785                                 while (pcount > 0 && --fmtcnt >= 0) {
 786                                         if (*fmt == ')')
 787                                                 --pcount;
 788                                         else if (*fmt == '(')
 789                                                 ++pcount;
 790                                         fmt++;
 791                                 }
 792                                 keylen = fmt - keystart - 1;
 793                                 if (fmtcnt < 0 || pcount > 0) {
 794                                         PyErr_SetString(PyExc_ValueError,
 795                                                    "incomplete format key");
 796                                         goto error;
 797                                 }
 798                                 key = PyString_FromStringAndSize(keystart,
 799                                                                  keylen);
 800                                 if (key == NULL)
 801                                         goto error;
 802                                 if (args_owned) {
 803                                         Py_DECREF(args);
 804                                         args_owned = 0;
 805                                 }
 806                                 args = PyObject_GetItem(dict, key);
 807                                 Py_DECREF(key);
 808                                 if (args == NULL) {
 809                                         goto error;
 810                                 }
 811                                 args_owned = 1;
 812                                 arglen = -1;
 813                                 argidx = -2;
 814                         }
 815                         while (--fmtcnt >= 0) {
 816                                 switch (c = *fmt++) {
 817                                 case '-': flags |= F_LJUST; continue;
 818                                 case '+': flags |= F_SIGN; continue;
 819                                 case ' ': flags |= F_BLANK; continue;
 820                                 case '#': flags |= F_ALT; continue;
 821                                 case '0': flags |= F_ZERO; continue;
 822                                 }
 823                                 break;
 824                         }
 825                         if (c == '*') {
 826                                 v = getnextarg(args, arglen, &argidx);
 827                                 if (v == NULL)
 828                                         goto error;
 829                                 if (!PyInt_Check(v)) {
 830                                         PyErr_SetString(PyExc_TypeError,
 831                                                         "* wants int");
 832                                         goto error;
 833                                 }
 834                                 width = PyInt_AsLong(v);
 835                                 if (width < 0)
 836                                         width = 0;
 837                                 if (--fmtcnt >= 0)
 838                                         c = *fmt++;
 839                         }
 840                         else if (c >= 0 && isdigit(c)) {
 841                                 width = c - '0';
 842                                 while (--fmtcnt >= 0) {
 843                                         c = Py_CHARMASK(*fmt++);
 844                                         if (!isdigit(c))
 845                                                 break;
 846                                         if ((width*10) / 10 != width) {
 847                                                 PyErr_SetString(
 848                                                         PyExc_ValueError,
 849                                                         "width too big");
 850                                                 goto error;
 851                                         }
 852                                         width = width*10 + (c - '0');
 853                                 }
 854                         }
 855                         if (c == '.') {
 856                                 prec = 0;
 857                                 if (--fmtcnt >= 0)
 858                                         c = *fmt++;
 859                                 if (c == '*') {
 860                                         v = getnextarg(args, arglen, &argidx);
 861                                         if (v == NULL)
 862                                                 goto error;
 863                                         if (!PyInt_Check(v)) {
 864                                                 PyErr_SetString(
 865                                                         PyExc_TypeError,
 866                                                         "* wants int");
 867                                                 goto error;
 868                                         }
 869                                         prec = PyInt_AsLong(v);
 870                                         if (prec < 0)
 871                                                 prec = 0;
 872                                         if (--fmtcnt >= 0)
 873                                                 c = *fmt++;
 874                                 }
 875                                 else if (c >= 0 && isdigit(c)) {
 876                                         prec = c - '0';
 877                                         while (--fmtcnt >= 0) {
 878                                                 c = Py_CHARMASK(*fmt++);
 879                                                 if (!isdigit(c))
 880                                                         break;
 881                                                 if ((prec*10) / 10 != prec) {
 882                                                         PyErr_SetString(
 883                                                             PyExc_ValueError,
 884                                                             "prec too big");
 885                                                         goto error;
 886                                                 }
 887                                                 prec = prec*10 + (c - '0');
 888                                         }
 889                                 }
 890                         } /* prec */
 891                         if (fmtcnt >= 0) {
 892                                 if (c == 'h' || c == 'l' || c == 'L') {
 893                                         size = c;
 894                                         if (--fmtcnt >= 0)
 895                                                 c = *fmt++;
 896                                 }
 897                         }
 898                         if (fmtcnt < 0) {
 899                                 PyErr_SetString(PyExc_ValueError,
 900                                                 "incomplete format");
 901                                 goto error;
 902                         }
 903                         if (c != '%') {
 904                                 v = getnextarg(args, arglen, &argidx);
 905                                 if (v == NULL)
 906                                         goto error;
 907                         }
 908                         sign = 0;
 909                         fill = ' ';
 910                         switch (c) {
 911                         case '%':
 912                                 buf = "%";
 913                                 len = 1;
 914                                 break;
 915                         case 's':
 916                                 temp = PyObject_Str(v);
 917                                 if (temp == NULL)
 918                                         goto error;
 919                                 if (!PyString_Check(temp)) {
 920                                         PyErr_SetString(PyExc_TypeError,
 921                                           "%s argument has non-string str()");
 922                                         goto error;
 923                                 }
 924                                 buf = PyString_AsString(temp);
 925                                 len = PyString_Size(temp);
 926                                 if (prec >= 0 && len > prec)
 927                                         len = prec;
 928                                 break;
 929                         case 'i':
 930                         case 'd':
 931                         case 'u':
 932                         case 'o':
 933                         case 'x':
 934                         case 'X':
 935                                 if (c == 'i')
 936                                         c = 'd';
 937                                 buf = tmpbuf;
 938                                 len = formatint(buf, flags, prec, c, v);
 939                                 if (len < 0)
 940                                         goto error;
 941                                 sign = (c == 'd');
 942                                 if (flags&F_ZERO) {
 943                                         fill = '0';
 944                                         if ((flags&F_ALT) &&
 945                                             (c == 'x' || c == 'X') &&
 946                                             buf[0] == '0' && buf[1] == c) {
 947                                                 *res++ = *buf++;
 948                                                 *res++ = *buf++;
 949                                                 rescnt -= 2;
 950                                                 len -= 2;
 951                                                 width -= 2;
 952                                                 if (width < 0)
 953                                                         width = 0;
 954                                         }
 955                                 }
 956                                 break;
 957                         case 'e':
 958                         case 'E':
 959                         case 'f':
 960                         case 'g':
 961                         case 'G':
 962                                 buf = tmpbuf;
 963                                 len = formatfloat(buf, flags, prec, c, v);
 964                                 if (len < 0)
 965                                         goto error;
 966                                 sign = 1;
 967                                 if (flags&F_ZERO)
 968                                         fill = '0';
 969                                 break;
 970                         case 'c':
 971                                 buf = tmpbuf;
 972                                 len = formatchar(buf, v);
 973                                 if (len < 0)
 974                                         goto error;
 975                                 break;
 976                         default:
 977                                 PyErr_Format(PyExc_ValueError,
 978                                 "unsupported format character '%c' (0x%x)",
 979                                         c, c);
 980                                 goto error;
 981                         }
 982                         if (sign) {
 983                                 if (*buf == '-' || *buf == '+') {
 984                                         sign = *buf++;
 985                                         len--;
 986                                 }
 987                                 else if (flags & F_SIGN)
 988                                         sign = '+';
 989                                 else if (flags & F_BLANK)
 990                                         sign = ' ';
 991                                 else
 992                                         sign = '\0';
 993                         }
 994                         if (width < len)
 995                                 width = len;
 996                         if (rescnt < width + (sign != '\0')) {
 997                                 reslen -= rescnt;
 998                                 rescnt = width + fmtcnt + 100;
 999                                 reslen += rescnt;
1000                                 if (_PyString_Resize(&result, reslen) < 0)
1001                                         return NULL;
1002                                 res = PyString_AsString(result)
1003                                         + reslen - rescnt;
1004                         }
1005                         if (sign) {
1006                                 if (fill != ' ')
1007                                         *res++ = sign;
1008                                 rescnt--;
1009                                 if (width > len)
1010                                         width--;
1011                         }
1012                         if (width > len && !(flags&F_LJUST)) {
1013                                 do {
1014                                         --rescnt;
1015                                         *res++ = fill;
1016                                 } while (--width > len);
1017                         }
1018                         if (sign && fill == ' ')
1019                                 *res++ = sign;
1020                         memcpy(res, buf, len);
1021                         res += len;
1022                         rescnt -= len;
1023                         while (--width >= len) {
1024                                 --rescnt;
1025                                 *res++ = ' ';
1026                         }
1027                         if (dict && (argidx < arglen) && c != '%') {
1028                                 PyErr_SetString(PyExc_TypeError,
1029                                            "not all arguments converted");
1030                                 goto error;
1031                         }
1032                         Py_XDECREF(temp);
1033                 } /* '%' */
1034         } /* until end */
1035         if (argidx < arglen && !dict) {
1036                 PyErr_SetString(PyExc_TypeError,
1037                                 "not all arguments converted");
1038                 goto error;
1039         }
1040         if (args_owned) {
1041                 Py_DECREF(args);
1042         }
1043         _PyString_Resize(&result, reslen - rescnt);
1044         return result;
1045  error:
1046         Py_DECREF(result);
1047         if (args_owned) {
1048                 Py_DECREF(args);
1049         }
1050         return NULL;
1051 }
1052
1053
1054 #ifdef INTERN_STRINGS
1055
1056 static PyObject *interned;
1057
1058 void
1059 PyString_InternInPlace(p)
1060         PyObject **p;
1061 {
1062         register PyStringObject *s = (PyStringObject *)(*p);
1063         PyObject *t;
1064         if (s == NULL || !PyString_Check(s))
1065                 Py_FatalError("PyString_InternInPlace: strings only please!");
1066         if ((t = s->ob_sinterned) != NULL) {
1067                 if (t == (PyObject *)s)
1068                         return;
1069                 Py_INCREF(t);
1070                 *p = t;
1071                 Py_DECREF(s);
1072                 return;
1073         }
1074         if (interned == NULL) {
1075                 interned = PyDict_New();
1076                 if (interned == NULL)
1077                         return;
1078         }
1079         if ((t = PyDict_GetItem(interned, (PyObject *)s)) != NULL) {
1080                 Py_INCREF(t);
1081                 *p = s->ob_sinterned = t;
1082                 Py_DECREF(s);
1083                 return;
1084         }
1085         t = (PyObject *)s;
1086         if (PyDict_SetItem(interned, t, t) == 0) {
1087                 s->ob_sinterned = t;
1088                 return;
1089         }
1090         PyErr_Clear();
1091 }
1092
1093
1094 PyObject *
1095 PyString_InternFromString(cp)
1096         const char *cp;
1097 {
1098         PyObject *s = PyString_FromString(cp);
1099         if (s == NULL)
1100                 return NULL;
1101         PyString_InternInPlace(&s);
1102         return s;
1103 }
1104
1105 #endif
1106
1107 void
1108 PyString_Fini()
1109 {
1110         int i;
1111         for (i = 0; i < UCHAR_MAX + 1; i++) {
1112                 Py_XDECREF(characters[i]);
1113                 characters[i] = NULL;
1114         }
1115 #ifndef DONT_SHARE_SHORT_STRINGS
1116         Py_XDECREF(nullstring);
1117         nullstring = NULL;
1118 #endif
1119 #ifdef INTERN_STRINGS
1120         if (interned) {
1121                 int pos, changed;
1122                 PyObject *key, *value;
1123                 do {
1124                         changed = 0;
1125                         pos = 0;
1126                         while (PyDict_Next(interned, &pos, &key, &value)) {
1127                                 if (key->ob_refcnt == 2 && key == value) {
1128                                         PyDict_DelItem(interned, key);
1129                                         changed = 1;
1130                                 }
1131                         }
1132                 } while (changed);
1133         }
1134 #endif
1135 }