Objects/abstract.c

   1 /* Abstract Object Interface (many thanks to Jim Fulton) */
   2
   3 #include "Python.h"
   4 #include <ctype.h>
   5 #include "structmember.h" /* we need the offsetof() macro from there */
   6 #include "longintrepr.h"
   7
   8 #define NEW_STYLE_NUMBER(o) PyType_HasFeature((o)->ob_type, \
   9                                 Py_TPFLAGS_CHECKTYPES)
  10
  11
  12 /* Shorthands to return certain errors */
  13
  14 static PyObject *
  15 type_error(const char *msg, PyObject *obj)
  16 {
  17         PyErr_Format(PyExc_TypeError, msg, obj->ob_type->tp_name);
  18         return NULL;
  19 }
  20
  21 static PyObject *
  22 null_error(void)
  23 {
  24         if (!PyErr_Occurred())
  25                 PyErr_SetString(PyExc_SystemError,
  26                                 "null argument to internal routine");
  27         return NULL;
  28 }
  29
  30 /* Operations on any object */
  31
  32 int
  33 PyObject_Cmp(PyObject *o1, PyObject *o2, int *result)
  34 {
  35         int r;
  36
  37         if (o1 == NULL || o2 == NULL) {
  38                 null_error();
  39                 return -1;
  40         }
  41         r = PyObject_Compare(o1, o2);
  42         if (PyErr_Occurred())
  43                 return -1;
  44         *result = r;
  45         return 0;
  46 }
  47
  48 PyObject *
  49 PyObject_Type(PyObject *o)
  50 {
  51         PyObject *v;
  52
  53         if (o == NULL)
  54                 return null_error();
  55         v = (PyObject *)o->ob_type;
  56         Py_INCREF(v);
  57         return v;
  58 }
  59
  60 Py_ssize_t
  61 PyObject_Size(PyObject *o)
  62 {
  63         PySequenceMethods *m;
  64
  65         if (o == NULL) {
  66                 null_error();
  67                 return -1;
  68         }
  69
  70         m = o->ob_type->tp_as_sequence;
  71         if (m && m->sq_length)
  72                 return m->sq_length(o);
  73
  74         return PyMapping_Size(o);
  75 }
  76
  77 #undef PyObject_Length
  78 Py_ssize_t
  79 PyObject_Length(PyObject *o)
  80 {
  81         return PyObject_Size(o);
  82 }
  83 #define PyObject_Length PyObject_Size
  84
  85
  86 /* The length hint function returns a non-negative value from o.__len__()
  87    or o.__length_hint__().  If those methods aren't found or return a negative
  88    value, then the defaultvalue is returned.  This function never fails.
  89    Accordingly, it will mask exceptions raised in either method.
  90 */
  91
  92 Py_ssize_t
  93 _PyObject_LengthHint(PyObject *o, Py_ssize_t defaultvalue)
  94 {
  95         static PyObject *hintstrobj = NULL;
  96         PyObject *ro;
  97         Py_ssize_t rv;
  98
  99         /* try o.__len__() */
 100         rv = PyObject_Size(o);
 101         if (rv >= 0)
 102                 return rv;
 103         if (PyErr_Occurred())
 104                 PyErr_Clear();
 105
 106         /* cache a hashed version of the attribute string */
 107         if (hintstrobj == NULL) {
 108                 hintstrobj = PyString_InternFromString("__length_hint__");
 109                 if (hintstrobj == NULL)
 110                         goto defaultcase;
 111         }
 112
 113         /* try o.__length_hint__() */
 114         ro = PyObject_CallMethodObjArgs(o, hintstrobj, NULL);
 115         if (ro == NULL)
 116                 goto defaultcase;
 117         rv = PyInt_AsLong(ro);
 118         Py_DECREF(ro);
 119         if (rv >= 0)
 120                 return rv;
 121
 122 defaultcase:
 123         if (PyErr_Occurred())
 124                 PyErr_Clear();
 125         return defaultvalue;
 126 }
 127
 128 PyObject *
 129 PyObject_GetItem(PyObject *o, PyObject *key)
 130 {
 131         PyMappingMethods *m;
 132
 133         if (o == NULL || key == NULL)
 134                 return null_error();
 135
 136         m = o->ob_type->tp_as_mapping;
 137         if (m && m->mp_subscript)
 138                 return m->mp_subscript(o, key);
 139
 140         if (o->ob_type->tp_as_sequence) {
 141                 if (PyIndex_Check(key)) {
 142                         Py_ssize_t key_value;
 143                         key_value = PyNumber_AsSsize_t(key, PyExc_IndexError);
 144                         if (key_value == -1 && PyErr_Occurred())
 145                                 return NULL;
 146                         return PySequence_GetItem(o, key_value);
 147                 }
 148                 else if (o->ob_type->tp_as_sequence->sq_item)
 149                         return type_error("sequence index must "
 150                                           "be integer, not '%.200s'", key);
 151         }
 152
 153         return type_error("'%.200s' object is unsubscriptable", o);
 154 }
 155
 156 int
 157 PyObject_SetItem(PyObject *o, PyObject *key, PyObject *value)
 158 {
 159         PyMappingMethods *m;
 160
 161         if (o == NULL || key == NULL || value == NULL) {
 162                 null_error();
 163                 return -1;
 164         }
 165         m = o->ob_type->tp_as_mapping;
 166         if (m && m->mp_ass_subscript)
 167                 return m->mp_ass_subscript(o, key, value);
 168
 169         if (o->ob_type->tp_as_sequence) {
 170                 if (PyIndex_Check(key)) {
 171                         Py_ssize_t key_value;
 172                         key_value = PyNumber_AsSsize_t(key, PyExc_IndexError);
 173                         if (key_value == -1 && PyErr_Occurred())
 174                                 return -1;
 175                         return PySequence_SetItem(o, key_value, value);
 176                 }
 177                 else if (o->ob_type->tp_as_sequence->sq_ass_item) {
 178                         type_error("sequence index must be "
 179                                    "integer, not '%.200s'", key);
 180                         return -1;
 181                 }
 182         }
 183
 184         type_error("'%.200s' object does not support item assignment", o);
 185         return -1;
 186 }
 187
 188 int
 189 PyObject_DelItem(PyObject *o, PyObject *key)
 190 {
 191         PyMappingMethods *m;
 192
 193         if (o == NULL || key == NULL) {
 194                 null_error();
 195                 return -1;
 196         }
 197         m = o->ob_type->tp_as_mapping;
 198         if (m && m->mp_ass_subscript)
 199                 return m->mp_ass_subscript(o, key, (PyObject*)NULL);
 200
 201         if (o->ob_type->tp_as_sequence) {
 202                 if (PyIndex_Check(key)) {
 203                         Py_ssize_t key_value;
 204                         key_value = PyNumber_AsSsize_t(key, PyExc_IndexError);
 205                         if (key_value == -1 && PyErr_Occurred())
 206                                 return -1;
 207                         return PySequence_DelItem(o, key_value);
 208                 }
 209                 else if (o->ob_type->tp_as_sequence->sq_ass_item) {
 210                         type_error("sequence index must be "
 211                                    "integer, not '%.200s'", key);
 212                         return -1;
 213                 }
 214         }
 215
 216         type_error("'%.200s' object does not support item deletion", o);
 217         return -1;
 218 }
 219
 220 int
 221 PyObject_DelItemString(PyObject *o, char *key)
 222 {
 223         PyObject *okey;
 224         int ret;
 225
 226         if (o == NULL || key == NULL) {
 227                 null_error();
 228                 return -1;
 229         }
 230         okey = PyString_FromString(key);
 231         if (okey == NULL)
 232                 return -1;
 233         ret = PyObject_DelItem(o, okey);
 234         Py_DECREF(okey);
 235         return ret;
 236 }
 237
 238 int
 239 PyObject_AsCharBuffer(PyObject *obj,
 240                           const char **buffer,
 241                           Py_ssize_t *buffer_len)
 242 {
 243         PyBufferProcs *pb;
 244         char *pp;
 245         Py_ssize_t len;
 246
 247         if (obj == NULL || buffer == NULL || buffer_len == NULL) {
 248                 null_error();
 249                 return -1;
 250         }
 251         pb = obj->ob_type->tp_as_buffer;
 252         if (pb == NULL ||
 253              pb->bf_getcharbuffer == NULL ||
 254              pb->bf_getsegcount == NULL) {
 255                 PyErr_SetString(PyExc_TypeError,
 256                                 "expected a character buffer object");
 257                 return -1;
 258         }
 259         if ((*pb->bf_getsegcount)(obj,NULL) != 1) {
 260                 PyErr_SetString(PyExc_TypeError,
 261                                 "expected a single-segment buffer object");
 262                 return -1;
 263         }
 264         len = (*pb->bf_getcharbuffer)(obj, 0, &pp);
 265         if (len < 0)
 266                 return -1;
 267         *buffer = pp;
 268         *buffer_len = len;
 269         return 0;
 270 }
 271
 272 int
 273 PyObject_CheckReadBuffer(PyObject *obj)
 274 {
 275         PyBufferProcs *pb = obj->ob_type->tp_as_buffer;
 276
 277         if (pb == NULL ||
 278             pb->bf_getreadbuffer == NULL ||
 279             pb->bf_getsegcount == NULL ||
 280             (*pb->bf_getsegcount)(obj, NULL) != 1)
 281                 return 0;
 282         return 1;
 283 }
 284
 285 int PyObject_AsReadBuffer(PyObject *obj,
 286                           const void **buffer,
 287                           Py_ssize_t *buffer_len)
 288 {
 289         PyBufferProcs *pb;
 290         void *pp;
 291         Py_ssize_t len;
 292
 293         if (obj == NULL || buffer == NULL || buffer_len == NULL) {
 294                 null_error();
 295                 return -1;
 296         }
 297         pb = obj->ob_type->tp_as_buffer;
 298         if (pb == NULL ||
 299              pb->bf_getreadbuffer == NULL ||
 300              pb->bf_getsegcount == NULL) {
 301                 PyErr_SetString(PyExc_TypeError,
 302                                 "expected a readable buffer object");
 303                 return -1;
 304         }
 305         if ((*pb->bf_getsegcount)(obj, NULL) != 1) {
 306                 PyErr_SetString(PyExc_TypeError,
 307                                 "expected a single-segment buffer object");
 308                 return -1;
 309         }
 310         len = (*pb->bf_getreadbuffer)(obj, 0, &pp);
 311         if (len < 0)
 312                 return -1;
 313         *buffer = pp;
 314         *buffer_len = len;
 315         return 0;
 316 }
 317
 318 int PyObject_AsWriteBuffer(PyObject *obj,
 319                            void **buffer,
 320                            Py_ssize_t *buffer_len)
 321 {
 322         PyBufferProcs *pb;
 323         void*pp;
 324         Py_ssize_t len;
 325
 326         if (obj == NULL || buffer == NULL || buffer_len == NULL) {
 327                 null_error();
 328                 return -1;
 329         }
 330         pb = obj->ob_type->tp_as_buffer;
 331         if (pb == NULL ||
 332              pb->bf_getwritebuffer == NULL ||
 333              pb->bf_getsegcount == NULL) {
 334                 PyErr_SetString(PyExc_TypeError,
 335                                 "expected a writeable buffer object");
 336                 return -1;
 337         }
 338         if ((*pb->bf_getsegcount)(obj, NULL) != 1) {
 339                 PyErr_SetString(PyExc_TypeError,
 340                                 "expected a single-segment buffer object");
 341                 return -1;
 342         }
 343         len = (*pb->bf_getwritebuffer)(obj,0,&pp);
 344         if (len < 0)
 345                 return -1;
 346         *buffer = pp;
 347         *buffer_len = len;
 348         return 0;
 349 }
 350
 351 /* Buffer C-API for Python 3.0 */
 352
 353 int
 354 PyObject_GetBuffer(PyObject *obj, Py_buffer *view, int flags)
 355 {
 356         if (!PyObject_CheckBuffer(obj)) {
 357                 PyErr_Format(PyExc_TypeError,
 358                              "'%100s' does not have the buffer interface",
 359                              Py_TYPE(obj)->tp_name);
 360                 return -1;
 361         }
 362         return (*(obj->ob_type->tp_as_buffer->bf_getbuffer))(obj, view, flags);
 363 }
 364
 365 void
 366 PyObject_ReleaseBuffer(PyObject *obj, Py_buffer *view)
 367 {
 368         if (obj->ob_type->tp_as_buffer != NULL &&
 369             obj->ob_type->tp_as_buffer->bf_releasebuffer != NULL) {
 370                 (*(obj->ob_type->tp_as_buffer->bf_releasebuffer))(obj, view);
 371         }
 372 }
 373
 374
 375 static int
 376 _IsFortranContiguous(Py_buffer *view)
 377 {
 378         Py_ssize_t sd, dim;
 379         int i;
 380
 381         if (view->ndim == 0) return 1;
 382         if (view->strides == NULL) return (view->ndim == 1);
 383
 384         sd = view->itemsize;
 385         if (view->ndim == 1) return (view->shape[0] == 1 ||
 386                                    sd == view->strides[0]);
 387         for (i=0; i<view->ndim; i++) {
 388                 dim = view->shape[i];
 389                 if (dim == 0) return 1;
 390                 if (view->strides[i] != sd) return 0;
 391                 sd *= dim;
 392         }
 393         return 1;
 394 }
 395
 396 static int
 397 _IsCContiguous(Py_buffer *view)
 398 {
 399         Py_ssize_t sd, dim;
 400         int i;
 401
 402         if (view->ndim == 0) return 1;
 403         if (view->strides == NULL) return 1;
 404
 405         sd = view->itemsize;
 406         if (view->ndim == 1) return (view->shape[0] == 1 ||
 407                                    sd == view->strides[0]);
 408         for (i=view->ndim-1; i>=0; i--) {
 409                 dim = view->shape[i];
 410                 if (dim == 0) return 1;
 411                 if (view->strides[i] != sd) return 0;
 412                 sd *= dim;
 413         }
 414         return 1;
 415 }
 416
 417 int
 418 PyBuffer_IsContiguous(Py_buffer *view, char fort)
 419 {
 420
 421         if (view->suboffsets != NULL) return 0;
 422
 423         if (fort == 'C')
 424                 return _IsCContiguous(view);
 425         else if (fort == 'F')
 426                 return _IsFortranContiguous(view);
 427         else if (fort == 'A')
 428                 return (_IsCContiguous(view) || _IsFortranContiguous(view));
 429         return 0;
 430 }
 431
 432
 433 void*
 434 PyBuffer_GetPointer(Py_buffer *view, Py_ssize_t *indices)
 435 {
 436         char* pointer;
 437         int i;
 438         pointer = (char *)view->buf;
 439         for (i = 0; i < view->ndim; i++) {
 440                 pointer += view->strides[i]*indices[i];
 441                 if ((view->suboffsets != NULL) && (view->suboffsets[i] >= 0)) {
 442                         pointer = *((char**)pointer) + view->suboffsets[i];
 443                 }
 444         }
 445         return (void*)pointer;
 446 }
 447
 448
 449 static void
 450 _add_one_to_index_F(int nd, Py_ssize_t *index, Py_ssize_t *shape)
 451 {
 452         int k;
 453
 454         for (k=0; k<nd; k++) {
 455                 if (index[k] < shape[k]-1) {
 456                         index[k]++;
 457                         break;
 458                 }
 459                 else {
 460                         index[k] = 0;
 461                 }
 462         }
 463 }
 464
 465 static void
 466 _add_one_to_index_C(int nd, Py_ssize_t *index, Py_ssize_t *shape)
 467 {
 468         int k;
 469
 470         for (k=nd-1; k>=0; k--) {
 471                 if (index[k] < shape[k]-1) {
 472                         index[k]++;
 473                         break;
 474                 }
 475                 else {
 476                         index[k] = 0;
 477                 }
 478         }
 479 }
 480
 481   /* view is not checked for consistency in either of these.  It is
 482      assumed that the size of the buffer is view->len in
 483      view->len / view->itemsize elements.
 484   */
 485
 486 int
 487 PyBuffer_ToContiguous(void *buf, Py_buffer *view, Py_ssize_t len, char fort)
 488 {
 489         int k;
 490         void (*addone)(int, Py_ssize_t *, Py_ssize_t *);
 491         Py_ssize_t *indices, elements;
 492         char *dest, *ptr;
 493
 494         if (len > view->len) {
 495                 len = view->len;
 496         }
 497
 498         if (PyBuffer_IsContiguous(view, fort)) {
 499                 /* simplest copy is all that is needed */
 500                 memcpy(buf, view->buf, len);
 501                 return 0;
 502         }
 503
 504         /* Otherwise a more elaborate scheme is needed */
 505
 506         /* XXX(nnorwitz): need to check for overflow! */
 507         indices = (Py_ssize_t *)PyMem_Malloc(sizeof(Py_ssize_t)*(view->ndim));
 508         if (indices == NULL) {
 509                 PyErr_NoMemory();
 510                 return -1;
 511         }
 512         for (k=0; k<view->ndim;k++) {
 513                 indices[k] = 0;
 514         }
 515
 516         if (fort == 'F') {
 517                 addone = _add_one_to_index_F;
 518         }
 519         else {
 520                 addone = _add_one_to_index_C;
 521         }
 522         dest = buf;
 523         /* XXX : This is not going to be the fastest code in the world
 524                  several optimizations are possible.
 525          */
 526         elements = len / view->itemsize;
 527         while (elements--) {
 528                 addone(view->ndim, indices, view->shape);
 529                 ptr = PyBuffer_GetPointer(view, indices);
 530                 memcpy(dest, ptr, view->itemsize);
 531                 dest += view->itemsize;
 532         }
 533         PyMem_Free(indices);
 534         return 0;
 535 }
 536
 537 int
 538 PyBuffer_FromContiguous(Py_buffer *view, void *buf, Py_ssize_t len, char fort)
 539 {
 540         int k;
 541         void (*addone)(int, Py_ssize_t *, Py_ssize_t *);
 542         Py_ssize_t *indices, elements;
 543         char *src, *ptr;
 544
 545         if (len > view->len) {
 546                 len = view->len;
 547         }
 548
 549         if (PyBuffer_IsContiguous(view, fort)) {
 550                 /* simplest copy is all that is needed */
 551                 memcpy(view->buf, buf, len);
 552                 return 0;
 553         }
 554
 555         /* Otherwise a more elaborate scheme is needed */
 556
 557         /* XXX(nnorwitz): need to check for overflow! */
 558         indices = (Py_ssize_t *)PyMem_Malloc(sizeof(Py_ssize_t)*(view->ndim));
 559         if (indices == NULL) {
 560                 PyErr_NoMemory();
 561                 return -1;
 562         }
 563         for (k=0; k<view->ndim;k++) {
 564                 indices[k] = 0;
 565         }
 566
 567         if (fort == 'F') {
 568                 addone = _add_one_to_index_F;
 569         }
 570         else {
 571                 addone = _add_one_to_index_C;
 572         }
 573         src = buf;
 574         /* XXX : This is not going to be the fastest code in the world
 575                  several optimizations are possible.
 576          */
 577         elements = len / view->itemsize;
 578         while (elements--) {
 579                 addone(view->ndim, indices, view->shape);
 580                 ptr = PyBuffer_GetPointer(view, indices);
 581                 memcpy(ptr, src, view->itemsize);
 582                 src += view->itemsize;
 583         }
 584
 585         PyMem_Free(indices);
 586         return 0;
 587 }
 588
 589 int PyObject_CopyData(PyObject *dest, PyObject *src)
 590 {
 591         Py_buffer view_dest, view_src;
 592         int k;
 593         Py_ssize_t *indices, elements;
 594         char *dptr, *sptr;
 595
 596         if (!PyObject_CheckBuffer(dest) ||
 597             !PyObject_CheckBuffer(src)) {
 598                 PyErr_SetString(PyExc_TypeError,
 599                                 "both destination and source must have the "\
 600                                 "buffer interface");
 601                 return -1;
 602         }
 603
 604         if (PyObject_GetBuffer(dest, &view_dest, PyBUF_FULL) != 0) return -1;
 605         if (PyObject_GetBuffer(src, &view_src, PyBUF_FULL_RO) != 0) {
 606                 PyObject_ReleaseBuffer(dest, &view_dest);
 607                 return -1;
 608         }
 609
 610         if (view_dest.len < view_src.len) {
 611                 PyErr_SetString(PyExc_BufferError,
 612                                 "destination is too small to receive data from source");
 613                 PyObject_ReleaseBuffer(dest, &view_dest);
 614                 PyObject_ReleaseBuffer(src, &view_src);
 615                 return -1;
 616         }
 617
 618         if ((PyBuffer_IsContiguous(&view_dest, 'C') &&
 619              PyBuffer_IsContiguous(&view_src, 'C')) ||
 620             (PyBuffer_IsContiguous(&view_dest, 'F') &&
 621              PyBuffer_IsContiguous(&view_src, 'F'))) {
 622                 /* simplest copy is all that is needed */
 623                 memcpy(view_dest.buf, view_src.buf, view_src.len);
 624                 PyObject_ReleaseBuffer(dest, &view_dest);
 625                 PyObject_ReleaseBuffer(src, &view_src);
 626                 return 0;
 627         }
 628
 629         /* Otherwise a more elaborate copy scheme is needed */
 630
 631         /* XXX(nnorwitz): need to check for overflow! */
 632         indices = (Py_ssize_t *)PyMem_Malloc(sizeof(Py_ssize_t)*view_src.ndim);
 633         if (indices == NULL) {
 634                 PyErr_NoMemory();
 635                 PyObject_ReleaseBuffer(dest, &view_dest);
 636                 PyObject_ReleaseBuffer(src, &view_src);
 637                 return -1;
 638         }
 639         for (k=0; k<view_src.ndim;k++) {
 640                 indices[k] = 0;
 641         }
 642         elements = 1;
 643         for (k=0; k<view_src.ndim; k++) {
 644                 /* XXX(nnorwitz): can this overflow? */
 645                 elements *= view_src.shape[k];
 646         }
 647         while (elements--) {
 648                 _add_one_to_index_C(view_src.ndim, indices, view_src.shape);
 649                 dptr = PyBuffer_GetPointer(&view_dest, indices);
 650                 sptr = PyBuffer_GetPointer(&view_src, indices);
 651                 memcpy(dptr, sptr, view_src.itemsize);
 652         }
 653         PyMem_Free(indices);
 654         PyObject_ReleaseBuffer(dest, &view_dest);
 655         PyObject_ReleaseBuffer(src, &view_src);
 656         return 0;
 657 }
 658
 659 void
 660 PyBuffer_FillContiguousStrides(int nd, Py_ssize_t *shape,
 661                                Py_ssize_t *strides, int itemsize,
 662                                char fort)
 663 {
 664         int k;
 665         Py_ssize_t sd;
 666
 667         sd = itemsize;
 668         if (fort == 'F') {
 669                 for (k=0; k<nd; k++) {
 670                         strides[k] = sd;
 671                         sd *= shape[k];
 672                 }
 673         }
 674         else {
 675                 for (k=nd-1; k>=0; k--) {
 676                         strides[k] = sd;
 677                         sd *= shape[k];
 678                 }
 679         }
 680         return;
 681 }
 682
 683 int
 684 PyBuffer_FillInfo(Py_buffer *view, void *buf, Py_ssize_t len,
 685               int readonly, int flags)
 686 {
 687         if (view == NULL) return 0;
 688         if (((flags & PyBUF_WRITABLE) == PyBUF_WRITABLE) &&
 689             (readonly == 1)) {
 690                 PyErr_SetString(PyExc_BufferError,
 691                                 "Object is not writable.");
 692                 return -1;
 693         }
 694
 695         view->buf = buf;
 696         view->len = len;
 697         view->readonly = readonly;
 698         view->itemsize = 1;
 699         view->format = NULL;
 700         if ((flags & PyBUF_FORMAT) == PyBUF_FORMAT)
 701                 view->format = "B";
 702         view->ndim = 1;
 703         view->shape = NULL;
 704         if ((flags & PyBUF_ND) == PyBUF_ND)
 705                 view->shape = &(view->len);
 706         view->strides = NULL;
 707         if ((flags & PyBUF_STRIDES) == PyBUF_STRIDES)
 708                 view->strides = &(view->itemsize);
 709         view->suboffsets = NULL;
 710         view->internal = NULL;
 711         return 0;
 712 }
 713
 714 PyObject *
 715 PyObject_Format(PyObject* obj, PyObject *format_spec)
 716 {
 717         static PyObject * str__format__ = NULL;
 718         PyObject *empty = NULL;
 719         PyObject *result = NULL;
 720         int spec_is_unicode;
 721         int result_is_unicode;
 722
 723         /* Initialize cached value */
 724         if (str__format__ == NULL) {
 725                 /* Initialize static variable needed by _PyType_Lookup */
 726                 str__format__ = PyString_InternFromString("__format__");
 727                 if (str__format__ == NULL)
 728                         goto done;
 729         }
 730
 731         /* If no format_spec is provided, use an empty string */
 732         if (format_spec == NULL) {
 733                 empty = PyString_FromStringAndSize(NULL, 0);
 734                 format_spec = empty;
 735         }
 736
 737         /* Check the format_spec type, and make sure it's str or unicode */
 738         if (PyUnicode_Check(format_spec))
 739                 spec_is_unicode = 1;
 740         else if (PyString_Check(format_spec))
 741                 spec_is_unicode = 0;
 742         else {
 743                 PyErr_Format(PyExc_TypeError,
 744                              "format expects arg 2 to be string "
 745                              "or unicode, not %.100s", Py_TYPE(format_spec)->tp_name);
 746                 goto done;
 747         }
 748
 749         /* Make sure the type is initialized.  float gets initialized late */
 750         if (Py_TYPE(obj)->tp_dict == NULL)
 751                 if (PyType_Ready(Py_TYPE(obj)) < 0)
 752                         goto done;
 753
 754         /* Check for a __format__ method and call it. */
 755         if (PyInstance_Check(obj)) {
 756                 /* We're an instance of a classic class */
 757                 PyObject *bound_method = PyObject_GetAttr(obj,
 758                                                           str__format__);
 759                 if (bound_method != NULL) {
 760                         result = PyObject_CallFunctionObjArgs(bound_method,
 761                                                               format_spec,
 762                                                               NULL);
 763                         Py_DECREF(bound_method);
 764                 } else {
 765                         PyObject *self_as_str;
 766                         PyObject *format_method;
 767
 768                         PyErr_Clear();
 769                         /* Per the PEP, convert to str (or unicode,
 770                            depending on the type of the format
 771                            specifier).  For new-style classes, this
 772                            logic is done by object.__format__(). */
 773                         if (spec_is_unicode)
 774                                 self_as_str = PyObject_Unicode(obj);
 775                         else
 776                                 self_as_str = PyObject_Str(obj);
 777                         if (self_as_str == NULL)
 778                                 goto done;
 779
 780                         /* Then call str.__format__ on that result */
 781                         format_method = PyObject_GetAttr(self_as_str,
 782                                                          str__format__);
 783                         if (format_method == NULL) {
 784                                 Py_DECREF(self_as_str);
 785                                 goto done;
 786                         }
 787                         result = PyObject_CallFunctionObjArgs(format_method,
 788                                                               format_spec,
 789                                                               NULL);
 790                         Py_DECREF(self_as_str);
 791                         Py_DECREF(format_method);
 792                         if (result == NULL)
 793                                 goto done;
 794                 }
 795         } else {
 796                 /* Not an instance of a classic class, use the code
 797                    from py3k */
 798
 799                 /* Find the (unbound!) __format__ method (a borrowed
 800                    reference) */
 801                 PyObject *method = _PyType_Lookup(Py_TYPE(obj),
 802                                                   str__format__);
 803                 if (method == NULL) {
 804                         PyErr_Format(PyExc_TypeError,
 805                                      "Type %.100s doesn't define __format__",
 806                                      Py_TYPE(obj)->tp_name);
 807                         goto done;
 808                 }
 809                 /* And call it, binding it to the value */
 810                 result = PyObject_CallFunctionObjArgs(method, obj,
 811                                                       format_spec, NULL);
 812         }
 813
 814         if (result == NULL)
 815                 goto done;
 816
 817         /* Check the result type, and make sure it's str or unicode */
 818         if (PyUnicode_Check(result))
 819                 result_is_unicode = 1;
 820         else if (PyString_Check(result))
 821                 result_is_unicode = 0;
 822         else {
 823                 PyErr_Format(PyExc_TypeError,
 824                              "%.100s.__format__ must return string or "
 825                              "unicode, not %.100s", Py_TYPE(obj)->tp_name,
 826                              Py_TYPE(result)->tp_name);
 827                 Py_DECREF(result);
 828                 result = NULL;
 829                 goto done;
 830         }
 831
 832         /* Convert to unicode, if needed.  Required if spec is unicode
 833            and result is str */
 834         if (spec_is_unicode && !result_is_unicode) {
 835                 PyObject *tmp = PyObject_Unicode(result);
 836                 /* This logic works whether or not tmp is NULL */
 837                 Py_DECREF(result);
 838                 result = tmp;
 839         }
 840
 841 done:
 842         Py_XDECREF(empty);
 843         return result;
 844 }
 845
 846 /* Operations on numbers */
 847
 848 int
 849 PyNumber_Check(PyObject *o)
 850 {
 851         return o && o->ob_type->tp_as_number &&
 852                (o->ob_type->tp_as_number->nb_int ||
 853                 o->ob_type->tp_as_number->nb_float);
 854 }
 855
 856 /* Binary operators */
 857
 858 /* New style number protocol support */
 859
 860 #define NB_SLOT(x) offsetof(PyNumberMethods, x)
 861 #define NB_BINOP(nb_methods, slot) \
 862                 (*(binaryfunc*)(& ((char*)nb_methods)[slot]))
 863 #define NB_TERNOP(nb_methods, slot) \
 864                 (*(ternaryfunc*)(& ((char*)nb_methods)[slot]))
 865
 866 /*
 867   Calling scheme used for binary operations:
 868
 869   v     w       Action
 870   -------------------------------------------------------------------
 871   new   new     w.op(v,w)[*], v.op(v,w), w.op(v,w)
 872   new   old     v.op(v,w), coerce(v,w), v.op(v,w)
 873   old   new     w.op(v,w), coerce(v,w), v.op(v,w)
 874   old   old     coerce(v,w), v.op(v,w)
 875
 876   [*] only when v->ob_type != w->ob_type && w->ob_type is a subclass of
 877       v->ob_type
 878
 879   Legend:
 880   -------
 881   * new == new style number
 882   * old == old style number
 883   * Action indicates the order in which operations are tried until either
 884     a valid result is produced or an error occurs.
 885
 886  */
 887
 888 static PyObject *
 889 binary_op1(PyObject *v, PyObject *w, const int op_slot)
 890 {
 891         PyObject *x;
 892         binaryfunc slotv = NULL;
 893         binaryfunc slotw = NULL;
 894
 895         if (v->ob_type->tp_as_number != NULL && NEW_STYLE_NUMBER(v))
 896                 slotv = NB_BINOP(v->ob_type->tp_as_number, op_slot);
 897         if (w->ob_type != v->ob_type &&
 898             w->ob_type->tp_as_number != NULL && NEW_STYLE_NUMBER(w)) {
 899                 slotw = NB_BINOP(w->ob_type->tp_as_number, op_slot);
 900                 if (slotw == slotv)
 901                         slotw = NULL;
 902         }
 903         if (slotv) {
 904                 if (slotw && PyType_IsSubtype(w->ob_type, v->ob_type)) {
 905                         x = slotw(v, w);
 906                         if (x != Py_NotImplemented)
 907                                 return x;
 908                         Py_DECREF(x); /* can't do it */
 909                         slotw = NULL;
 910                 }
 911                 x = slotv(v, w);
 912                 if (x != Py_NotImplemented)
 913                         return x;
 914                 Py_DECREF(x); /* can't do it */
 915         }
 916         if (slotw) {
 917                 x = slotw(v, w);
 918                 if (x != Py_NotImplemented)
 919                         return x;
 920                 Py_DECREF(x); /* can't do it */
 921         }
 922         if (!NEW_STYLE_NUMBER(v) || !NEW_STYLE_NUMBER(w)) {
 923                 int err = PyNumber_CoerceEx(&v, &w);
 924                 if (err < 0) {
 925                         return NULL;
 926                 }
 927                 if (err == 0) {
 928                         PyNumberMethods *mv = v->ob_type->tp_as_number;
 929                         if (mv) {
 930                                 binaryfunc slot;
 931                                 slot = NB_BINOP(mv, op_slot);
 932                                 if (slot) {
 933                                         x = slot(v, w);
 934                                         Py_DECREF(v);
 935                                         Py_DECREF(w);
 936                                         return x;
 937                                 }
 938                         }
 939                         /* CoerceEx incremented the reference counts */
 940                         Py_DECREF(v);
 941                         Py_DECREF(w);
 942                 }
 943         }
 944         Py_INCREF(Py_NotImplemented);
 945         return Py_NotImplemented;
 946 }
 947
 948 static PyObject *
 949 binop_type_error(PyObject *v, PyObject *w, const char *op_name)
 950 {
 951         PyErr_Format(PyExc_TypeError,
 952                      "unsupported operand type(s) for %.100s: "
 953                      "'%.100s' and '%.100s'",
 954                      op_name,
 955                      v->ob_type->tp_name,
 956                      w->ob_type->tp_name);
 957         return NULL;
 958 }
 959
 960 static PyObject *
 961 binary_op(PyObject *v, PyObject *w, const int op_slot, const char *op_name)
 962 {
 963         PyObject *result = binary_op1(v, w, op_slot);
 964         if (result == Py_NotImplemented) {
 965                 Py_DECREF(result);
 966                 return binop_type_error(v, w, op_name);
 967         }
 968         return result;
 969 }
 970
 971
 972 /*
 973   Calling scheme used for ternary operations:
 974
 975   *** In some cases, w.op is called before v.op; see binary_op1. ***
 976
 977   v     w       z       Action
 978   -------------------------------------------------------------------
 979   new   new     new     v.op(v,w,z), w.op(v,w,z), z.op(v,w,z)
 980   new   old     new     v.op(v,w,z), z.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 981   old   new     new     w.op(v,w,z), z.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 982   old   old     new     z.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 983   new   new     old     v.op(v,w,z), w.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 984   new   old     old     v.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 985   old   new     old     w.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 986   old   old     old     coerce(v,w,z), v.op(v,w,z)
 987
 988   Legend:
 989   -------
 990   * new == new style number
 991   * old == old style number
 992   * Action indicates the order in which operations are tried until either
 993     a valid result is produced or an error occurs.
 994   * coerce(v,w,z) actually does: coerce(v,w), coerce(v,z), coerce(w,z) and
 995     only if z != Py_None; if z == Py_None, then it is treated as absent
 996     variable and only coerce(v,w) is tried.
 997
 998  */
 999
