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