1000 static PyObject *
1001 ternary_op(PyObject *v,
1002            PyObject *w,
1003            PyObject *z,
1004            const int op_slot,
1005            const char *op_name)
1006 {
1007         PyNumberMethods *mv, *mw, *mz;
1008         PyObject *x = NULL;
1009         ternaryfunc slotv = NULL;
1010         ternaryfunc slotw = NULL;
1011         ternaryfunc slotz = NULL;
1012
1013         mv = v->ob_type->tp_as_number;
1014         mw = w->ob_type->tp_as_number;
1015         if (mv != NULL && NEW_STYLE_NUMBER(v))
1016                 slotv = NB_TERNOP(mv, op_slot);
1017         if (w->ob_type != v->ob_type &&
1018             mw != NULL && NEW_STYLE_NUMBER(w)) {
1019                 slotw = NB_TERNOP(mw, op_slot);
1020                 if (slotw == slotv)
1021                         slotw = NULL;
1022         }
1023         if (slotv) {
1024                 if (slotw && PyType_IsSubtype(w->ob_type, v->ob_type)) {
1025                         x = slotw(v, w, z);
1026                         if (x != Py_NotImplemented)
1027                                 return x;
1028                         Py_DECREF(x); /* can't do it */
1029                         slotw = NULL;
1030                 }
1031                 x = slotv(v, w, z);
1032                 if (x != Py_NotImplemented)
1033                         return x;
1034                 Py_DECREF(x); /* can't do it */
1035         }
1036         if (slotw) {
1037                 x = slotw(v, w, z);
1038                 if (x != Py_NotImplemented)
1039                         return x;
1040                 Py_DECREF(x); /* can't do it */
1041         }
1042         mz = z->ob_type->tp_as_number;
1043         if (mz != NULL && NEW_STYLE_NUMBER(z)) {
1044                 slotz = NB_TERNOP(mz, op_slot);
1045                 if (slotz == slotv || slotz == slotw)
1046                         slotz = NULL;
1047                 if (slotz) {
1048                         x = slotz(v, w, z);
1049                         if (x != Py_NotImplemented)
1050                                 return x;
1051                         Py_DECREF(x); /* can't do it */
1052                 }
1053         }
1054
1055         if (!NEW_STYLE_NUMBER(v) || !NEW_STYLE_NUMBER(w) ||
1056                         (z != Py_None && !NEW_STYLE_NUMBER(z))) {
1057                 /* we have an old style operand, coerce */
1058                 PyObject *v1, *z1, *w2, *z2;
1059                 int c;
1060
1061                 c = PyNumber_Coerce(&v, &w);
1062                 if (c != 0)
1063                         goto error3;
1064
1065                 /* Special case: if the third argument is None, it is
1066                    treated as absent argument and not coerced. */
1067                 if (z == Py_None) {
1068                         if (v->ob_type->tp_as_number) {
1069                                 slotz = NB_TERNOP(v->ob_type->tp_as_number,
1070                                                   op_slot);
1071                                 if (slotz)
1072                                         x = slotz(v, w, z);
1073                                 else
1074                                         c = -1;
1075                         }
1076                         else
1077                                 c = -1;
1078                         goto error2;
1079                 }
1080                 v1 = v;
1081                 z1 = z;
1082                 c = PyNumber_Coerce(&v1, &z1);
1083                 if (c != 0)
1084                         goto error2;
1085                 w2 = w;
1086                 z2 = z1;
1087                 c = PyNumber_Coerce(&w2, &z2);
1088                 if (c != 0)
1089                         goto error1;
1090
1091                 if (v1->ob_type->tp_as_number != NULL) {
1092                         slotv = NB_TERNOP(v1->ob_type->tp_as_number,
1093                                           op_slot);
1094                         if (slotv)
1095                                 x = slotv(v1, w2, z2);
1096                         else
1097                                 c = -1;
1098                 }
1099                 else
1100                         c = -1;
1101
1102                 Py_DECREF(w2);
1103                 Py_DECREF(z2);
1104         error1:
1105                 Py_DECREF(v1);
1106                 Py_DECREF(z1);
1107         error2:
1108                 Py_DECREF(v);
1109                 Py_DECREF(w);
1110         error3:
1111                 if (c >= 0)
1112                         return x;
1113         }
1114
1115         if (z == Py_None)
1116                 PyErr_Format(
1117                         PyExc_TypeError,
1118                         "unsupported operand type(s) for ** or pow(): "
1119                         "'%.100s' and '%.100s'",
1120                         v->ob_type->tp_name,
1121                         w->ob_type->tp_name);
1122         else
1123                 PyErr_Format(
1124                         PyExc_TypeError,
1125                         "unsupported operand type(s) for pow(): "
1126                         "'%.100s', '%.100s', '%.100s'",
1127                         v->ob_type->tp_name,
1128                         w->ob_type->tp_name,
1129                         z->ob_type->tp_name);
1130         return NULL;
1131 }
1132
1133 #define BINARY_FUNC(func, op, op_name) \
1134     PyObject * \
1135     func(PyObject *v, PyObject *w) { \
1136             return binary_op(v, w, NB_SLOT(op), op_name); \
1137     }
1138
1139 BINARY_FUNC(PyNumber_Or, nb_or, "|")
1140 BINARY_FUNC(PyNumber_Xor, nb_xor, "^")
1141 BINARY_FUNC(PyNumber_And, nb_and, "&")
1142 BINARY_FUNC(PyNumber_Lshift, nb_lshift, "<<")
1143 BINARY_FUNC(PyNumber_Rshift, nb_rshift, ">>")
1144 BINARY_FUNC(PyNumber_Subtract, nb_subtract, "-")
1145 BINARY_FUNC(PyNumber_Divide, nb_divide, "/")
1146 BINARY_FUNC(PyNumber_Divmod, nb_divmod, "divmod()")
1147
1148 PyObject *
1149 PyNumber_Add(PyObject *v, PyObject *w)
1150 {
1151         PyObject *result = binary_op1(v, w, NB_SLOT(nb_add));
1152         if (result == Py_NotImplemented) {
1153                 PySequenceMethods *m = v->ob_type->tp_as_sequence;
1154                 Py_DECREF(result);
1155                 if (m && m->sq_concat) {
1156                         return (*m->sq_concat)(v, w);
1157                 }
1158                 result = binop_type_error(v, w, "+");
1159         }
1160         return result;
1161 }
1162
1163 static PyObject *
1164 sequence_repeat(ssizeargfunc repeatfunc, PyObject *seq, PyObject *n)
1165 {
1166         Py_ssize_t count;
1167         if (PyIndex_Check(n)) {
1168                 count = PyNumber_AsSsize_t(n, PyExc_OverflowError);
1169                 if (count == -1 && PyErr_Occurred())
1170                         return NULL;
1171         }
1172         else {
1173                 return type_error("can't multiply sequence by "
1174                                   "non-int of type '%.200s'", n);
1175         }
1176         return (*repeatfunc)(seq, count);
1177 }
1178
1179 PyObject *
1180 PyNumber_Multiply(PyObject *v, PyObject *w)
1181 {
1182         PyObject *result = binary_op1(v, w, NB_SLOT(nb_multiply));
1183         if (result == Py_NotImplemented) {
1184                 PySequenceMethods *mv = v->ob_type->tp_as_sequence;
1185                 PySequenceMethods *mw = w->ob_type->tp_as_sequence;
1186                 Py_DECREF(result);
1187                 if  (mv && mv->sq_repeat) {
1188                         return sequence_repeat(mv->sq_repeat, v, w);
1189                 }
1190                 else if (mw && mw->sq_repeat) {
1191                         return sequence_repeat(mw->sq_repeat, w, v);
1192                 }
1193                 result = binop_type_error(v, w, "*");
1194         }
1195         return result;
1196 }
1197
1198 PyObject *
1199 PyNumber_FloorDivide(PyObject *v, PyObject *w)
1200 {
1201         /* XXX tp_flags test */
1202         return binary_op(v, w, NB_SLOT(nb_floor_divide), "//");
1203 }
1204
1205 PyObject *
1206 PyNumber_TrueDivide(PyObject *v, PyObject *w)
1207 {
1208         /* XXX tp_flags test */
1209         return binary_op(v, w, NB_SLOT(nb_true_divide), "/");
1210 }
1211
1212 PyObject *
1213 PyNumber_Remainder(PyObject *v, PyObject *w)
1214 {
1215         return binary_op(v, w, NB_SLOT(nb_remainder), "%");
1216 }
1217
1218 PyObject *
1219 PyNumber_Power(PyObject *v, PyObject *w, PyObject *z)
1220 {
1221         return ternary_op(v, w, z, NB_SLOT(nb_power), "** or pow()");
1222 }
1223
1224 /* Binary in-place operators */
1225
1226 /* The in-place operators are defined to fall back to the 'normal',
1227    non in-place operations, if the in-place methods are not in place.
1228
1229    - If the left hand object has the appropriate struct members, and
1230      they are filled, call the appropriate function and return the
1231      result.  No coercion is done on the arguments; the left-hand object
1232      is the one the operation is performed on, and it's up to the
1233      function to deal with the right-hand object.
1234
1235    - Otherwise, in-place modification is not supported. Handle it exactly as
1236      a non in-place operation of the same kind.
1237
1238    */
1239
1240 #define HASINPLACE(t) \
1241         PyType_HasFeature((t)->ob_type, Py_TPFLAGS_HAVE_INPLACEOPS)
1242
1243 static PyObject *
1244 binary_iop1(PyObject *v, PyObject *w, const int iop_slot, const int op_slot)
1245 {
1246         PyNumberMethods *mv = v->ob_type->tp_as_number;
1247         if (mv != NULL && HASINPLACE(v)) {
1248                 binaryfunc slot = NB_BINOP(mv, iop_slot);
1249                 if (slot) {
1250                         PyObject *x = (slot)(v, w);
1251                         if (x != Py_NotImplemented) {
1252                                 return x;
1253                         }
1254                         Py_DECREF(x);
1255                 }
1256         }
1257         return binary_op1(v, w, op_slot);
1258 }
1259
1260 static PyObject *
1261 binary_iop(PyObject *v, PyObject *w, const int iop_slot, const int op_slot,
1262                 const char *op_name)
1263 {
1264         PyObject *result = binary_iop1(v, w, iop_slot, op_slot);
1265         if (result == Py_NotImplemented) {
1266                 Py_DECREF(result);
1267                 return binop_type_error(v, w, op_name);
1268         }
1269         return result;
1270 }
1271
1272 #define INPLACE_BINOP(func, iop, op, op_name) \
1273         PyObject * \
1274         func(PyObject *v, PyObject *w) { \
1275                 return binary_iop(v, w, NB_SLOT(iop), NB_SLOT(op), op_name); \
1276         }
1277
1278 INPLACE_BINOP(PyNumber_InPlaceOr, nb_inplace_or, nb_or, "|=")
1279 INPLACE_BINOP(PyNumber_InPlaceXor, nb_inplace_xor, nb_xor, "^=")
1280 INPLACE_BINOP(PyNumber_InPlaceAnd, nb_inplace_and, nb_and, "&=")
1281 INPLACE_BINOP(PyNumber_InPlaceLshift, nb_inplace_lshift, nb_lshift, "<<=")
1282 INPLACE_BINOP(PyNumber_InPlaceRshift, nb_inplace_rshift, nb_rshift, ">>=")
1283 INPLACE_BINOP(PyNumber_InPlaceSubtract, nb_inplace_subtract, nb_subtract, "-=")
1284 INPLACE_BINOP(PyNumber_InPlaceDivide, nb_inplace_divide, nb_divide, "/=")
1285
1286 PyObject *
1287 PyNumber_InPlaceFloorDivide(PyObject *v, PyObject *w)
1288 {
1289         /* XXX tp_flags test */
1290         return binary_iop(v, w, NB_SLOT(nb_inplace_floor_divide),
1291                           NB_SLOT(nb_floor_divide), "//=");
1292 }
1293
1294 PyObject *
1295 PyNumber_InPlaceTrueDivide(PyObject *v, PyObject *w)
1296 {
1297         /* XXX tp_flags test */
1298         return binary_iop(v, w, NB_SLOT(nb_inplace_true_divide),
1299                           NB_SLOT(nb_true_divide), "/=");
1300 }
1301
1302 PyObject *
1303 PyNumber_InPlaceAdd(PyObject *v, PyObject *w)
1304 {
1305         PyObject *result = binary_iop1(v, w, NB_SLOT(nb_inplace_add),
1306                                        NB_SLOT(nb_add));
1307         if (result == Py_NotImplemented) {
1308                 PySequenceMethods *m = v->ob_type->tp_as_sequence;
1309                 Py_DECREF(result);
1310                 if (m != NULL) {
1311                         binaryfunc f = NULL;
1312                         if (HASINPLACE(v))
1313                                 f = m->sq_inplace_concat;
1314                         if (f == NULL)
1315                                 f = m->sq_concat;
1316                         if (f != NULL)
1317                                 return (*f)(v, w);
1318                 }
1319                 result = binop_type_error(v, w, "+=");
1320         }
1321         return result;
1322 }
1323
1324 PyObject *
1325 PyNumber_InPlaceMultiply(PyObject *v, PyObject *w)
1326 {
1327         PyObject *result = binary_iop1(v, w, NB_SLOT(nb_inplace_multiply),
1328                                        NB_SLOT(nb_multiply));
1329         if (result == Py_NotImplemented) {
1330                 ssizeargfunc f = NULL;
1331                 PySequenceMethods *mv = v->ob_type->tp_as_sequence;
1332                 PySequenceMethods *mw = w->ob_type->tp_as_sequence;
1333                 Py_DECREF(result);
1334                 if (mv != NULL) {
1335                         if (HASINPLACE(v))
1336                                 f = mv->sq_inplace_repeat;
1337                         if (f == NULL)
1338                                 f = mv->sq_repeat;
1339                         if (f != NULL)
1340                                 return sequence_repeat(f, v, w);
1341                 }
1342                 else if (mw != NULL) {
1343                         /* Note that the right hand operand should not be
1344                          * mutated in this case so sq_inplace_repeat is not
1345                          * used. */
1346                         if (mw->sq_repeat)
1347                                 return sequence_repeat(mw->sq_repeat, w, v);
1348                 }
1349                 result = binop_type_error(v, w, "*=");
1350         }
1351         return result;
1352 }
1353
1354 PyObject *
1355 PyNumber_InPlaceRemainder(PyObject *v, PyObject *w)
1356 {
1357         return binary_iop(v, w, NB_SLOT(nb_inplace_remainder),
1358                                 NB_SLOT(nb_remainder), "%=");
1359 }
1360
1361 PyObject *
1362 PyNumber_InPlacePower(PyObject *v, PyObject *w, PyObject *z)
1363 {
1364         if (HASINPLACE(v) && v->ob_type->tp_as_number &&
1365             v->ob_type->tp_as_number->nb_inplace_power != NULL) {
1366                 return ternary_op(v, w, z, NB_SLOT(nb_inplace_power), "**=");
1367         }
1368         else {
1369                 return ternary_op(v, w, z, NB_SLOT(nb_power), "**=");
1370         }
1371 }
1372
1373
1374 /* Unary operators and functions */
1375
1376 PyObject *
1377 PyNumber_Negative(PyObject *o)
1378 {
1379         PyNumberMethods *m;
1380
1381         if (o == NULL)
1382                 return null_error();
1383         m = o->ob_type->tp_as_number;
1384         if (m && m->nb_negative)
1385                 return (*m->nb_negative)(o);
1386
1387         return type_error("bad operand type for unary -: '%.200s'", o);
1388 }
1389
1390 PyObject *
1391 PyNumber_Positive(PyObject *o)
1392 {
1393         PyNumberMethods *m;
1394
1395         if (o == NULL)
1396                 return null_error();
1397         m = o->ob_type->tp_as_number;
1398         if (m && m->nb_positive)
1399                 return (*m->nb_positive)(o);
1400
1401         return type_error("bad operand type for unary +: '%.200s'", o);
1402 }
1403
1404 PyObject *
1405 PyNumber_Invert(PyObject *o)
1406 {
1407         PyNumberMethods *m;
1408
1409         if (o == NULL)
1410                 return null_error();
1411         m = o->ob_type->tp_as_number;
1412         if (m && m->nb_invert)
1413                 return (*m->nb_invert)(o);
1414
1415         return type_error("bad operand type for unary ~: '%.200s'", o);
1416 }
1417
1418 PyObject *
1419 PyNumber_Absolute(PyObject *o)
1420 {
1421         PyNumberMethods *m;
1422
1423         if (o == NULL)
1424                 return null_error();
1425         m = o->ob_type->tp_as_number;
1426         if (m && m->nb_absolute)
1427                 return m->nb_absolute(o);
1428
1429         return type_error("bad operand type for abs(): '%.200s'", o);
1430 }
1431
1432 /* Add a check for embedded NULL-bytes in the argument. */
1433 static PyObject *
1434 int_from_string(const char *s, Py_ssize_t len)
1435 {
1436         char *end;
1437         PyObject *x;
1438
1439         x = PyInt_FromString((char*)s, &end, 10);
1440         if (x == NULL)
1441                 return NULL;
1442         if (end != s + len) {
1443                 PyErr_SetString(PyExc_ValueError,
1444                                 "null byte in argument for int()");
1445                 Py_DECREF(x);
1446                 return NULL;
1447         }
1448         return x;
1449 }
1450
1451 /* Return a Python Int or Long from the object item
1452    Raise TypeError if the result is not an int-or-long
1453    or if the object cannot be interpreted as an index.
1454 */
1455 PyObject *
1456 PyNumber_Index(PyObject *item)
1457 {
1458         PyObject *result = NULL;
1459         if (item == NULL)
1460                 return null_error();
1461         if (PyInt_Check(item) || PyLong_Check(item)) {
1462                 Py_INCREF(item);
1463                 return item;
1464         }
1465         if (PyIndex_Check(item)) {
1466                 result = item->ob_type->tp_as_number->nb_index(item);
1467                 if (result &&
1468                     !PyInt_Check(result) && !PyLong_Check(result)) {
1469                         PyErr_Format(PyExc_TypeError,
1470                                      "__index__ returned non-(int,long) " \
1471                                      "(type %.200s)",
1472                                      result->ob_type->tp_name);
1473                         Py_DECREF(result);
1474                         return NULL;
1475                 }
1476         }
1477         else {
1478                 PyErr_Format(PyExc_TypeError,
1479                              "'%.200s' object cannot be interpreted "
1480                              "as an index", item->ob_type->tp_name);
1481         }
1482         return result;
1483 }
1484
1485 /* Return an error on Overflow only if err is not NULL*/
1486
1487 Py_ssize_t
1488 PyNumber_AsSsize_t(PyObject *item, PyObject *err)
1489 {
1490         Py_ssize_t result;
1491         PyObject *runerr;
1492         PyObject *value = PyNumber_Index(item);
1493         if (value == NULL)
1494                 return -1;
1495
1496         /* We're done if PyInt_AsSsize_t() returns without error. */
1497         result = PyInt_AsSsize_t(value);
1498         if (result != -1 || !(runerr = PyErr_Occurred()))
1499                 goto finish;
1500
1501         /* Error handling code -- only manage OverflowError differently */
1502         if (!PyErr_GivenExceptionMatches(runerr, PyExc_OverflowError))
1503                 goto finish;
1504
1505         PyErr_Clear();
1506         /* If no error-handling desired then the default clipping
1507            is sufficient.
1508          */
1509         if (!err) {
1510                 assert(PyLong_Check(value));
1511                 /* Whether or not it is less than or equal to
1512                    zero is determined by the sign of ob_size
1513                 */
1514                 if (_PyLong_Sign(value) < 0)
1515                         result = PY_SSIZE_T_MIN;
1516                 else
1517                         result = PY_SSIZE_T_MAX;
1518         }
1519         else {
1520                 /* Otherwise replace the error with caller's error object. */
1521                 PyErr_Format(err,
1522                              "cannot fit '%.200s' into an index-sized integer",
1523                              item->ob_type->tp_name);
1524         }
1525
1526  finish:
1527         Py_DECREF(value);
1528         return result;
1529 }
1530
1531
1532 PyObject *
1533 _PyNumber_ConvertIntegralToInt(PyObject *integral, const char* error_format)
1534 {
1535         const char *type_name;
1536         static PyObject *int_name = NULL;
1537         if (int_name == NULL) {
1538                 int_name = PyString_InternFromString("__int__");
1539                 if (int_name == NULL)
1540                         return NULL;
1541         }
1542
1543         if (integral && (!PyInt_Check(integral) &&
1544                          !PyLong_Check(integral))) {
1545                 /* Don't go through tp_as_number->nb_int to avoid
1546                    hitting the classic class fallback to __trunc__. */
1547                 PyObject *int_func = PyObject_GetAttr(integral, int_name);
1548                 if (int_func == NULL) {
1549                         PyErr_Clear(); /* Raise a different error. */
1550                         goto non_integral_error;
1551                 }
1552                 Py_DECREF(integral);
1553                 integral = PyEval_CallObject(int_func, NULL);
1554                 Py_DECREF(int_func);
1555                 if (integral && (!PyInt_Check(integral) &&
1556                                   !PyLong_Check(integral))) {
1557                         goto non_integral_error;
1558                 }
1559         }
1560         return integral;
1561
1562 non_integral_error:
1563         if (PyInstance_Check(integral)) {
1564                 type_name = PyString_AS_STRING(((PyInstanceObject *)integral)
1565                                                ->in_class->cl_name);
1566         }
1567         else {
1568                 type_name = integral->ob_type->tp_name;
1569         }
1570         PyErr_Format(PyExc_TypeError, error_format, type_name);
1571         Py_DECREF(integral);
1572         return NULL;
1573 }
1574
1575
1576 PyObject *
1577 PyNumber_Int(PyObject *o)
1578 {
1579         PyNumberMethods *m;
1580         static PyObject *trunc_name = NULL;
1581         PyObject *trunc_func;
1582         const char *buffer;
1583         Py_ssize_t buffer_len;
1584
1585         if (trunc_name == NULL) {
1586                 trunc_name = PyString_InternFromString("__trunc__");
1587                 if (trunc_name == NULL)
1588                         return NULL;
1589         }
1590
1591         if (o == NULL)
1592                 return null_error();
1593         if (PyInt_CheckExact(o)) {
1594                 Py_INCREF(o);
1595                 return o;
1596         }
1597         m = o->ob_type->tp_as_number;
1598         if (m && m->nb_int) { /* This should include subclasses of int */
1599                 /* Classic classes always take this branch. */
1600                 PyObject *res = m->nb_int(o);
1601                 if (res && (!PyInt_Check(res) && !PyLong_Check(res))) {
1602                         PyErr_Format(PyExc_TypeError,
1603                                      "__int__ returned non-int (type %.200s)",
1604                                      res->ob_type->tp_name);
1605                         Py_DECREF(res);
1606                         return NULL;
1607                 }
1608                 return res;
1609         }
1610         if (PyInt_Check(o)) { /* A int subclass without nb_int */
1611                 PyIntObject *io = (PyIntObject*)o;
1612                 return PyInt_FromLong(io->ob_ival);
1613         }
1614         trunc_func = PyObject_GetAttr(o, trunc_name);
1615         if (trunc_func) {
1616                 PyObject *truncated = PyEval_CallObject(trunc_func, NULL);
1617                 Py_DECREF(trunc_func);
1618                 /* __trunc__ is specified to return an Integral type, but
1619                    int() needs to return an int. */
1620                 return _PyNumber_ConvertIntegralToInt(
1621                         truncated,
1622                         "__trunc__ returned non-Integral (type %.200s)");
1623         }
1624         PyErr_Clear();  /* It's not an error if  o.__trunc__ doesn't exist. */
1625
1626         if (PyString_Check(o))
1627                 return int_from_string(PyString_AS_STRING(o),
1628                                        PyString_GET_SIZE(o));
1629 #ifdef Py_USING_UNICODE
1630         if (PyUnicode_Check(o))
1631                 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(o),
1632                                          PyUnicode_GET_SIZE(o),
1633                                          10);
1634 #endif
1635         if (!PyObject_AsCharBuffer(o, &buffer, &buffer_len))
1636                 return int_from_string((char*)buffer, buffer_len);
1637
1638         return type_error("int() argument must be a string or a "
1639                           "number, not '%.200s'", o);
1640 }
1641
1642 /* Add a check for embedded NULL-bytes in the argument. */
1643 static PyObject *
1644 long_from_string(const char *s, Py_ssize_t len)
1645 {
1646         char *end;
1647         PyObject *x;
1648
1649         x = PyLong_FromString((char*)s, &end, 10);
1650         if (x == NULL)
1651                 return NULL;
1652         if (end != s + len) {
1653                 PyErr_SetString(PyExc_ValueError,
1654                                 "null byte in argument for long()");
1655                 Py_DECREF(x);
1656                 return NULL;
1657         }
1658         return x;
1659 }
1660
1661 PyObject *
1662 PyNumber_Long(PyObject *o)
1663 {
1664         PyNumberMethods *m;
1665         static PyObject *trunc_name = NULL;
1666         PyObject *trunc_func;
1667         const char *buffer;
1668         Py_ssize_t buffer_len;
1669
1670         if (trunc_name == NULL) {
1671                 trunc_name = PyString_InternFromString("__trunc__");
1672                 if (trunc_name == NULL)
1673                         return NULL;
1674         }
1675
1676         if (o == NULL)
1677                 return null_error();
1678         m = o->ob_type->tp_as_number;
1679         if (m && m->nb_long) { /* This should include subclasses of long */
1680                 /* Classic classes always take this branch. */
1681                 PyObject *res = m->nb_long(o);
1682                 if (res && (!PyInt_Check(res) && !PyLong_Check(res))) {
1683                         PyErr_Format(PyExc_TypeError,
1684                                      "__long__ returned non-long (type %.200s)",
1685                                      res->ob_type->tp_name);
1686                         Py_DECREF(res);
1687                         return NULL;
1688                 }
1689                 return res;
1690         }
1691         if (PyLong_Check(o)) /* A long subclass without nb_long */
1692                 return _PyLong_Copy((PyLongObject *)o);
1693         trunc_func = PyObject_GetAttr(o, trunc_name);
1694         if (trunc_func) {
1695                 PyObject *truncated = PyEval_CallObject(trunc_func, NULL);
1696                 PyObject *int_instance;
1697                 Py_DECREF(trunc_func);
1698                 /* __trunc__ is specified to return an Integral type,
1699                    but long() needs to return a long. */
1700                 int_instance = _PyNumber_ConvertIntegralToInt(
1701                         truncated,
1702                         "__trunc__ returned non-Integral (type %.200s)");
1703                 if (int_instance && PyInt_Check(int_instance)) {
1704                         /* Make sure that long() returns a long instance. */
1705                         long value = PyInt_AS_LONG(int_instance);
1706                         Py_DECREF(int_instance);
1707                         return PyLong_FromLong(value);
1708                 }
1709                 return int_instance;
1710         }
1711         PyErr_Clear();  /* It's not an error if  o.__trunc__ doesn't exist. */
1712
1713         if (PyString_Check(o))
1714                 /* need to do extra error checking that PyLong_FromString()
1715                  * doesn't do.  In particular long('9.5') must raise an
1716                  * exception, not truncate the float.
1717                  */
1718                 return long_from_string(PyString_AS_STRING(o),
1719                                         PyString_GET_SIZE(o));
1720 #ifdef Py_USING_UNICODE
1721         if (PyUnicode_Check(o))
1722                 /* The above check is done in PyLong_FromUnicode(). */
1723                 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(o),
1724                                           PyUnicode_GET_SIZE(o),
1725                                           10);
1726 #endif
1727         if (!PyObject_AsCharBuffer(o, &buffer, &buffer_len))
1728                 return long_from_string(buffer, buffer_len);
1729
1730         return type_error("long() argument must be a string or a "
1731                           "number, not '%.200s'", o);
1732 }
1733
1734 PyObject *
1735 PyNumber_Float(PyObject *o)
1736 {
1737         PyNumberMethods *m;
1738
1739         if (o == NULL)
1740                 return null_error();
1741         m = o->ob_type->tp_as_number;
1742         if (m && m->nb_float) { /* This should include subclasses of float */
1743                 PyObject *res = m->nb_float(o);
1744                 if (res && !PyFloat_Check(res)) {
1745                         PyErr_Format(PyExc_TypeError,
1746                           "__float__ returned non-float (type %.200s)",
1747                           res->ob_type->tp_name);
1748                         Py_DECREF(res);
1749                         return NULL;
1750                 }
1751                 return res;
1752         }
1753         if (PyFloat_Check(o)) { /* A float subclass with nb_float == NULL */
1754                 PyFloatObject *po = (PyFloatObject *)o;
1755                 return PyFloat_FromDouble(po->ob_fval);
1756         }
1757         return PyFloat_FromString(o, NULL);
1758 }
1759
1760 PyObject *
1761 PyNumber_ToBase(PyObject *n, int base)
1762 {
1763         PyObject *res = NULL;
1764         PyObject *index = PyNumber_Index(n);
1765
1766         if (!index)
1767                 return NULL;
1768         if (PyLong_Check(index))
1769                 res = _PyLong_Format(index, base, 0, 1);
1770         else if (PyInt_Check(index))
1771                 res = _PyInt_Format((PyIntObject*)index, base, 1);
1772         else
1773                 /* It should not be possible to get here, as
1774                    PyNumber_Index already has a check for the same
1775                    condition */
1776                 PyErr_SetString(PyExc_ValueError, "PyNumber_ToBase: index not "
1777                                 "int or long");
1778         Py_DECREF(index);
1779         return res;
1780 }
1781
1782
1783 /* Operations on sequences */
1784
1785 int
1786 PySequence_Check(PyObject *s)
1787 {
1788         if (s && PyInstance_Check(s))
1789                 return PyObject_HasAttrString(s, "__getitem__");
1790         if (PyObject_IsInstance(s, (PyObject *)&PyDict_Type))
1791                 return 0;
1792         return s != NULL && s->ob_type->tp_as_sequence &&
1793                 s->ob_type->tp_as_sequence->sq_item != NULL;
1794 }
1795
1796 Py_ssize_t
1797 PySequence_Size(PyObject *s)
1798 {
1799         PySequenceMethods *m;
1800
1801         if (s == NULL) {
1802                 null_error();
1803                 return -1;
1804         }
1805
1806         m = s->ob_type->tp_as_sequence;
1807         if (m && m->sq_length)
1808                 return m->sq_length(s);
1809
1810         type_error("object of type '%.200s' has no len()", s);
1811         return -1;
1812 }
1813
1814 #undef PySequence_Length
1815 Py_ssize_t
1816 PySequence_Length(PyObject *s)
1817 {
1818         return PySequence_Size(s);
1819 }
1820 #define PySequence_Length PySequence_Size
1821
1822 PyObject *
1823 PySequence_Concat(PyObject *s, PyObject *o)
1824 {
1825         PySequenceMethods *m;
1826
1827         if (s == NULL || o == NULL)
1828                 return null_error();
1829
1830         m = s->ob_type->tp_as_sequence;
1831         if (m && m->sq_concat)
1832                 return m->sq_concat(s, o);
1833
1834         /* Instances of user classes defining an __add__() method only
1835            have an nb_add slot, not an sq_concat slot.  So we fall back
1836            to nb_add if both arguments appear to be sequences. */
1837         if (PySequence_Check(s) && PySequence_Check(o)) {
1838                 PyObject *result = binary_op1(s, o, NB_SLOT(nb_add));
1839                 if (result != Py_NotImplemented)
1840                         return result;
1841                 Py_DECREF(result);
1842         }
1843         return type_error("'%.200s' object can't be concatenated", s);
1844 }
1845
1846 PyObject *
1847 PySequence_Repeat(PyObject *o, Py_ssize_t count)
1848 {
1849         PySequenceMethods *m;
1850
1851         if (o == NULL)
1852                 return null_error();
1853
1854         m = o->ob_type->tp_as_sequence;
1855         if (m && m->sq_repeat)
1856                 return m->sq_repeat(o, count);
1857
1858         /* Instances of user classes defining a __mul__() method only
1859            have an nb_multiply slot, not an sq_repeat slot. so we fall back
1860            to nb_multiply if o appears to be a sequence. */
1861         if (PySequence_Check(o)) {
1862                 PyObject *n, *result;
1863                 n = PyInt_FromSsize_t(count);
1864                 if (n == NULL)
1865                         return NULL;
1866                 result = binary_op1(o, n, NB_SLOT(nb_multiply));
1867                 Py_DECREF(n);
1868                 if (result != Py_NotImplemented)
1869                         return result;
1870                 Py_DECREF(result);
1871         }
1872         return type_error("'%.200s' object can't be repeated", o);
1873 }
1874
1875 PyObject *
1876 PySequence_InPlaceConcat(PyObject *s, PyObject *o)
1877 {
1878         PySequenceMethods *m;
1879
1880         if (s == NULL || o == NULL)
1881                 return null_error();
1882
1883         m = s->ob_type->tp_as_sequence;
1884         if (m && HASINPLACE(s) && m->sq_inplace_concat)
1885                 return m->sq_inplace_concat(s, o);
1886         if (m && m->sq_concat)
1887                 return m->sq_concat(s, o);
1888
1889         if (PySequence_Check(s) && PySequence_Check(o)) {
1890                 PyObject *result = binary_iop1(s, o, NB_SLOT(nb_inplace_add),
1891                                                NB_SLOT(nb_add));
1892                 if (result != Py_NotImplemented)
1893                         return result;
1894                 Py_DECREF(result);
1895         }
1896         return type_error("'%.200s' object can't be concatenated", s);
1897 }
1898
1899 PyObject *
1900 PySequence_InPlaceRepeat(PyObject *o, Py_ssize_t count)
1901 {
1902         PySequenceMethods *m;
1903
1904         if (o == NULL)
1905                 return null_error();
1906
1907         m = o->ob_type->tp_as_sequence;
1908         if (m && HASINPLACE(o) && m->sq_inplace_repeat)
1909                 return m->sq_inplace_repeat(o, count);
1910         if (m && m->sq_repeat)
1911                 return m->sq_repeat(o, count);
1912
1913         if (PySequence_Check(o)) {
1914                 PyObject *n, *result;
1915                 n = PyInt_FromSsize_t(count);
1916                 if (n == NULL)
1917                         return NULL;
1918                 result = binary_iop1(o, n, NB_SLOT(nb_inplace_multiply),
1919                                      NB_SLOT(nb_multiply));
1920                 Py_DECREF(n);
1921                 if (result != Py_NotImplemented)
1922                         return result;
1923                 Py_DECREF(result);
1924         }
1925         return type_error("'%.200s' object can't be repeated", o);
1926 }
1927
1928 PyObject *
1929 PySequence_GetItem(PyObject *s, Py_ssize_t i)
1930 {
1931         PySequenceMethods *m;
1932
1933         if (s == NULL)
1934                 return null_error();
1935
1936         m = s->ob_type->tp_as_sequence;
1937         if (m && m->sq_item) {
1938                 if (i < 0) {
1939                         if (m->sq_length) {
1940                                 Py_ssize_t l = (*m->sq_length)(s);
1941                                 if (l < 0)
1942                                         return NULL;
1943                                 i += l;
1944                         }
1945                 }
1946                 return m->sq_item(s, i);
1947         }
1948
1949         return type_error("'%.200s' object is unindexable", s);
1950 }
1951
1952 PyObject *
1953 PySequence_GetSlice(PyObject *s, Py_ssize_t i1, Py_ssize_t i2)
1954 {
1955         PySequenceMethods *m;
1956         PyMappingMethods *mp;
1957
1958         if (!s) return null_error();
1959
1960         m = s->ob_type->tp_as_sequence;
1961         if (m && m->sq_slice) {
1962                 if (i1 < 0 || i2 < 0) {
1963                         if (m->sq_length) {
1964                                 Py_ssize_t l = (*m->sq_length)(s);
1965                                 if (l < 0)
1966                                         return NULL;
1967                                 if (i1 < 0)
1968                                         i1 += l;
1969                                 if (i2 < 0)
1970                                         i2 += l;
1971                         }
1972                 }
1973                 return m->sq_slice(s, i1, i2);
1974         } else if ((mp = s->ob_type->tp_as_mapping) && mp->mp_subscript) {
1975                 PyObject *res;
1976                 PyObject *slice = _PySlice_FromIndices(i1, i2);
1977                 if (!slice)
1978                         return NULL;
1979                 res = mp->mp_subscript(s, slice);
1980                 Py_DECREF(slice);
1981                 return res;
1982         }
1983
1984         return type_error("'%.200s' object is unsliceable", s);
1985 }
1986
1987 int
1988 PySequence_SetItem(PyObject *s, Py_ssize_t i, PyObject *o)
1989 {
1990         PySequenceMethods *m;
1991
1992         if (s == NULL) {
1993                 null_error();
1994                 return -1;
1995         }
1996
1997         m = s->ob_type->tp_as_sequence;
1998         if (m && m->sq_ass_item) {
1999                 if (i < 0) {
2000                         if (m->sq_length) {
2001                                 Py_ssize_t l = (*m->sq_length)(s);
2002                                 if (l < 0)
2003                                         return -1;
2004                                 i += l;
2005                         }
2006                 }
2007                 return m->sq_ass_item(s, i, o);
2008         }
2009
2010         type_error("'%.200s' object does not support item assignment", s);
2011         return -1;
2012 }
2013
2014 int
2015 PySequence_DelItem(PyObject *s, Py_ssize_t i)
2016 {
2017         PySequenceMethods *m;
2018
2019         if (s == NULL) {
2020                 null_error();
2021                 return -1;
2022         }
2023
2024         m = s->ob_type->tp_as_sequence;
2025         if (m && m->sq_ass_item) {
2026                 if (i < 0) {
2027                         if (m->sq_length) {
2028                                 Py_ssize_t l = (*m->sq_length)(s);
2029                                 if (l < 0)
2030                                         return -1;
2031                                 i += l;
2032                         }
2033                 }
2034                 return m->sq_ass_item(s, i, (PyObject *)NULL);
2035         }
2036
2037         type_error("'%.200s' object doesn't support item deletion", s);
2038         return -1;
2039 }
2040
2041 int
2042 PySequence_SetSlice(PyObject *s, Py_ssize_t i1, Py_ssize_t i2, PyObject *o)
2043 {
2044         PySequenceMethods *m;
2045         PyMappingMethods *mp;
2046
2047         if (s == NULL) {
2048                 null_error();
2049                 return -1;
2050         }
2051
2052         m = s->ob_type->tp_as_sequence;
2053         if (m && m->sq_ass_slice) {
2054                 if (i1 < 0 || i2 < 0) {
2055                         if (m->sq_length) {
2056                                 Py_ssize_t l = (*m->sq_length)(s);
2057                                 if (l < 0)
2058                                         return -1;
2059                                 if (i1 < 0)
2060                                         i1 += l;
2061                                 if (i2 < 0)
2062                                         i2 += l;
2063                         }
2064                 }
2065                 return m->sq_ass_slice(s, i1, i2, o);
2066         } else if ((mp = s->ob_type->tp_as_mapping) && mp->mp_ass_subscript) {
2067                 int res;
2068                 PyObject *slice = _PySlice_FromIndices(i1, i2);
2069                 if (!slice)
2070                         return -1;
2071                 res = mp->mp_ass_subscript(s, slice, o);
2072                 Py_DECREF(slice);
2073                 return res;
2074         }
2075
2076         type_error("'%.200s' object doesn't support slice assignment", s);
2077         return -1;
2078 }
2079
2080 int
2081 PySequence_DelSlice(PyObject *s, Py_ssize_t i1, Py_ssize_t i2)
2082 {
2083         PySequenceMethods *m;
2084
2085         if (s == NULL) {
2086                 null_error();
2087                 return -1;
2088         }
2089
2090         m = s->ob_type->tp_as_sequence;
2091         if (m && m->sq_ass_slice) {
2092                 if (i1 < 0 || i2 < 0) {
2093                         if (m->sq_length) {
2094                                 Py_ssize_t l = (*m->sq_length)(s);
2095                                 if (l < 0)
2096                                         return -1;
2097                                 if (i1 < 0)
2098                                         i1 += l;
2099                                 if (i2 < 0)
2100                                         i2 += l;
2101                         }
2102                 }
2103                 return m->sq_ass_slice(s, i1, i2, (PyObject *)NULL);
2104         }
2105         type_error("'%.200s' object doesn't support slice deletion", s);
2106         return -1;
2107 }
2108
2109 PyObject *
2110 PySequence_Tuple(PyObject *v)
2111 {
2112         PyObject *it;  /* iter(v) */
2113         Py_ssize_t n;         /* guess for result tuple size */
2114         PyObject *result;
2115         Py_ssize_t j;
2116
2117         if (v == NULL)
2118                 return null_error();
2119
2120         /* Special-case the common tuple and list cases, for efficiency. */
2121         if (PyTuple_CheckExact(v)) {
2122                 /* Note that we can't know whether it's safe to return
2123                    a tuple *subclass* instance as-is, hence the restriction
2124                    to exact tuples here.  In contrast, lists always make
2125                    a copy, so there's no need for exactness below. */
2126                 Py_INCREF(v);
2127                 return v;
2128         }
2129         if (PyList_Check(v))
2130                 return PyList_AsTuple(v);
2131
2132         /* Get iterator. */
2133         it = PyObject_GetIter(v);
2134         if (it == NULL)
2135                 return NULL;
2136
2137         /* Guess result size and allocate space. */
2138         n = _PyObject_LengthHint(v, 10);
2139         result = PyTuple_New(n);
2140         if (result == NULL)
2141                 goto Fail;
2142
2143         /* Fill the tuple. */
2144         for (j = 0; ; ++j) {
2145                 PyObject *item = PyIter_Next(it);
2146                 if (item == NULL) {
2147                         if (PyErr_Occurred())
2148                                 goto Fail;
2149                         break;
2150                 }
2151                 if (j >= n) {
2152                         Py_ssize_t oldn = n;
2153                         /* The over-allocation strategy can grow a bit faster
2154                            than for lists because unlike lists the
2155                            over-allocation isn't permanent -- we reclaim
2156                            the excess before the end of this routine.
2157                            So, grow by ten and then add 25%.
2158                         */
2159                         n += 10;
2160                         n += n >> 2;
2161                         if (n < oldn) {
2162                                 /* Check for overflow */
2163                                 PyErr_NoMemory();
2164                                 Py_DECREF(item);
2165                                 goto Fail;
2166                         }
2167                         if (_PyTuple_Resize(&result, n) != 0) {
2168                                 Py_DECREF(item);
2169                                 goto Fail;
2170                         }
2171                 }
2172                 PyTuple_SET_ITEM(result, j, item);
2173         }
2174
2175         /* Cut tuple back if guess was too large. */
2176         if (j < n &&
2177             _PyTuple_Resize(&result, j) != 0)
2178                 goto Fail;
2179
2180         Py_DECREF(it);
2181         return result;
2182
2183 Fail:
2184         Py_XDECREF(result);
2185         Py_DECREF(it);
2186         return NULL;
2187 }
2188
2189 PyObject *
2190 PySequence_List(PyObject *v)
2191 {
2192         PyObject *result;  /* result list */
2193         PyObject *rv;      /* return value from PyList_Extend */
2194
2195         if (v == NULL)
2196                 return null_error();
2197
2198         result = PyList_New(0);
2199         if (result == NULL)
2200                 return NULL;
2201
2202         rv = _PyList_Extend((PyListObject *)result, v);
2203         if (rv == NULL) {
2204                 Py_DECREF(result);
2205                 return NULL;
2206         }
2207         Py_DECREF(rv);
2208         return result;
2209 }
2210
2211 PyObject *
2212 PySequence_Fast(PyObject *v, const char *m)
2213 {
2214         PyObject *it;
2215
2216         if (v == NULL)
2217                 return null_error();
2218
2219         if (PyList_CheckExact(v) || PyTuple_CheckExact(v)) {
2220                 Py_INCREF(v);
2221                 return v;
2222         }
2223
2224         it = PyObject_GetIter(v);
2225         if (it == NULL) {
2226                 if (PyErr_ExceptionMatches(PyExc_TypeError))
2227                         PyErr_SetString(PyExc_TypeError, m);
2228                 return NULL;
2229         }
2230
2231         v = PySequence_List(it);
2232         Py_DECREF(it);
2233
2234         return v;
2235 }
2236
2237 /* Iterate over seq.  Result depends on the operation:
2238    PY_ITERSEARCH_COUNT:  -1 if error, else # of times obj appears in seq.
2239    PY_ITERSEARCH_INDEX:  0-based index of first occurence of obj in seq;
2240         set ValueError and return -1 if none found; also return -1 on error.
2241    Py_ITERSEARCH_CONTAINS:  return 1 if obj in seq, else 0; -1 on error.
2242 */
2243 Py_ssize_t
2244 _PySequence_IterSearch(PyObject *seq, PyObject *obj, int operation)
2245 {
2246         Py_ssize_t n;
2247         int wrapped;  /* for PY_ITERSEARCH_INDEX, true iff n wrapped around */
2248         PyObject *it;  /* iter(seq) */
2249
2250         if (seq == NULL || obj == NULL) {
2251                 null_error();
2252                 return -1;
2253         }
2254
2255         it = PyObject_GetIter(seq);
2256         if (it == NULL) {
2257                 type_error("argument of type '%.200s' is not iterable", seq);
2258                 return -1;
2259         }
2260
2261         n = wrapped = 0;
2262         for (;;) {
2263                 int cmp;
2264                 PyObject *item = PyIter_Next(it);
2265                 if (item == NULL) {
2266                         if (PyErr_Occurred())
2267                                 goto Fail;
2268                         break;
2269                 }
2270
2271                 cmp = PyObject_RichCompareBool(obj, item, Py_EQ);
2272                 Py_DECREF(item);
2273                 if (cmp < 0)
2274                         goto Fail;
2275                 if (cmp > 0) {
2276                         switch (operation) {
2277                         case PY_ITERSEARCH_COUNT:
2278                                 if (n == PY_SSIZE_T_MAX) {
2279                                         PyErr_SetString(PyExc_OverflowError,
2280                                                "count exceeds C integer size");
2281                                         goto Fail;
2282                                 }
2283                                 ++n;
2284                                 break;
2285
2286                         case PY_ITERSEARCH_INDEX:
2287                                 if (wrapped) {
2288                                         PyErr_SetString(PyExc_OverflowError,
2289                                                "index exceeds C integer size");
2290                                         goto Fail;
2291                                 }
2292                                 goto Done;
2293
2294                         case PY_ITERSEARCH_CONTAINS:
2295                                 n = 1;
2296                                 goto Done;
2297
2298                         default:
2299                                 assert(!"unknown operation");
2300                         }
2301                 }
2302
2303                 if (operation == PY_ITERSEARCH_INDEX) {
2304                         if (n == PY_SSIZE_T_MAX)
2305                                 wrapped = 1;
2306                         ++n;
2307                 }
2308         }
2309
2310         if (operation != PY_ITERSEARCH_INDEX)
2311                 goto Done;
2312
2313         PyErr_SetString(PyExc_ValueError,
2314                         "sequence.index(x): x not in sequence");
2315         /* fall into failure code */
2316 Fail:
2317         n = -1;
2318         /* fall through */
2319 Done:
2320         Py_DECREF(it);
2321         return n;
2322
2323 }
2324
2325 /* Return # of times o appears in s. */
2326 Py_ssize_t
2327 PySequence_Count(PyObject *s, PyObject *o)
2328 {
2329         return _PySequence_IterSearch(s, o, PY_ITERSEARCH_COUNT);
2330 }
2331
2332 /* Return -1 if error; 1 if ob in seq; 0 if ob not in seq.
2333  * Use sq_contains if possible, else defer to _PySequence_IterSearch().
2334  */
2335 int
2336 PySequence_Contains(PyObject *seq, PyObject *ob)
2337 {
2338         Py_ssize_t result;
2339         if (PyType_HasFeature(seq->ob_type, Py_TPFLAGS_HAVE_SEQUENCE_IN)) {
2340                 PySequenceMethods *sqm = seq->ob_type->tp_as_sequence;
2341                 if (sqm != NULL && sqm->sq_contains != NULL)
2342                         return (*sqm->sq_contains)(seq, ob);
2343         }
2344         result = _PySequence_IterSearch(seq, ob, PY_ITERSEARCH_CONTAINS);
2345         return Py_SAFE_DOWNCAST(result, Py_ssize_t, int);
2346 }
2347
2348 /* Backwards compatibility */
2349 #undef PySequence_In
2350 int
2351 PySequence_In(PyObject *w, PyObject *v)
2352 {
2353         return PySequence_Contains(w, v);
2354 }
2355
2356 Py_ssize_t
2357 PySequence_Index(PyObject *s, PyObject *o)
2358 {
2359         return _PySequence_IterSearch(s, o, PY_ITERSEARCH_INDEX);
2360 }
2361
2362 /* Operations on mappings */
2363
2364 int
2365 PyMapping_Check(PyObject *o)
2366 {
2367         if (o && PyInstance_Check(o))
2368                 return PyObject_HasAttrString(o, "__getitem__");
2369
2370         return  o && o->ob_type->tp_as_mapping &&
2371                 o->ob_type->tp_as_mapping->mp_subscript &&
2372                 !(o->ob_type->tp_as_sequence &&
2373                   o->ob_type->tp_as_sequence->sq_slice);
2374 }
2375
2376 Py_ssize_t
2377 PyMapping_Size(PyObject *o)
2378 {
2379         PyMappingMethods *m;
2380
2381         if (o == NULL) {
2382                 null_error();
2383                 return -1;
2384         }
2385
2386         m = o->ob_type->tp_as_mapping;
2387         if (m && m->mp_length)
2388                 return m->mp_length(o);
2389
2390         type_error("object of type '%.200s' has no len()", o);
2391         return -1;
2392 }
2393
2394 #undef PyMapping_Length
2395 Py_ssize_t
2396 PyMapping_Length(PyObject *o)
2397 {
2398         return PyMapping_Size(o);
2399 }
2400 #define PyMapping_Length PyMapping_Size
2401
2402 PyObject *
2403 PyMapping_GetItemString(PyObject *o, char *key)
2404 {
2405         PyObject *okey, *r;
2406
2407         if (key == NULL)
2408                 return null_error();
2409
2410         okey = PyString_FromString(key);
2411         if (okey == NULL)
2412                 return NULL;
2413         r = PyObject_GetItem(o, okey);
2414         Py_DECREF(okey);
2415         return r;
2416 }
2417
2418 int
2419 PyMapping_SetItemString(PyObject *o, char *key, PyObject *value)
2420 {
2421         PyObject *okey;
2422         int r;
2423
2424         if (key == NULL) {
2425                 null_error();
2426                 return -1;
2427         }
2428
2429         okey = PyString_FromString(key);
2430         if (okey == NULL)
2431                 return -1;
2432         r = PyObject_SetItem(o, okey, value);
2433         Py_DECREF(okey);
2434         return r;
2435 }
2436
2437 int
2438 PyMapping_HasKeyString(PyObject *o, char *key)
2439 {
2440         PyObject *v;
2441
2442         v = PyMapping_GetItemString(o, key);
2443         if (v) {
2444                 Py_DECREF(v);
2445                 return 1;
2446         }
2447         PyErr_Clear();
2448         return 0;
2449 }
2450
2451 int
2452 PyMapping_HasKey(PyObject *o, PyObject *key)
2453 {
2454         PyObject *v;
2455
2456         v = PyObject_GetItem(o, key);
2457         if (v) {
2458                 Py_DECREF(v);
2459                 return 1;
2460         }
2461         PyErr_Clear();
2462         return 0;
2463 }
2464
2465 /* Operations on callable objects */
2466
2467 /* XXX PyCallable_Check() is in object.c */
2468
2469 PyObject *
2470 PyObject_CallObject(PyObject *o, PyObject *a)
2471 {
2472         return PyEval_CallObjectWithKeywords(o, a, NULL);
2473 }
2474
2475 PyObject *
2476 PyObject_Call(PyObject *func, PyObject *arg, PyObject *kw)
2477 {
2478         ternaryfunc call;
2479
2480         if ((call = func->ob_type->tp_call) != NULL) {
2481                 PyObject *result;
2482                 if (Py_EnterRecursiveCall(" while calling a Python object"))
2483                     return NULL;
2484                 result = (*call)(func, arg, kw);
2485                 Py_LeaveRecursiveCall();
2486                 if (result == NULL && !PyErr_Occurred())
2487                         PyErr_SetString(
2488                                 PyExc_SystemError,
2489                                 "NULL result without error in PyObject_Call");
2490                 return result;
2491         }
2492         PyErr_Format(PyExc_TypeError, "'%.200s' object is not callable",
2493                      func->ob_type->tp_name);
2494         return NULL;
2495 }
2496
2497 static PyObject*
2498 call_function_tail(PyObject *callable, PyObject *args)
2499 {
2500         PyObject *retval;
2501
2502         if (args == NULL)
2503                 return NULL;
2504
2505         if (!PyTuple_Check(args)) {
2506                 PyObject *a;
2507
2508                 a = PyTuple_New(1);
2509                 if (a == NULL) {
2510                         Py_DECREF(args);
2511                         return NULL;
2512                 }
2513                 PyTuple_SET_ITEM(a, 0, args);
2514                 args = a;
2515         }
2516         retval = PyObject_Call(callable, args, NULL);
2517
2518         Py_DECREF(args);
2519
2520         return retval;
2521 }
2522
2523 PyObject *
2524 PyObject_CallFunction(PyObject *callable, char *format, ...)
2525 {
2526         va_list va;
2527         PyObject *args;
2528
2529         if (callable == NULL)
2530                 return null_error();
2531
2532         if (format && *format) {
2533                 va_start(va, format);
2534                 args = Py_VaBuildValue(format, va);
2535                 va_end(va);
2536         }
2537         else
2538                 args = PyTuple_New(0);
2539
2540         return call_function_tail(callable, args);
2541 }
2542
2543 PyObject *
2544 _PyObject_CallFunction_SizeT(PyObject *callable, char *format, ...)
2545 {
2546         va_list va;
2547         PyObject *args;
2548
2549         if (callable == NULL)
2550                 return null_error();
2551
2552         if (format && *format) {
2553                 va_start(va, format);
2554                 args = _Py_VaBuildValue_SizeT(format, va);
2555                 va_end(va);
2556         }
2557         else
2558                 args = PyTuple_New(0);
2559
2560         return call_function_tail(callable, args);
2561 }
2562
2563 PyObject *
2564 PyObject_CallMethod(PyObject *o, char *name, char *format, ...)
2565 {
2566         va_list va;
2567         PyObject *args;
2568         PyObject *func = NULL;
2569         PyObject *retval = NULL;
2570
2571         if (o == NULL || name == NULL)
2572                 return null_error();
2573
2574         func = PyObject_GetAttrString(o, name);
2575         if (func == NULL) {
2576                 PyErr_SetString(PyExc_AttributeError, name);
2577                 return 0;
2578         }
2579
2580         if (!PyCallable_Check(func)) {
2581                 type_error("attribute of type '%.200s' is not callable", func);
2582                 goto exit;
2583         }
2584
2585         if (format && *format) {
2586                 va_start(va, format);
2587                 args = Py_VaBuildValue(format, va);
2588                 va_end(va);
2589         }
2590         else
2591                 args = PyTuple_New(0);
2592
2593         retval = call_function_tail(func, args);
2594
2595   exit:
2596         /* args gets consumed in call_function_tail */
2597         Py_XDECREF(func);
2598
2599         return retval;
2600 }
2601
2602 PyObject *
2603 _PyObject_CallMethod_SizeT(PyObject *o, char *name, char *format, ...)
2604 {
2605         va_list va;
2606         PyObject *args;
2607         PyObject *func = NULL;
2608         PyObject *retval = NULL;
2609
2610         if (o == NULL || name == NULL)
2611                 return null_error();
2612
2613         func = PyObject_GetAttrString(o, name);
2614         if (func == NULL) {
2615                 PyErr_SetString(PyExc_AttributeError, name);
2616                 return 0;
2617         }
2618
2619         if (!PyCallable_Check(func)) {
2620                 type_error("attribute of type '%.200s' is not callable", func);
2621                 goto exit;
2622         }
2623
2624         if (format && *format) {
2625                 va_start(va, format);
2626                 args = _Py_VaBuildValue_SizeT(format, va);
2627                 va_end(va);
2628         }
2629         else
2630                 args = PyTuple_New(0);
2631
2632         retval = call_function_tail(func, args);
2633
2634   exit:
2635         /* args gets consumed in call_function_tail */
2636         Py_XDECREF(func);
2637
2638         return retval;
2639 }
2640
2641
2642 static PyObject *
2643 objargs_mktuple(va_list va)
2644 {
2645         int i, n = 0;
2646         va_list countva;
2647         PyObject *result, *tmp;
2648
2649 #ifdef VA_LIST_IS_ARRAY
2650         memcpy(countva, va, sizeof(va_list));
2651 #else
2652 #ifdef __va_copy
2653         __va_copy(countva, va);
2654 #else
2655         countva = va;
2656 #endif
2657 #endif
2658
2659         while (((PyObject *)va_arg(countva, PyObject *)) != NULL)
2660                 ++n;
2661         result = PyTuple_New(n);
2662         if (result != NULL && n > 0) {
2663                 for (i = 0; i < n; ++i) {
2664                         tmp = (PyObject *)va_arg(va, PyObject *);
2665                         PyTuple_SET_ITEM(result, i, tmp);
2666                         Py_INCREF(tmp);
2667                 }
2668         }
2669         return result;
2670 }
2671
2672 PyObject *
2673 PyObject_CallMethodObjArgs(PyObject *callable, PyObject *name, ...)
2674 {
2675         PyObject *args, *tmp;
2676         va_list vargs;
2677
2678         if (callable == NULL || name == NULL)
2679                 return null_error();
2680
2681         callable = PyObject_GetAttr(callable, name);
2682         if (callable == NULL)
2683                 return NULL;
2684
2685         /* count the args */
2686         va_start(vargs, name);
2687         args = objargs_mktuple(vargs);
2688         va_end(vargs);
2689         if (args == NULL) {
2690                 Py_DECREF(callable);
2691                 return NULL;
2692         }
2693         tmp = PyObject_Call(callable, args, NULL);
2694         Py_DECREF(args);
2695         Py_DECREF(callable);
2696
2697         return tmp;
2698 }
2699
2700 PyObject *
2701 PyObject_CallFunctionObjArgs(PyObject *callable, ...)
2702 {
2703         PyObject *args, *tmp;
2704         va_list vargs;
2705
2706         if (callable == NULL)
2707                 return null_error();
2708
2709         /* count the args */
2710         va_start(vargs, callable);
2711         args = objargs_mktuple(vargs);
2712         va_end(vargs);
2713         if (args == NULL)
2714                 return NULL;
2715         tmp = PyObject_Call(callable, args, NULL);
2716         Py_DECREF(args);
2717
2718         return tmp;
2719 }
2720
2721
2722 /* isinstance(), issubclass() */
2723
2724 /* abstract_get_bases() has logically 4 return states, with a sort of 0th
2725  * state that will almost never happen.
2726  *
2727  * 0. creating the __bases__ static string could get a MemoryError
2728  * 1. getattr(cls, '__bases__') could raise an AttributeError
2729  * 2. getattr(cls, '__bases__') could raise some other exception
2730  * 3. getattr(cls, '__bases__') could return a tuple
2731  * 4. getattr(cls, '__bases__') could return something other than a tuple
2732  *
2733  * Only state #3 is a non-error state and only it returns a non-NULL object
2734  * (it returns the retrieved tuple).
2735  *
2736  * Any raised AttributeErrors are masked by clearing the exception and
2737  * returning NULL.  If an object other than a tuple comes out of __bases__,
2738  * then again, the return value is NULL.  So yes, these two situations
2739  * produce exactly the same results: NULL is returned and no error is set.
2740  *
2741  * If some exception other than AttributeError is raised, then NULL is also
2742  * returned, but the exception is not cleared.  That's because we want the
2743  * exception to be propagated along.
2744  *
2745  * Callers are expected to test for PyErr_Occurred() when the return value
2746  * is NULL to decide whether a valid exception should be propagated or not.
2747  * When there's no exception to propagate, it's customary for the caller to
2748  * set a TypeError.
2749  */
2750 static PyObject *
2751 abstract_get_bases(PyObject *cls)
2752 {
2753         static PyObject *__bases__ = NULL;
2754         PyObject *bases;
2755
2756         if (__bases__ == NULL) {
2757                 __bases__ = PyString_InternFromString("__bases__");
2758                 if (__bases__ == NULL)
2759                         return NULL;
2760         }
2761         bases = PyObject_GetAttr(cls, __bases__);
2762         if (bases == NULL) {
2763                 if (PyErr_ExceptionMatches(PyExc_AttributeError))
2764                         PyErr_Clear();
2765                 return NULL;
2766         }
2767         if (!PyTuple_Check(bases)) {
2768                 Py_DECREF(bases);
2769                 return NULL;
2770         }
2771         return bases;
2772 }
2773
2774
2775 static int
2776 abstract_issubclass(PyObject *derived, PyObject *cls)
2777 {
2778         PyObject *bases;
2779         Py_ssize_t i, n;
2780         int r = 0;
2781
2782
2783         if (derived == cls)
2784                 return 1;
2785
2786         if (PyTuple_Check(cls)) {
2787                 /* Not a general sequence -- that opens up the road to
2788                    recursion and stack overflow. */
2789                 n = PyTuple_GET_SIZE(cls);
2790                 for (i = 0; i < n; i++) {
2791                         if (derived == PyTuple_GET_ITEM(cls, i))
2792                                 return 1;
2793                 }
2794         }
2795         bases = abstract_get_bases(derived);
2796         if (bases == NULL) {
2797                 if (PyErr_Occurred())
2798                         return -1;
2799                 return 0;
2800         }
2801         n = PyTuple_GET_SIZE(bases);
2802         for (i = 0; i < n; i++) {
2803                 r = abstract_issubclass(PyTuple_GET_ITEM(bases, i), cls);
2804                 if (r != 0)
2805                         break;
2806         }
2807
2808         Py_DECREF(bases);
2809
2810         return r;
2811 }
2812
2813 static int
2814 check_class(PyObject *cls, const char *error)
2815 {
2816         PyObject *bases = abstract_get_bases(cls);
2817         if (bases == NULL) {
2818                 /* Do not mask errors. */
2819                 if (!PyErr_Occurred())
2820                         PyErr_SetString(PyExc_TypeError, error);
2821                 return 0;
2822         }
2823         Py_DECREF(bases);
2824         return -1;
2825 }
2826
2827 static int
2828 recursive_isinstance(PyObject *inst, PyObject *cls, int recursion_depth)
2829 {
2830         PyObject *icls;
2831         static PyObject *__class__ = NULL;
2832         int retval = 0;
2833
2834         if (__class__ == NULL) {
2835                 __class__ = PyString_InternFromString("__class__");
2836                 if (__class__ == NULL)
2837                         return -1;
2838         }
2839
2840         if (PyClass_Check(cls) && PyInstance_Check(inst)) {
2841                 PyObject *inclass =
2842                         (PyObject*)((PyInstanceObject*)inst)->in_class;
2843                 retval = PyClass_IsSubclass(inclass, cls);
2844         }
2845         else if (PyType_Check(cls)) {
2846                 retval = PyObject_TypeCheck(inst, (PyTypeObject *)cls);
2847                 if (retval == 0) {
2848                         PyObject *c = PyObject_GetAttr(inst, __class__);
2849                         if (c == NULL) {
2850                                 PyErr_Clear();
2851                         }
2852                         else {
2853                                 if (c != (PyObject *)(inst->ob_type) &&
2854                                     PyType_Check(c))
2855                                         retval = PyType_IsSubtype(
2856                                                 (PyTypeObject *)c,
2857                                                 (PyTypeObject *)cls);
2858                                 Py_DECREF(c);
2859                         }
2860                 }
2861         }
2862         else if (PyTuple_Check(cls)) {
2863                 Py_ssize_t i, n;
2864
2865                 if (!recursion_depth) {
2866                     PyErr_SetString(PyExc_RuntimeError,
2867                                     "nest level of tuple too deep");
2868                     return -1;
2869                 }
2870
2871                 n = PyTuple_GET_SIZE(cls);
2872                 for (i = 0; i < n; i++) {
2873                         retval = recursive_isinstance(
2874                                     inst,
2875                                     PyTuple_GET_ITEM(cls, i),
2876                                     recursion_depth-1);
2877                         if (retval != 0)
2878                                 break;
2879                 }
2880         }
2881         else {
2882                 if (!check_class(cls,
2883                         "isinstance() arg 2 must be a class, type,"
2884                         " or tuple of classes and types"))
2885                         return -1;
2886                 icls = PyObject_GetAttr(inst, __class__);
2887                 if (icls == NULL) {
2888                         PyErr_Clear();
2889                         retval = 0;
2890                 }
2891                 else {
2892                         retval = abstract_issubclass(icls, cls);
2893                         Py_DECREF(icls);
2894                 }
2895         }
2896
2897         return retval;
2898 }
2899
2900 int
2901 PyObject_IsInstance(PyObject *inst, PyObject *cls)
2902 {
2903         static PyObject *name = NULL;
2904         PyObject *checker;
2905
2906         /* Quick test for an exact match */
2907         if (Py_TYPE(inst) == (PyTypeObject *)cls)
2908                 return 1;
2909
2910         if (name == NULL) {
2911                 name = PyString_InternFromString("__instancecheck__");
2912                 if (name == NULL)
2913                         return -1;
2914         }
2915         checker = PyObject_GetAttr(cls, name);
2916         if (checker == NULL && PyErr_Occurred())
2917                 PyErr_Clear();
2918         if (checker != NULL) {
2919                 PyObject *res;
2920                 int ok = -1;
2921                 if (Py_EnterRecursiveCall(" in __instancecheck__")) {
2922                         Py_DECREF(checker);
2923                         return ok;
2924                 }
2925                 res = PyObject_CallFunctionObjArgs(checker, inst, NULL);
2926                 Py_LeaveRecursiveCall();
2927                 Py_DECREF(checker);
2928                 if (res != NULL) {
2929                         ok = PyObject_IsTrue(res);
2930                         Py_DECREF(res);
2931                 }
2932                 return ok;
2933         }
2934         return recursive_isinstance(inst, cls, Py_GetRecursionLimit());
2935 }
2936
2937 static  int
2938 recursive_issubclass(PyObject *derived, PyObject *cls, int recursion_depth)
2939 {
2940         int retval;
2941
2942         if (!PyClass_Check(derived) || !PyClass_Check(cls)) {
2943                 if (!check_class(derived,
2944                                  "issubclass() arg 1 must be a class"))
2945                         return -1;
2946
2947                 if (PyTuple_Check(cls)) {
2948                         Py_ssize_t i;
2949                         Py_ssize_t n = PyTuple_GET_SIZE(cls);
2950
2951                         if (!recursion_depth) {
2952                             PyErr_SetString(PyExc_RuntimeError,
2953                                             "nest level of tuple too deep");
2954                             return -1;
2955                         }
2956                         for (i = 0; i < n; ++i) {
2957                                 retval = recursive_issubclass(
2958                                             derived,
2959                                             PyTuple_GET_ITEM(cls, i),
2960                                             recursion_depth-1);
2961                                 if (retval != 0) {
2962                                         /* either found it, or got an error */
2963                                         return retval;
2964                                 }
2965                         }
2966                         return 0;
2967                 }
2968                 else {
2969                         if (!check_class(cls,
2970                                         "issubclass() arg 2 must be a class"
2971                                         " or tuple of classes"))
2972                                 return -1;
2973                 }
2974
2975                 retval = abstract_issubclass(derived, cls);
2976         }
2977         else {
2978                 /* shortcut */
2979                 if (!(retval = (derived == cls)))
2980                         retval = PyClass_IsSubclass(derived, cls);
2981         }
2982
2983         return retval;
2984 }
2985
2986 int
2987 PyObject_IsSubclass(PyObject *derived, PyObject *cls)
2988 {
2989         static PyObject *name = NULL;
2990         PyObject *t, *v, *tb;
2991         PyObject *checker;
2992         PyErr_Fetch(&t, &v, &tb);
2993
2994         if (name == NULL) {
2995                 name = PyString_InternFromString("__subclasscheck__");
2996                 if (name == NULL)
2997                         return -1;
2998         }
2999         checker = PyObject_GetAttr(cls, name);
3000         PyErr_Restore(t, v, tb);
3001         if (checker != NULL) {
3002                 PyObject *res;
3003                 int ok = -1;
3004                 if (Py_EnterRecursiveCall(" in __subclasscheck__"))
3005                         return ok;
3006                 res = PyObject_CallFunctionObjArgs(checker, derived, NULL);
3007                 Py_LeaveRecursiveCall();
3008                 Py_DECREF(checker);
3009                 if (res != NULL) {
3010                         ok = PyObject_IsTrue(res);
3011                         Py_DECREF(res);
3012                 }
3013                 return ok;
3014         }
3015         return recursive_issubclass(derived, cls, Py_GetRecursionLimit());
3016 }
3017
3018
3019 PyObject *
3020 PyObject_GetIter(PyObject *o)
3021 {
3022         PyTypeObject *t = o->ob_type;
3023         getiterfunc f = NULL;
3024         if (PyType_HasFeature(t, Py_TPFLAGS_HAVE_ITER))
3025                 f = t->tp_iter;
3026         if (f == NULL) {
3027                 if (PySequence_Check(o))
3028                         return PySeqIter_New(o);
3029                 return type_error("'%.200s' object is not iterable", o);
3030         }
3031         else {
3032                 PyObject *res = (*f)(o);
3033                 if (res != NULL && !PyIter_Check(res)) {
3034                         PyErr_Format(PyExc_TypeError,
3035                                      "iter() returned non-iterator "
3036                                      "of type '%.100s'",
3037                                      res->ob_type->tp_name);
3038                         Py_DECREF(res);
3039                         res = NULL;
3040                 }
3041                 return res;
3042         }
3043 }
3044
3045 /* Return next item.
3046  * If an error occurs, return NULL.  PyErr_Occurred() will be true.
3047  * If the iteration terminates normally, return NULL and clear the
3048  * PyExc_StopIteration exception (if it was set).  PyErr_Occurred()
3049  * will be false.
3050  * Else return the next object.  PyErr_Occurred() will be false.
3051  */
3052 PyObject *
3053 PyIter_Next(PyObject *iter)
3054 {
3055         PyObject *result;
3056         assert(PyIter_Check(iter));
3057         result = (*iter->ob_type->tp_iternext)(iter);
3058         if (result == NULL &&
3059             PyErr_Occurred() &&
3060             PyErr_ExceptionMatches(PyExc_StopIteration))
3061                 PyErr_Clear();
3062         return result;
3063 }