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 #define HASINDEX(o) PyType_HasFeature((o)->ob_type, Py_TPFLAGS_HAVE_INDEX)
  12
  13
  14 /* Shorthands to return certain errors */
  15
  16 static PyObject *
  17 type_error(const char *msg, PyObject *obj)
  18 {
  19         PyErr_Format(PyExc_TypeError, msg, obj->ob_type->tp_name);
  20         return NULL;
  21 }
  22
  23 static PyObject *
  24 null_error(void)
  25 {
  26         if (!PyErr_Occurred())
  27                 PyErr_SetString(PyExc_SystemError,
  28                                 "null argument to internal routine");
  29         return NULL;
  30 }
  31
  32 /* Operations on any object */
  33
  34 int
  35 PyObject_Cmp(PyObject *o1, PyObject *o2, int *result)
  36 {
  37         int r;
  38
  39         if (o1 == NULL || o2 == NULL) {
  40                 null_error();
  41                 return -1;
  42         }
  43         r = PyObject_Compare(o1, o2);
  44         if (PyErr_Occurred())
  45                 return -1;
  46         *result = r;
  47         return 0;
  48 }
  49
  50 PyObject *
  51 PyObject_Type(PyObject *o)
  52 {
  53         PyObject *v;
  54
  55         if (o == NULL)
  56                 return null_error();
  57         v = (PyObject *)o->ob_type;
  58         Py_INCREF(v);
  59         return v;
  60 }
  61
  62 Py_ssize_t
  63 PyObject_Size(PyObject *o)
  64 {
  65         PySequenceMethods *m;
  66
  67         if (o == NULL) {
  68                 null_error();
  69                 return -1;
  70         }
  71
  72         m = o->ob_type->tp_as_sequence;
  73         if (m && m->sq_length)
  74                 return m->sq_length(o);
  75
  76         return PyMapping_Size(o);
  77 }
  78
  79 #undef PyObject_Length
  80 Py_ssize_t
  81 PyObject_Length(PyObject *o)
  82 {
  83         return PyObject_Size(o);
  84 }
  85 #define PyObject_Length PyObject_Size
  86
  87 Py_ssize_t
  88 _PyObject_LengthHint(PyObject *o)
  89 {
  90         Py_ssize_t rv = PyObject_Size(o);
  91         if (rv != -1)
  92                 return rv;
  93         if (PyErr_ExceptionMatches(PyExc_TypeError) ||
  94             PyErr_ExceptionMatches(PyExc_AttributeError)) {
  95                 PyObject *err_type, *err_value, *err_tb, *ro;
  96
  97                 PyErr_Fetch(&err_type, &err_value, &err_tb);
  98                 ro = PyObject_CallMethod(o, "__length_hint__", NULL);
  99                 if (ro != NULL) {
 100                         rv = PyInt_AsLong(ro);
 101                         Py_DECREF(ro);
 102                         Py_XDECREF(err_type);
 103                         Py_XDECREF(err_value);
 104                         Py_XDECREF(err_tb);
 105                         return rv;
 106                 }
 107                 PyErr_Restore(err_type, err_value, err_tb);
 108         }
 109         return -1;
 110 }
 111
 112 PyObject *
 113 PyObject_GetItem(PyObject *o, PyObject *key)
 114 {
 115         PyMappingMethods *m;
 116
 117         if (o == NULL || key == NULL)
 118                 return null_error();
 119
 120         m = o->ob_type->tp_as_mapping;
 121         if (m && m->mp_subscript)
 122                 return m->mp_subscript(o, key);
 123
 124         if (o->ob_type->tp_as_sequence) {
 125                 PyNumberMethods *nb = key->ob_type->tp_as_number;
 126                 if (nb != NULL && HASINDEX(key) && nb->nb_index != NULL) {
 127                         Py_ssize_t key_value = nb->nb_index(key);
 128                         if (key_value == -1 && PyErr_Occurred())
 129                                 return NULL;
 130                         return PySequence_GetItem(o, key_value);
 131                 }
 132                 else if (o->ob_type->tp_as_sequence->sq_item)
 133                         return type_error("sequence index must "
 134                                           "be integer, not '%.200s'", key);
 135         }
 136
 137         return type_error("'%.200s' object is unsubscriptable", o);
 138 }
 139
 140 int
 141 PyObject_SetItem(PyObject *o, PyObject *key, PyObject *value)
 142 {
 143         PyMappingMethods *m;
 144
 145         if (o == NULL || key == NULL || value == NULL) {
 146                 null_error();
 147                 return -1;
 148         }
 149         m = o->ob_type->tp_as_mapping;
 150         if (m && m->mp_ass_subscript)
 151                 return m->mp_ass_subscript(o, key, value);
 152
 153         if (o->ob_type->tp_as_sequence) {
 154                 PyNumberMethods *nb = key->ob_type->tp_as_number;
 155                 if (nb != NULL && HASINDEX(key) && nb->nb_index != NULL) {
 156                         Py_ssize_t key_value = nb->nb_index(key);
 157                         if (key_value == -1 && PyErr_Occurred())
 158                                 return -1;
 159                         return PySequence_SetItem(o, key_value, value);
 160                 }
 161                 else if (o->ob_type->tp_as_sequence->sq_ass_item) {
 162                         type_error("sequence index must be "
 163                                    "integer, not '%.200s'", key);
 164                         return -1;
 165                 }
 166         }
 167
 168         type_error("'%.200s' object does not support item assignment", o);
 169         return -1;
 170 }
 171
 172 int
 173 PyObject_DelItem(PyObject *o, PyObject *key)
 174 {
 175         PyMappingMethods *m;
 176
 177         if (o == NULL || key == NULL) {
 178                 null_error();
 179                 return -1;
 180         }
 181         m = o->ob_type->tp_as_mapping;
 182         if (m && m->mp_ass_subscript)
 183                 return m->mp_ass_subscript(o, key, (PyObject*)NULL);
 184
 185         if (o->ob_type->tp_as_sequence) {
 186                 PyNumberMethods *nb = key->ob_type->tp_as_number;
 187                 if (nb != NULL && HASINDEX(key) && nb->nb_index != NULL) {
 188                         Py_ssize_t key_value = nb->nb_index(key);
 189                         if (key_value == -1 && PyErr_Occurred())
 190                                 return -1;
 191                         return PySequence_DelItem(o, key_value);
 192                 }
 193                 else if (o->ob_type->tp_as_sequence->sq_ass_item) {
 194                         type_error("sequence index must be "
 195                                    "integer, not '%.200s'", key);
 196                         return -1;
 197                 }
 198         }
 199
 200         type_error("'%.200s' object does not support item deletion", o);
 201         return -1;
 202 }
 203
 204 int
 205 PyObject_DelItemString(PyObject *o, char *key)
 206 {
 207         PyObject *okey;
 208         int ret;
 209
 210         if (o == NULL || key == NULL) {
 211                 null_error();
 212                 return -1;
 213         }
 214         okey = PyString_FromString(key);
 215         if (okey == NULL)
 216                 return -1;
 217         ret = PyObject_DelItem(o, okey);
 218         Py_DECREF(okey);
 219         return ret;
 220 }
 221
 222 int
 223 PyObject_AsCharBuffer(PyObject *obj,
 224                           const char **buffer,
 225                           Py_ssize_t *buffer_len)
 226 {
 227         PyBufferProcs *pb;
 228         char *pp;
 229         Py_ssize_t len;
 230
 231         if (obj == NULL || buffer == NULL || buffer_len == NULL) {
 232                 null_error();
 233                 return -1;
 234         }
 235         pb = obj->ob_type->tp_as_buffer;
 236         if (pb == NULL ||
 237              pb->bf_getcharbuffer == NULL ||
 238              pb->bf_getsegcount == NULL) {
 239                 PyErr_SetString(PyExc_TypeError,
 240                                 "expected a character buffer object");
 241                 return -1;
 242         }
 243         if ((*pb->bf_getsegcount)(obj,NULL) != 1) {
 244                 PyErr_SetString(PyExc_TypeError,
 245                                 "expected a single-segment buffer object");
 246                 return -1;
 247         }
 248         len = (*pb->bf_getcharbuffer)(obj, 0, &pp);
 249         if (len < 0)
 250                 return -1;
 251         *buffer = pp;
 252         *buffer_len = len;
 253         return 0;
 254 }
 255
 256 int
 257 PyObject_CheckReadBuffer(PyObject *obj)
 258 {
 259         PyBufferProcs *pb = obj->ob_type->tp_as_buffer;
 260
 261         if (pb == NULL ||
 262             pb->bf_getreadbuffer == NULL ||
 263             pb->bf_getsegcount == NULL ||
 264             (*pb->bf_getsegcount)(obj, NULL) != 1)
 265                 return 0;
 266         return 1;
 267 }
 268
 269 int PyObject_AsReadBuffer(PyObject *obj,
 270                           const void **buffer,
 271                           Py_ssize_t *buffer_len)
 272 {
 273         PyBufferProcs *pb;
 274         void *pp;
 275         Py_ssize_t len;
 276
 277         if (obj == NULL || buffer == NULL || buffer_len == NULL) {
 278                 null_error();
 279                 return -1;
 280         }
 281         pb = obj->ob_type->tp_as_buffer;
 282         if (pb == NULL ||
 283              pb->bf_getreadbuffer == NULL ||
 284              pb->bf_getsegcount == NULL) {
 285                 PyErr_SetString(PyExc_TypeError,
 286                                 "expected a readable buffer object");
 287                 return -1;
 288         }
 289         if ((*pb->bf_getsegcount)(obj, NULL) != 1) {
 290                 PyErr_SetString(PyExc_TypeError,
 291                                 "expected a single-segment buffer object");
 292                 return -1;
 293         }
 294         len = (*pb->bf_getreadbuffer)(obj, 0, &pp);
 295         if (len < 0)
 296                 return -1;
 297         *buffer = pp;
 298         *buffer_len = len;
 299         return 0;
 300 }
 301
 302 int PyObject_AsWriteBuffer(PyObject *obj,
 303                            void **buffer,
 304                            Py_ssize_t *buffer_len)
 305 {
 306         PyBufferProcs *pb;
 307         void*pp;
 308         Py_ssize_t len;
 309
 310         if (obj == NULL || buffer == NULL || buffer_len == NULL) {
 311                 null_error();
 312                 return -1;
 313         }
 314         pb = obj->ob_type->tp_as_buffer;
 315         if (pb == NULL ||
 316              pb->bf_getwritebuffer == NULL ||
 317              pb->bf_getsegcount == NULL) {
 318                 PyErr_SetString(PyExc_TypeError,
 319                                 "expected a writeable buffer object");
 320                 return -1;
 321         }
 322         if ((*pb->bf_getsegcount)(obj, NULL) != 1) {
 323                 PyErr_SetString(PyExc_TypeError,
 324                                 "expected a single-segment buffer object");
 325                 return -1;
 326         }
 327         len = (*pb->bf_getwritebuffer)(obj,0,&pp);
 328         if (len < 0)
 329                 return -1;
 330         *buffer = pp;
 331         *buffer_len = len;
 332         return 0;
 333 }
 334
 335 /* Operations on numbers */
 336
 337 int
 338 PyNumber_Check(PyObject *o)
 339 {
 340         return o && o->ob_type->tp_as_number &&
 341                (o->ob_type->tp_as_number->nb_int ||
 342                 o->ob_type->tp_as_number->nb_float);
 343 }
 344
 345 /* Binary operators */
 346
 347 /* New style number protocol support */
 348
 349 #define NB_SLOT(x) offsetof(PyNumberMethods, x)
 350 #define NB_BINOP(nb_methods, slot) \
 351                 (*(binaryfunc*)(& ((char*)nb_methods)[slot]))
 352 #define NB_TERNOP(nb_methods, slot) \
 353                 (*(ternaryfunc*)(& ((char*)nb_methods)[slot]))
 354
 355 /*
 356   Calling scheme used for binary operations:
 357
 358   v     w       Action
 359   -------------------------------------------------------------------
 360   new   new     w.op(v,w)[*], v.op(v,w), w.op(v,w)
 361   new   old     v.op(v,w), coerce(v,w), v.op(v,w)
 362   old   new     w.op(v,w), coerce(v,w), v.op(v,w)
 363   old   old     coerce(v,w), v.op(v,w)
 364
 365   [*] only when v->ob_type != w->ob_type && w->ob_type is a subclass of
 366       v->ob_type
 367
 368   Legend:
 369   -------
 370   * new == new style number
 371   * old == old style number
 372   * Action indicates the order in which operations are tried until either
 373     a valid result is produced or an error occurs.
 374
 375  */
 376
 377 static PyObject *
 378 binary_op1(PyObject *v, PyObject *w, const int op_slot)
 379 {
 380         PyObject *x;
 381         binaryfunc slotv = NULL;
 382         binaryfunc slotw = NULL;
 383
 384         if (v->ob_type->tp_as_number != NULL && NEW_STYLE_NUMBER(v))
 385                 slotv = NB_BINOP(v->ob_type->tp_as_number, op_slot);
 386         if (w->ob_type != v->ob_type &&
 387             w->ob_type->tp_as_number != NULL && NEW_STYLE_NUMBER(w)) {
 388                 slotw = NB_BINOP(w->ob_type->tp_as_number, op_slot);
 389                 if (slotw == slotv)
 390                         slotw = NULL;
 391         }
 392         if (slotv) {
 393                 if (slotw && PyType_IsSubtype(w->ob_type, v->ob_type)) {
 394                         x = slotw(v, w);
 395                         if (x != Py_NotImplemented)
 396                                 return x;
 397                         Py_DECREF(x); /* can't do it */
 398                         slotw = NULL;
 399                 }
 400                 x = slotv(v, w);
 401                 if (x != Py_NotImplemented)
 402                         return x;
 403                 Py_DECREF(x); /* can't do it */
 404         }
 405         if (slotw) {
 406                 x = slotw(v, w);
 407                 if (x != Py_NotImplemented)
 408                         return x;
 409                 Py_DECREF(x); /* can't do it */
 410         }
 411         if (!NEW_STYLE_NUMBER(v) || !NEW_STYLE_NUMBER(w)) {
 412                 int err = PyNumber_CoerceEx(&v, &w);
 413                 if (err < 0) {
 414                         return NULL;
 415                 }
 416                 if (err == 0) {
 417                         PyNumberMethods *mv = v->ob_type->tp_as_number;
 418                         if (mv) {
 419                                 binaryfunc slot;
 420                                 slot = NB_BINOP(mv, op_slot);
 421                                 if (slot) {
 422                                         x = slot(v, w);
 423                                         Py_DECREF(v);
 424                                         Py_DECREF(w);
 425                                         return x;
 426                                 }
 427                         }
 428                         /* CoerceEx incremented the reference counts */
 429                         Py_DECREF(v);
 430                         Py_DECREF(w);
 431                 }
 432         }
 433         Py_INCREF(Py_NotImplemented);
 434         return Py_NotImplemented;
 435 }
 436
 437 static PyObject *
 438 binop_type_error(PyObject *v, PyObject *w, const char *op_name)
 439 {
 440         PyErr_Format(PyExc_TypeError,
 441                      "unsupported operand type(s) for %.100s: "
 442                      "'%.100s' and '%.100s'",
 443                      op_name,
 444                      v->ob_type->tp_name,
 445                      w->ob_type->tp_name);
 446         return NULL;
 447 }
 448
 449 static PyObject *
 450 binary_op(PyObject *v, PyObject *w, const int op_slot, const char *op_name)
 451 {
 452         PyObject *result = binary_op1(v, w, op_slot);
 453         if (result == Py_NotImplemented) {
 454                 Py_DECREF(result);
 455                 return binop_type_error(v, w, op_name);
 456         }
 457         return result;
 458 }
 459
 460
 461 /*
 462   Calling scheme used for ternary operations:
 463
 464   *** In some cases, w.op is called before v.op; see binary_op1. ***
 465
 466   v     w       z       Action
 467   -------------------------------------------------------------------
 468   new   new     new     v.op(v,w,z), w.op(v,w,z), z.op(v,w,z)
 469   new   old     new     v.op(v,w,z), z.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 470   old   new     new     w.op(v,w,z), z.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 471   old   old     new     z.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 472   new   new     old     v.op(v,w,z), w.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 473   new   old     old     v.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 474   old   new     old     w.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 475   old   old     old     coerce(v,w,z), v.op(v,w,z)
 476
 477   Legend:
 478   -------
 479   * new == new style number
 480   * old == old style number
 481   * Action indicates the order in which operations are tried until either
 482     a valid result is produced or an error occurs.
 483   * coerce(v,w,z) actually does: coerce(v,w), coerce(v,z), coerce(w,z) and
 484     only if z != Py_None; if z == Py_None, then it is treated as absent
 485     variable and only coerce(v,w) is tried.
 486
 487  */
 488
 489 static PyObject *
 490 ternary_op(PyObject *v,
 491            PyObject *w,
 492            PyObject *z,
 493            const int op_slot,
 494            const char *op_name)
 495 {
 496         PyNumberMethods *mv, *mw, *mz;
 497         PyObject *x = NULL;
 498         ternaryfunc slotv = NULL;
 499         ternaryfunc slotw = NULL;
 500         ternaryfunc slotz = NULL;
 501
 502         mv = v->ob_type->tp_as_number;
 503         mw = w->ob_type->tp_as_number;
 504         if (mv != NULL && NEW_STYLE_NUMBER(v))
 505                 slotv = NB_TERNOP(mv, op_slot);
 506         if (w->ob_type != v->ob_type &&
 507             mw != NULL && NEW_STYLE_NUMBER(w)) {
 508                 slotw = NB_TERNOP(mw, op_slot);
 509                 if (slotw == slotv)
 510                         slotw = NULL;
 511         }
 512         if (slotv) {
 513                 if (slotw && PyType_IsSubtype(w->ob_type, v->ob_type)) {
 514                         x = slotw(v, w, z);
 515                         if (x != Py_NotImplemented)
 516                                 return x;
 517                         Py_DECREF(x); /* can't do it */
 518                         slotw = NULL;
 519                 }
 520                 x = slotv(v, w, z);
 521                 if (x != Py_NotImplemented)
 522                         return x;
 523                 Py_DECREF(x); /* can't do it */
 524         }
 525         if (slotw) {
 526                 x = slotw(v, w, z);
 527                 if (x != Py_NotImplemented)
 528                         return x;
 529                 Py_DECREF(x); /* can't do it */
 530         }
 531         mz = z->ob_type->tp_as_number;
 532         if (mz != NULL && NEW_STYLE_NUMBER(z)) {
 533                 slotz = NB_TERNOP(mz, op_slot);
 534                 if (slotz == slotv || slotz == slotw)
 535                         slotz = NULL;
 536                 if (slotz) {
 537                         x = slotz(v, w, z);
 538                         if (x != Py_NotImplemented)
 539                                 return x;
 540                         Py_DECREF(x); /* can't do it */
 541                 }
 542         }
 543
 544         if (!NEW_STYLE_NUMBER(v) || !NEW_STYLE_NUMBER(w) ||
 545                         (z != Py_None && !NEW_STYLE_NUMBER(z))) {
 546                 /* we have an old style operand, coerce */
 547                 PyObject *v1, *z1, *w2, *z2;
 548                 int c;
 549
 550                 c = PyNumber_Coerce(&v, &w);
 551                 if (c != 0)
 552                         goto error3;
 553
 554                 /* Special case: if the third argument is None, it is
 555                    treated as absent argument and not coerced. */
 556                 if (z == Py_None) {
 557                         if (v->ob_type->tp_as_number) {
 558                                 slotz = NB_TERNOP(v->ob_type->tp_as_number,
 559                                                   op_slot);
 560                                 if (slotz)
 561                                         x = slotz(v, w, z);
 562                                 else
 563                                         c = -1;
 564                         }
 565                         else
 566                                 c = -1;
 567                         goto error2;
 568                 }
 569                 v1 = v;
 570                 z1 = z;
 571                 c = PyNumber_Coerce(&v1, &z1);
 572                 if (c != 0)
 573                         goto error2;
 574                 w2 = w;
 575                 z2 = z1;
 576                 c = PyNumber_Coerce(&w2, &z2);
 577                 if (c != 0)
 578                         goto error1;
 579
 580                 if (v1->ob_type->tp_as_number != NULL) {
 581                         slotv = NB_TERNOP(v1->ob_type->tp_as_number,
 582                                           op_slot);
 583                         if (slotv)
 584                                 x = slotv(v1, w2, z2);
 585                         else
 586                                 c = -1;
 587                 }
 588                 else
 589                         c = -1;
 590
 591                 Py_DECREF(w2);
 592                 Py_DECREF(z2);
 593         error1:
 594                 Py_DECREF(v1);
 595                 Py_DECREF(z1);
 596         error2:
 597                 Py_DECREF(v);
 598                 Py_DECREF(w);
 599         error3:
 600                 if (c >= 0)
 601                         return x;
 602         }
 603
 604         if (z == Py_None)
 605                 PyErr_Format(
 606                         PyExc_TypeError,
 607                         "unsupported operand type(s) for ** or pow(): "
 608                         "'%.100s' and '%.100s'",
 609                         v->ob_type->tp_name,
 610                         w->ob_type->tp_name);
 611         else
 612                 PyErr_Format(
 613                         PyExc_TypeError,
 614                         "unsupported operand type(s) for pow(): "
 615                         "'%.100s', '%.100s', '%.100s'",
 616                         v->ob_type->tp_name,
 617                         w->ob_type->tp_name,
 618                         z->ob_type->tp_name);
 619         return NULL;
 620 }
 621
 622 #define BINARY_FUNC(func, op, op_name) \
 623     PyObject * \
 624     func(PyObject *v, PyObject *w) { \
 625             return binary_op(v, w, NB_SLOT(op), op_name); \
 626     }
 627
 628 BINARY_FUNC(PyNumber_Or, nb_or, "|")
 629 BINARY_FUNC(PyNumber_Xor, nb_xor, "^")
 630 BINARY_FUNC(PyNumber_And, nb_and, "&")
 631 BINARY_FUNC(PyNumber_Lshift, nb_lshift, "<<")
 632 BINARY_FUNC(PyNumber_Rshift, nb_rshift, ">>")
 633 BINARY_FUNC(PyNumber_Subtract, nb_subtract, "-")
 634 BINARY_FUNC(PyNumber_Divide, nb_divide, "/")
 635 BINARY_FUNC(PyNumber_Divmod, nb_divmod, "divmod()")
 636
 637 PyObject *
 638 PyNumber_Add(PyObject *v, PyObject *w)
 639 {
 640         PyObject *result = binary_op1(v, w, NB_SLOT(nb_add));
 641         if (result == Py_NotImplemented) {
 642                 PySequenceMethods *m = v->ob_type->tp_as_sequence;
 643                 Py_DECREF(result);
 644                 if (m && m->sq_concat) {
 645                         return (*m->sq_concat)(v, w);
 646                 }
 647                 result = binop_type_error(v, w, "+");
 648         }
 649         return result;
 650 }
 651
 652 static PyObject *
 653 sequence_repeat(ssizeargfunc repeatfunc, PyObject *seq, PyObject *n)
 654 {
 655         Py_ssize_t count;
 656         PyNumberMethods *nb = n->ob_type->tp_as_number;
 657         if (nb != NULL && HASINDEX(n) && nb->nb_index != NULL) {
 658                 count = nb->nb_index(n);
 659                 if (count == -1 && PyErr_Occurred())
 660                         return NULL;
 661         }
 662         else {
 663                 return type_error("can't multiply sequence by "
 664                                   "non-int of type '%.200s'", n);
 665         }
 666         return (*repeatfunc)(seq, count);
 667 }
 668
 669 PyObject *
 670 PyNumber_Multiply(PyObject *v, PyObject *w)
 671 {
 672         PyObject *result = binary_op1(v, w, NB_SLOT(nb_multiply));
 673         if (result == Py_NotImplemented) {
 674                 PySequenceMethods *mv = v->ob_type->tp_as_sequence;
 675                 PySequenceMethods *mw = w->ob_type->tp_as_sequence;
 676                 Py_DECREF(result);
 677                 if  (mv && mv->sq_repeat) {
 678                         return sequence_repeat(mv->sq_repeat, v, w);
 679                 }
 680                 else if (mw && mw->sq_repeat) {
 681                         return sequence_repeat(mw->sq_repeat, w, v);
 682                 }
 683                 result = binop_type_error(v, w, "*");
 684         }
 685         return result;
 686 }
 687
 688 PyObject *
 689 PyNumber_FloorDivide(PyObject *v, PyObject *w)
 690 {
 691         /* XXX tp_flags test */
 692         return binary_op(v, w, NB_SLOT(nb_floor_divide), "//");
 693 }
 694
 695 PyObject *
 696 PyNumber_TrueDivide(PyObject *v, PyObject *w)
 697 {
 698         /* XXX tp_flags test */
 699         return binary_op(v, w, NB_SLOT(nb_true_divide), "/");
 700 }
 701
 702 PyObject *
 703 PyNumber_Remainder(PyObject *v, PyObject *w)
 704 {
 705         return binary_op(v, w, NB_SLOT(nb_remainder), "%");
 706 }
 707
 708 PyObject *
 709 PyNumber_Power(PyObject *v, PyObject *w, PyObject *z)
 710 {
 711         return ternary_op(v, w, z, NB_SLOT(nb_power), "** or pow()");
 712 }
 713
 714 /* Binary in-place operators */
 715
 716 /* The in-place operators are defined to fall back to the 'normal',
 717    non in-place operations, if the in-place methods are not in place.
 718
 719    - If the left hand object has the appropriate struct members, and
 720      they are filled, call the appropriate function and return the
 721      result.  No coercion is done on the arguments; the left-hand object
 722      is the one the operation is performed on, and it's up to the
 723      function to deal with the right-hand object.
 724
 725    - Otherwise, in-place modification is not supported. Handle it exactly as
 726      a non in-place operation of the same kind.
 727
 728    */
 729
 730 #define HASINPLACE(t) \
 731         PyType_HasFeature((t)->ob_type, Py_TPFLAGS_HAVE_INPLACEOPS)
 732
 733 static PyObject *
 734 binary_iop1(PyObject *v, PyObject *w, const int iop_slot, const int op_slot)
 735 {
 736         PyNumberMethods *mv = v->ob_type->tp_as_number;
 737         if (mv != NULL && HASINPLACE(v)) {
 738                 binaryfunc slot = NB_BINOP(mv, iop_slot);
 739                 if (slot) {
 740                         PyObject *x = (slot)(v, w);
 741                         if (x != Py_NotImplemented) {
 742                                 return x;
 743                         }
 744                         Py_DECREF(x);
 745                 }
 746         }
 747         return binary_op1(v, w, op_slot);
 748 }
 749
 750 static PyObject *
 751 binary_iop(PyObject *v, PyObject *w, const int iop_slot, const int op_slot,
 752                 const char *op_name)
 753 {
 754         PyObject *result = binary_iop1(v, w, iop_slot, op_slot);
 755         if (result == Py_NotImplemented) {
 756                 Py_DECREF(result);
 757                 return binop_type_error(v, w, op_name);
 758         }
 759         return result;
 760 }
 761
 762 #define INPLACE_BINOP(func, iop, op, op_name) \
 763         PyObject * \
 764         func(PyObject *v, PyObject *w) { \
 765                 return binary_iop(v, w, NB_SLOT(iop), NB_SLOT(op), op_name); \
 766         }
 767
 768 INPLACE_BINOP(PyNumber_InPlaceOr, nb_inplace_or, nb_or, "|=")
 769 INPLACE_BINOP(PyNumber_InPlaceXor, nb_inplace_xor, nb_xor, "^=")
 770 INPLACE_BINOP(PyNumber_InPlaceAnd, nb_inplace_and, nb_and, "&=")
 771 INPLACE_BINOP(PyNumber_InPlaceLshift, nb_inplace_lshift, nb_lshift, "<<=")
 772 INPLACE_BINOP(PyNumber_InPlaceRshift, nb_inplace_rshift, nb_rshift, ">>=")
 773 INPLACE_BINOP(PyNumber_InPlaceSubtract, nb_inplace_subtract, nb_subtract, "-=")
 774 INPLACE_BINOP(PyNumber_InPlaceDivide, nb_inplace_divide, nb_divide, "/=")
 775
 776 PyObject *
 777 PyNumber_InPlaceFloorDivide(PyObject *v, PyObject *w)
 778 {
 779         /* XXX tp_flags test */
 780         return binary_iop(v, w, NB_SLOT(nb_inplace_floor_divide),
 781                           NB_SLOT(nb_floor_divide), "//=");
 782 }
 783
 784 PyObject *
 785 PyNumber_InPlaceTrueDivide(PyObject *v, PyObject *w)
 786 {
 787         /* XXX tp_flags test */
 788         return binary_iop(v, w, NB_SLOT(nb_inplace_true_divide),
 789                           NB_SLOT(nb_true_divide), "/=");
 790 }
 791
 792 PyObject *
 793 PyNumber_InPlaceAdd(PyObject *v, PyObject *w)
 794 {
 795         PyObject *result = binary_iop1(v, w, NB_SLOT(nb_inplace_add),
 796                                        NB_SLOT(nb_add));
 797         if (result == Py_NotImplemented) {
 798                 PySequenceMethods *m = v->ob_type->tp_as_sequence;
 799                 Py_DECREF(result);
 800                 if (m != NULL) {
 801                         binaryfunc f = NULL;
 802                         if (HASINPLACE(v))
 803                                 f = m->sq_inplace_concat;
 804                         if (f == NULL)
 805                                 f = m->sq_concat;
 806                         if (f != NULL)
 807                                 return (*f)(v, w);
 808                 }
 809                 result = binop_type_error(v, w, "+=");
 810         }
 811         return result;
 812 }
 813
 814 PyObject *
 815 PyNumber_InPlaceMultiply(PyObject *v, PyObject *w)
 816 {
 817         PyObject *result = binary_iop1(v, w, NB_SLOT(nb_inplace_multiply),
 818                                        NB_SLOT(nb_multiply));
 819         if (result == Py_NotImplemented) {
 820                 ssizeargfunc f = NULL;
 821                 PySequenceMethods *mv = v->ob_type->tp_as_sequence;
 822                 PySequenceMethods *mw = w->ob_type->tp_as_sequence;
 823                 Py_DECREF(result);
 824                 if (mv != NULL) {
 825                         if (HASINPLACE(v))
 826                                 f = mv->sq_inplace_repeat;
 827                         if (f == NULL)
 828                                 f = mv->sq_repeat;
 829                         if (f != NULL)
 830                                 return sequence_repeat(f, v, w);
 831                 }
 832                 else if (mw != NULL) {
 833                         /* Note that the right hand operand should not be
 834                          * mutated in this case so sq_inplace_repeat is not
 835                          * used. */
 836                         if (mw->sq_repeat)
 837                                 return sequence_repeat(mw->sq_repeat, w, v);
 838                 }
 839                 result = binop_type_error(v, w, "*=");
 840         }
 841         return result;
 842 }
 843
 844 PyObject *
 845 PyNumber_InPlaceRemainder(PyObject *v, PyObject *w)
 846 {
 847         return binary_iop(v, w, NB_SLOT(nb_inplace_remainder),
 848                                 NB_SLOT(nb_remainder), "%=");
 849 }
 850
 851 PyObject *
 852 PyNumber_InPlacePower(PyObject *v, PyObject *w, PyObject *z)
 853 {
 854         if (HASINPLACE(v) && v->ob_type->tp_as_number &&
 855             v->ob_type->tp_as_number->nb_inplace_power != NULL) {
 856                 return ternary_op(v, w, z, NB_SLOT(nb_inplace_power), "**=");
 857         }
 858         else {
 859                 return ternary_op(v, w, z, NB_SLOT(nb_power), "**=");
 860         }
 861 }
 862
 863
 864 /* Unary operators and functions */
 865
 866 PyObject *
 867 PyNumber_Negative(PyObject *o)
 868 {
 869         PyNumberMethods *m;
 870
 871         if (o == NULL)
 872                 return null_error();
 873         m = o->ob_type->tp_as_number;
 874         if (m && m->nb_negative)
 875                 return (*m->nb_negative)(o);
 876
 877         return type_error("bad operand type for unary -: '%.200s'", o);
 878 }
 879
 880 PyObject *
 881 PyNumber_Positive(PyObject *o)
 882 {
 883         PyNumberMethods *m;
 884
 885         if (o == NULL)
 886                 return null_error();
 887         m = o->ob_type->tp_as_number;
 888         if (m && m->nb_positive)
 889                 return (*m->nb_positive)(o);
 890
 891         return type_error("bad operand type for unary +: '%.200s'", o);
 892 }
 893
 894 PyObject *
 895 PyNumber_Invert(PyObject *o)
 896 {
 897         PyNumberMethods *m;
 898
 899         if (o == NULL)
 900                 return null_error();
 901         m = o->ob_type->tp_as_number;
 902         if (m && m->nb_invert)
 903                 return (*m->nb_invert)(o);
 904
 905         return type_error("bad operand type for unary ~: '%.200s'", o);
 906 }
 907
 908 PyObject *
 909 PyNumber_Absolute(PyObject *o)
 910 {
 911         PyNumberMethods *m;
 912
 913         if (o == NULL)
 914                 return null_error();
 915         m = o->ob_type->tp_as_number;
 916         if (m && m->nb_absolute)
 917                 return m->nb_absolute(o);
 918
 919         return type_error("bad operand type for abs(): '%.200s'", o);
 920 }
 921
 922 /* Add a check for embedded NULL-bytes in the argument. */
 923 static PyObject *
 924 int_from_string(const char *s, Py_ssize_t len)
 925 {
 926         char *end;
 927         PyObject *x;
 928
 929         x = PyInt_FromString((char*)s, &end, 10);
 930         if (x == NULL)
 931                 return NULL;
 932         if (end != s + len) {
 933                 PyErr_SetString(PyExc_ValueError,
 934                                 "null byte in argument for int()");
 935                 Py_DECREF(x);
 936                 return NULL;
 937         }
 938         return x;
 939 }
 940
 941 /* Return a Py_ssize_t integer from the object item */
 942 Py_ssize_t
 943 PyNumber_Index(PyObject *item)
 944 {
 945         Py_ssize_t value = -1;
 946         PyNumberMethods *nb = item->ob_type->tp_as_number;
 947         if (nb != NULL && HASINDEX(item) && nb->nb_index != NULL) {
 948                 value = nb->nb_index(item);
 949         }
 950         else {
 951                 PyErr_Format(PyExc_TypeError,
 952                              "'%.200s' object cannot be interpreted "
 953                              "as an index", item->ob_type->tp_name);
 954         }
 955         return value;
 956 }
 957
 958 PyObject *
 959 PyNumber_Int(PyObject *o)
 960 {
 961         PyNumberMethods *m;
 962         const char *buffer;
 963         Py_ssize_t buffer_len;
 964
 965         if (o == NULL)
 966                 return null_error();
 967         if (PyInt_CheckExact(o)) {
 968                 Py_INCREF(o);
 969                 return o;
 970         }
 971         m = o->ob_type->tp_as_number;
 972         if (m && m->nb_int) { /* This should include subclasses of int */
 973                 PyObject *res = m->nb_int(o);
 974                 if (res && (!PyInt_Check(res) && !PyLong_Check(res))) {
 975                         PyErr_Format(PyExc_TypeError,
 976                                      "__int__ returned non-int (type %.200s)",
 977                                      res->ob_type->tp_name);
 978                         Py_DECREF(res);
 979                         return NULL;
 980                 }
 981                 return res;
 982         }
 983         if (PyInt_Check(o)) { /* A int subclass without nb_int */
 984                 PyIntObject *io = (PyIntObject*)o;
 985                 return PyInt_FromLong(io->ob_ival);
 986         }
 987         if (PyString_Check(o))
 988                 return int_from_string(PyString_AS_STRING(o),
 989                                        PyString_GET_SIZE(o));
 990 #ifdef Py_USING_UNICODE
 991         if (PyUnicode_Check(o))
 992                 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(o),
 993                                          PyUnicode_GET_SIZE(o),
 994                                          10);
 995 #endif
 996         if (!PyObject_AsCharBuffer(o, &buffer, &buffer_len))
 997                 return int_from_string((char*)buffer, buffer_len);
 998
 999         return type_error("int() argument must be a string or a "
1000                           "number, not '%.200s'", o);
1001 }
1002
1003 /* Add a check for embedded NULL-bytes in the argument. */
1004 static PyObject *
1005 long_from_string(const char *s, Py_ssize_t len)
1006 {
1007         char *end;
1008         PyObject *x;
1009
1010         x = PyLong_FromString((char*)s, &end, 10);
1011         if (x == NULL)
1012                 return NULL;
1013         if (end != s + len) {
1014                 PyErr_SetString(PyExc_ValueError,
1015                                 "null byte in argument for long()");
1016                 Py_DECREF(x);
1017                 return NULL;
1018         }
1019         return x;
1020 }
1021
1022 PyObject *
1023 PyNumber_Long(PyObject *o)
1024 {
1025         PyNumberMethods *m;
1026         const char *buffer;
1027         Py_ssize_t buffer_len;
1028
1029         if (o == NULL)
1030                 return null_error();
1031         m = o->ob_type->tp_as_number;
1032         if (m && m->nb_long) { /* This should include subclasses of long */
1033                 PyObject *res = m->nb_long(o);
1034                 if (res && (!PyInt_Check(res) && !PyLong_Check(res))) {
1035                         PyErr_Format(PyExc_TypeError,
1036                                      "__long__ returned non-long (type %.200s)",
1037                                      res->ob_type->tp_name);
1038                         Py_DECREF(res);
1039                         return NULL;
1040                 }
1041                 return res;
1042         }
1043         if (PyLong_Check(o)) /* A long subclass without nb_long */
1044                 return _PyLong_Copy((PyLongObject *)o);
1045         if (PyString_Check(o))
1046                 /* need to do extra error checking that PyLong_FromString()
1047                  * doesn't do.  In particular long('9.5') must raise an
1048                  * exception, not truncate the float.
1049                  */
1050                 return long_from_string(PyString_AS_STRING(o),
1051                                         PyString_GET_SIZE(o));
1052 #ifdef Py_USING_UNICODE
1053         if (PyUnicode_Check(o))
1054                 /* The above check is done in PyLong_FromUnicode(). */
1055                 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(o),
1056                                           PyUnicode_GET_SIZE(o),
1057                                           10);
1058 #endif
1059         if (!PyObject_AsCharBuffer(o, &buffer, &buffer_len))
1060                 return long_from_string(buffer, buffer_len);
1061
1062         return type_error("long() argument must be a string or a "
1063                           "number, not '%.200s'", o);
1064 }
1065
1066 PyObject *
1067 PyNumber_Float(PyObject *o)
1068 {
1069         PyNumberMethods *m;
1070
1071         if (o == NULL)
1072                 return null_error();
1073         m = o->ob_type->tp_as_number;
1074         if (m && m->nb_float) { /* This should include subclasses of float */
1075                 PyObject *res = m->nb_float(o);
1076                 if (res && !PyFloat_Check(res)) {
1077                         PyErr_Format(PyExc_TypeError,
1078                           "__float__ returned non-float (type %.200s)",
1079                           res->ob_type->tp_name);
1080                         Py_DECREF(res);
1081                         return NULL;
1082                 }
1083                 return res;
1084         }
1085         if (PyFloat_Check(o)) { /* A float subclass with nb_float == NULL */
1086                 PyFloatObject *po = (PyFloatObject *)o;
1087                 return PyFloat_FromDouble(po->ob_fval);
1088         }
1089         return PyFloat_FromString(o, NULL);
1090 }
1091
1092 /* Operations on sequences */
1093
1094 int
1095 PySequence_Check(PyObject *s)
1096 {
1097         if (s && PyInstance_Check(s))
1098                 return PyObject_HasAttrString(s, "__getitem__");
1099         return s != NULL && s->ob_type->tp_as_sequence &&
1100                 s->ob_type->tp_as_sequence->sq_item != NULL;
1101 }
1102
1103 Py_ssize_t
1104 PySequence_Size(PyObject *s)
1105 {
1106         PySequenceMethods *m;
1107
1108         if (s == NULL) {
1109                 null_error();
1110                 return -1;
1111         }
1112
1113         m = s->ob_type->tp_as_sequence;
1114         if (m && m->sq_length)
1115                 return m->sq_length(s);
1116
1117         type_error("non-sequence object of type '%.200s' has no len()", s);
1118         return -1;
1119 }
1120
1121 #undef PySequence_Length
1122 Py_ssize_t
1123 PySequence_Length(PyObject *s)
1124 {
1125         return PySequence_Size(s);
1126 }
1127 #define PySequence_Length PySequence_Size
1128
1129 PyObject *
1130 PySequence_Concat(PyObject *s, PyObject *o)
1131 {
1132         PySequenceMethods *m;
1133
1134         if (s == NULL || o == NULL)
1135                 return null_error();
1136
1137         m = s->ob_type->tp_as_sequence;
1138         if (m && m->sq_concat)
1139                 return m->sq_concat(s, o);
1140
1141         /* Instances of user classes defining an __add__() method only
1142            have an nb_add slot, not an sq_concat slot.  So we fall back
1143            to nb_add if both arguments appear to be sequences. */
1144         if (PySequence_Check(s) && PySequence_Check(o)) {
1145                 PyObject *result = binary_op1(s, o, NB_SLOT(nb_add));
1146                 if (result != Py_NotImplemented)
1147                         return result;
1148                 Py_DECREF(result);
1149         }
1150         return type_error("'%.200s' object can't be concatenated", s);
1151 }
1152
1153 PyObject *
1154 PySequence_Repeat(PyObject *o, Py_ssize_t count)
1155 {
1156         PySequenceMethods *m;
1157
1158         if (o == NULL)
1159                 return null_error();
1160
1161         m = o->ob_type->tp_as_sequence;
1162         if (m && m->sq_repeat)
1163                 return m->sq_repeat(o, count);
1164
1165         /* Instances of user classes defining a __mul__() method only
1166            have an nb_multiply slot, not an sq_repeat slot. so we fall back
1167            to nb_multiply if o appears to be a sequence. */
1168         if (PySequence_Check(o)) {
1169                 PyObject *n, *result;
1170                 n = PyInt_FromSsize_t(count);
1171                 if (n == NULL)
1172                         return NULL;
1173                 result = binary_op1(o, n, NB_SLOT(nb_multiply));
1174                 Py_DECREF(n);
1175                 if (result != Py_NotImplemented)
1176                         return result;
1177                 Py_DECREF(result);
1178         }
1179         return type_error("'%.200s' object can't be repeated", o);
1180 }
1181
1182 PyObject *
1183 PySequence_InPlaceConcat(PyObject *s, PyObject *o)
1184 {
1185         PySequenceMethods *m;
1186
1187         if (s == NULL || o == NULL)
1188                 return null_error();
1189
1190         m = s->ob_type->tp_as_sequence;
1191         if (m && HASINPLACE(s) && m->sq_inplace_concat)
1192                 return m->sq_inplace_concat(s, o);
1193         if (m && m->sq_concat)
1194                 return m->sq_concat(s, o);
1195
1196         if (PySequence_Check(s) && PySequence_Check(o)) {
1197                 PyObject *result = binary_iop1(s, o, NB_SLOT(nb_inplace_add),
1198                                                NB_SLOT(nb_add));
1199                 if (result != Py_NotImplemented)
1200                         return result;
1201                 Py_DECREF(result);
1202         }
1203         return type_error("'%.200s' object can't be concatenated", s);
1204 }
1205
1206 PyObject *
1207 PySequence_InPlaceRepeat(PyObject *o, Py_ssize_t count)
1208 {
1209         PySequenceMethods *m;
1210
1211         if (o == NULL)
1212                 return null_error();
1213
1214         m = o->ob_type->tp_as_sequence;
1215         if (m && HASINPLACE(o) && m->sq_inplace_repeat)
1216                 return m->sq_inplace_repeat(o, count);
1217         if (m && m->sq_repeat)
1218                 return m->sq_repeat(o, count);
1219
1220         if (PySequence_Check(o)) {
1221                 PyObject *n, *result;
1222                 n = PyInt_FromSsize_t(count);
1223                 if (n == NULL)
1224                         return NULL;
1225                 result = binary_iop1(o, n, NB_SLOT(nb_inplace_multiply),
1226                                      NB_SLOT(nb_multiply));
1227                 Py_DECREF(n);
1228                 if (result != Py_NotImplemented)
1229                         return result;
1230                 Py_DECREF(result);
1231         }
1232         return type_error("'%.200s' object can't be repeated", o);
1233 }
1234
1235 PyObject *
1236 PySequence_GetItem(PyObject *s, Py_ssize_t i)
1237 {
1238         PySequenceMethods *m;
1239
1240         if (s == NULL)
1241                 return null_error();
1242
1243         m = s->ob_type->tp_as_sequence;
1244         if (m && m->sq_item) {
1245                 if (i < 0) {
1246                         if (m->sq_length) {
1247                                 Py_ssize_t l = (*m->sq_length)(s);
1248                                 if (l < 0)
1249                                         return NULL;
1250                                 i += l;
1251                         }
1252                 }
1253                 return m->sq_item(s, i);
1254         }
1255
1256         return type_error("'%.200s' object is unindexable", s);
1257 }
1258
1259 PyObject *
1260 PySequence_GetSlice(PyObject *s, Py_ssize_t i1, Py_ssize_t i2)
1261 {
1262         PySequenceMethods *m;
1263         PyMappingMethods *mp;
1264
1265         if (!s) return null_error();
1266
1267         m = s->ob_type->tp_as_sequence;
1268         if (m && m->sq_slice) {
1269                 if (i1 < 0 || i2 < 0) {
1270                         if (m->sq_length) {
1271                                 Py_ssize_t l = (*m->sq_length)(s);
1272                                 if (l < 0)
1273                                         return NULL;
1274                                 if (i1 < 0)
1275                                         i1 += l;
1276                                 if (i2 < 0)
1277                                         i2 += l;
1278                         }
1279                 }
1280                 return m->sq_slice(s, i1, i2);
1281         } else if ((mp = s->ob_type->tp_as_mapping) && mp->mp_subscript) {
1282                 PyObject *res;
1283                 PyObject *slice = _PySlice_FromIndices(i1, i2);
1284                 if (!slice)
1285                         return NULL;
1286                 res = mp->mp_subscript(s, slice);
1287                 Py_DECREF(slice);
1288                 return res;
1289         }
1290
1291         return type_error("'%.200s' object is unsliceable", s);
1292 }
1293
1294 int
1295 PySequence_SetItem(PyObject *s, Py_ssize_t i, PyObject *o)
1296 {
1297         PySequenceMethods *m;
1298
1299         if (s == NULL) {
1300                 null_error();
1301                 return -1;
1302         }
1303
1304         m = s->ob_type->tp_as_sequence;
1305         if (m && m->sq_ass_item) {
1306                 if (i < 0) {
1307                         if (m->sq_length) {
1308                                 Py_ssize_t l = (*m->sq_length)(s);
1309                                 if (l < 0)
1310                                         return -1;
1311                                 i += l;
1312                         }
1313                 }
1314                 return m->sq_ass_item(s, i, o);
1315         }
1316
1317         type_error("'%.200s' object does not support item assignment", s);
1318         return -1;
1319 }
1320
1321 int
1322 PySequence_DelItem(PyObject *s, Py_ssize_t i)
1323 {
1324         PySequenceMethods *m;
1325
1326         if (s == NULL) {
1327                 null_error();
1328                 return -1;
1329         }
1330
1331         m = s->ob_type->tp_as_sequence;
1332         if (m && m->sq_ass_item) {
1333                 if (i < 0) {
1334                         if (m->sq_length) {
1335                                 Py_ssize_t l = (*m->sq_length)(s);
1336                                 if (l < 0)
1337                                         return -1;
1338                                 i += l;
1339                         }
1340                 }
1341                 return m->sq_ass_item(s, i, (PyObject *)NULL);
1342         }
1343
1344         type_error("'%.200s' object doesn't support item deletion", s);
1345         return -1;
1346 }
1347
1348 int
1349 PySequence_SetSlice(PyObject *s, Py_ssize_t i1, Py_ssize_t i2, PyObject *o)
1350 {
1351         PySequenceMethods *m;
1352         PyMappingMethods *mp;
1353
1354         if (s == NULL) {
1355                 null_error();
1356                 return -1;
1357         }
1358
1359         m = s->ob_type->tp_as_sequence;
1360         if (m && m->sq_ass_slice) {
1361                 if (i1 < 0 || i2 < 0) {
1362                         if (m->sq_length) {
1363                                 Py_ssize_t l = (*m->sq_length)(s);
1364                                 if (l < 0)
1365                                         return -1;
1366                                 if (i1 < 0)
1367                                         i1 += l;
1368                                 if (i2 < 0)
1369                                         i2 += l;
1370                         }
1371                 }
1372                 return m->sq_ass_slice(s, i1, i2, o);
1373         } else if ((mp = s->ob_type->tp_as_mapping) && mp->mp_ass_subscript) {
1374                 int res;
1375                 PyObject *slice = _PySlice_FromIndices(i1, i2);
1376                 if (!slice)
1377                         return -1;
1378                 res = mp->mp_ass_subscript(s, slice, o);
1379                 Py_DECREF(slice);
1380                 return res;
1381         }
1382
1383         type_error("'%.200s' object doesn't support slice assignment", s);
1384         return -1;
1385 }
1386
1387 int
1388 PySequence_DelSlice(PyObject *s, Py_ssize_t i1, Py_ssize_t i2)
1389 {
1390         PySequenceMethods *m;
1391
1392         if (s == NULL) {
1393                 null_error();
1394                 return -1;
1395         }
1396
1397         m = s->ob_type->tp_as_sequence;
1398         if (m && m->sq_ass_slice) {
1399                 if (i1 < 0 || i2 < 0) {
1400                         if (m->sq_length) {
1401                                 Py_ssize_t l = (*m->sq_length)(s);
1402                                 if (l < 0)
1403                                         return -1;
1404                                 if (i1 < 0)
1405                                         i1 += l;
1406                                 if (i2 < 0)
1407                                         i2 += l;
1408                         }
1409                 }
1410                 return m->sq_ass_slice(s, i1, i2, (PyObject *)NULL);
1411         }
1412         type_error("'%.200s' object doesn't support slice deletion", s);
1413         return -1;
1414 }
1415
1416 PyObject *
1417 PySequence_Tuple(PyObject *v)
1418 {
1419         PyObject *it;  /* iter(v) */
1420         Py_ssize_t n;         /* guess for result tuple size */
1421         PyObject *result;
1422         Py_ssize_t j;
1423
1424         if (v == NULL)
1425                 return null_error();
1426
1427         /* Special-case the common tuple and list cases, for efficiency. */
1428         if (PyTuple_CheckExact(v)) {
1429                 /* Note that we can't know whether it's safe to return
1430                    a tuple *subclass* instance as-is, hence the restriction
1431                    to exact tuples here.  In contrast, lists always make
1432                    a copy, so there's no need for exactness below. */
1433                 Py_INCREF(v);
1434                 return v;
1435         }
1436         if (PyList_Check(v))
1437                 return PyList_AsTuple(v);
1438
1439         /* Get iterator. */
1440         it = PyObject_GetIter(v);
1441         if (it == NULL)
1442                 return NULL;
1443
1444         /* Guess result size and allocate space. */
1445         n = _PyObject_LengthHint(v);
1446         if (n < 0) {
1447                 if (!PyErr_ExceptionMatches(PyExc_TypeError)  &&
1448                     !PyErr_ExceptionMatches(PyExc_AttributeError)) {
1449                         Py_DECREF(it);
1450                         return NULL;
1451                 }
1452                 PyErr_Clear();
1453                 n = 10;  /* arbitrary */
1454         }
1455         result = PyTuple_New(n);
1456         if (result == NULL)
1457                 goto Fail;
1458
1459         /* Fill the tuple. */
1460         for (j = 0; ; ++j) {
1461                 PyObject *item = PyIter_Next(it);
1462                 if (item == NULL) {
1463                         if (PyErr_Occurred())
1464                                 goto Fail;
1465                         break;
1466                 }
1467                 if (j >= n) {
1468                         Py_ssize_t oldn = n;
1469                         /* The over-allocation strategy can grow a bit faster
1470                            than for lists because unlike lists the
1471                            over-allocation isn't permanent -- we reclaim
1472                            the excess before the end of this routine.
1473                            So, grow by ten and then add 25%.
1474                         */
1475                         n += 10;
1476                         n += n >> 2;
1477                         if (n < oldn) {
1478                                 /* Check for overflow */
1479                                 PyErr_NoMemory();
1480                                 Py_DECREF(item);
1481                                 goto Fail;
1482                         }
1483                         if (_PyTuple_Resize(&result, n) != 0) {
1484                                 Py_DECREF(item);
1485                                 goto Fail;
1486                         }
1487                 }
1488                 PyTuple_SET_ITEM(result, j, item);
1489         }
1490
1491         /* Cut tuple back if guess was too large. */
1492         if (j < n &&
1493             _PyTuple_Resize(&result, j) != 0)
1494                 goto Fail;
1495
1496         Py_DECREF(it);
1497         return result;
1498
1499 Fail:
1500         Py_XDECREF(result);
1501         Py_DECREF(it);
1502         return NULL;
1503 }
1504
1505 PyObject *
1506 PySequence_List(PyObject *v)
1507 {
1508         PyObject *result;  /* result list */
1509         PyObject *rv;      /* return value from PyList_Extend */
1510
1511         if (v == NULL)
1512                 return null_error();
1513
1514         result = PyList_New(0);
1515         if (result == NULL)
1516                 return NULL;
1517
1518         rv = _PyList_Extend((PyListObject *)result, v);
1519         if (rv == NULL) {
1520                 Py_DECREF(result);
1521                 return NULL;
1522         }
1523         Py_DECREF(rv);
1524         return result;
1525 }
1526
1527 PyObject *
1528 PySequence_Fast(PyObject *v, const char *m)
1529 {
1530         PyObject *it;
1531
1532         if (v == NULL)
1533                 return null_error();
1534
1535         if (PyList_CheckExact(v) || PyTuple_CheckExact(v)) {
1536                 Py_INCREF(v);
1537                 return v;
1538         }
1539
1540         it = PyObject_GetIter(v);
1541         if (it == NULL) {
1542                 if (PyErr_ExceptionMatches(PyExc_TypeError))
1543                         PyErr_SetString(PyExc_TypeError, m);
1544                 return NULL;
1545         }
1546
1547         v = PySequence_List(it);
1548         Py_DECREF(it);
1549
1550         return v;
1551 }
1552
1553 /* Iterate over seq.  Result depends on the operation:
1554    PY_ITERSEARCH_COUNT:  -1 if error, else # of times obj appears in seq.
1555    PY_ITERSEARCH_INDEX:  0-based index of first occurence of obj in seq;
1556         set ValueError and return -1 if none found; also return -1 on error.
1557    Py_ITERSEARCH_CONTAINS:  return 1 if obj in seq, else 0; -1 on error.
1558 */
1559 Py_ssize_t
1560 _PySequence_IterSearch(PyObject *seq, PyObject *obj, int operation)
1561 {
1562         Py_ssize_t n;
1563         int wrapped;  /* for PY_ITERSEARCH_INDEX, true iff n wrapped around */
1564         PyObject *it;  /* iter(seq) */
1565
1566         if (seq == NULL || obj == NULL) {
1567                 null_error();
1568                 return -1;
1569         }
1570
1571         it = PyObject_GetIter(seq);
1572         if (it == NULL) {
1573                 type_error("argument of type '%.200s' is not iterable", seq);
1574                 return -1;
1575         }
1576
1577         n = wrapped = 0;
1578         for (;;) {
1579                 int cmp;
1580                 PyObject *item = PyIter_Next(it);
1581                 if (item == NULL) {
1582                         if (PyErr_Occurred())
1583                                 goto Fail;
1584                         break;
1585                 }
1586
1587                 cmp = PyObject_RichCompareBool(obj, item, Py_EQ);
1588                 Py_DECREF(item);
1589                 if (cmp < 0)
1590                         goto Fail;
1591                 if (cmp > 0) {
1592                         switch (operation) {
1593                         case PY_ITERSEARCH_COUNT:
1594                                 ++n;
1595                                 if (n <= 0) {
1596                                         /* XXX(nnorwitz): int means ssize_t */
1597                                         PyErr_SetString(PyExc_OverflowError,
1598                                                 "count exceeds C int size");
1599                                         goto Fail;
1600                                 }
1601                                 break;
1602
1603                         case PY_ITERSEARCH_INDEX:
1604                                 if (wrapped) {
1605                                         /* XXX(nnorwitz): int means ssize_t */
1606                                         PyErr_SetString(PyExc_OverflowError,
1607                                                 "index exceeds C int size");
1608                                         goto Fail;
1609                                 }
1610                                 goto Done;
1611
1612                         case PY_ITERSEARCH_CONTAINS:
1613                                 n = 1;
1614                                 goto Done;
1615
1616                         default:
1617                                 assert(!"unknown operation");
1618                         }
1619                 }
1620
1621                 if (operation == PY_ITERSEARCH_INDEX) {
1622                         ++n;
1623                         if (n <= 0)
1624                                 wrapped = 1;
1625                 }
1626         }
1627
1628         if (operation != PY_ITERSEARCH_INDEX)
1629                 goto Done;
1630
1631         PyErr_SetString(PyExc_ValueError,
1632                         "sequence.index(x): x not in sequence");
1633         /* fall into failure code */
1634 Fail:
1635         n = -1;
1636         /* fall through */
1637 Done:
1638         Py_DECREF(it);
1639         return n;
1640
1641 }
1642
1643 /* Return # of times o appears in s. */
1644 Py_ssize_t
1645 PySequence_Count(PyObject *s, PyObject *o)
1646 {
1647         return _PySequence_IterSearch(s, o, PY_ITERSEARCH_COUNT);
1648 }
1649
1650 /* Return -1 if error; 1 if ob in seq; 0 if ob not in seq.
1651  * Use sq_contains if possible, else defer to _PySequence_IterSearch().
1652  */
1653 int
1654 PySequence_Contains(PyObject *seq, PyObject *ob)
1655 {
1656         Py_ssize_t result;
1657         if (PyType_HasFeature(seq->ob_type, Py_TPFLAGS_HAVE_SEQUENCE_IN)) {
1658                 PySequenceMethods *sqm = seq->ob_type->tp_as_sequence;
1659                 if (sqm != NULL && sqm->sq_contains != NULL)
1660                         return (*sqm->sq_contains)(seq, ob);
1661         }
1662         result = _PySequence_IterSearch(seq, ob, PY_ITERSEARCH_CONTAINS);
1663         return Py_SAFE_DOWNCAST(result, Py_ssize_t, int);
1664 }
1665
1666 /* Backwards compatibility */
1667 #undef PySequence_In
1668 int
1669 PySequence_In(PyObject *w, PyObject *v)
1670 {
1671         return PySequence_Contains(w, v);
1672 }
1673
1674 Py_ssize_t
1675 PySequence_Index(PyObject *s, PyObject *o)
1676 {
1677         return _PySequence_IterSearch(s, o, PY_ITERSEARCH_INDEX);
1678 }
1679
1680 /* Operations on mappings */
1681
1682 int
1683 PyMapping_Check(PyObject *o)
1684 {
1685         if (o && PyInstance_Check(o))
1686                 return PyObject_HasAttrString(o, "__getitem__");
1687
1688         return  o && o->ob_type->tp_as_mapping &&
1689                 o->ob_type->tp_as_mapping->mp_subscript &&
1690                 !(o->ob_type->tp_as_sequence &&
1691                   o->ob_type->tp_as_sequence->sq_slice);
1692 }
1693
1694 Py_ssize_t
1695 PyMapping_Size(PyObject *o)
1696 {
1697         PyMappingMethods *m;
1698
1699         if (o == NULL) {
1700                 null_error();
1701                 return -1;
1702         }
1703
1704         m = o->ob_type->tp_as_mapping;
1705         if (m && m->mp_length)
1706                 return m->mp_length(o);
1707
1708         type_error("non-mapping object of type '%.200s' has no len()", o);
1709         return -1;
1710 }
1711
1712 #undef PyMapping_Length
1713 Py_ssize_t
1714 PyMapping_Length(PyObject *o)
1715 {
1716         return PyMapping_Size(o);
1717 }
1718 #define PyMapping_Length PyMapping_Size
1719
1720 PyObject *
1721 PyMapping_GetItemString(PyObject *o, char *key)
1722 {
1723         PyObject *okey, *r;
1724
1725         if (key == NULL)
1726                 return null_error();
1727
1728         okey = PyString_FromString(key);
1729         if (okey == NULL)
1730                 return NULL;
1731         r = PyObject_GetItem(o, okey);
1732         Py_DECREF(okey);
1733         return r;
1734 }
1735
1736 int
1737 PyMapping_SetItemString(PyObject *o, char *key, PyObject *value)
1738 {
1739         PyObject *okey;
1740         int r;
1741
1742         if (key == NULL) {
1743                 null_error();
1744                 return -1;
1745         }
1746
1747         okey = PyString_FromString(key);
1748         if (okey == NULL)
1749                 return -1;
1750         r = PyObject_SetItem(o, okey, value);
1751         Py_DECREF(okey);
1752         return r;
1753 }
1754
1755 int
1756 PyMapping_HasKeyString(PyObject *o, char *key)
1757 {
1758         PyObject *v;
1759
1760         v = PyMapping_GetItemString(o, key);
1761         if (v) {
1762                 Py_DECREF(v);
1763                 return 1;
1764         }
1765         PyErr_Clear();
1766         return 0;
1767 }
1768
1769 int
1770 PyMapping_HasKey(PyObject *o, PyObject *key)
1771 {
1772         PyObject *v;
1773
1774         v = PyObject_GetItem(o, key);
1775         if (v) {
1776                 Py_DECREF(v);
1777                 return 1;
1778         }
1779         PyErr_Clear();
1780         return 0;
1781 }
1782
1783 /* Operations on callable objects */
1784
1785 /* XXX PyCallable_Check() is in object.c */
1786
1787 PyObject *
1788 PyObject_CallObject(PyObject *o, PyObject *a)
1789 {
1790         return PyEval_CallObjectWithKeywords(o, a, NULL);
1791 }
1792
1793 PyObject *
1794 PyObject_Call(PyObject *func, PyObject *arg, PyObject *kw)
1795 {
1796         ternaryfunc call;
1797
1798         if ((call = func->ob_type->tp_call) != NULL) {
1799                 PyObject *result = NULL;
1800                 /* slot_tp_call() will be called and ends up calling
1801                    PyObject_Call() if the object returned for __call__ has
1802                    __call__ itself defined upon it.  This can be an infinite
1803                    recursion if you set __call__ in a class to an instance of
1804                    it. */
1805                 if (Py_EnterRecursiveCall(" in __call__")) {
1806                     return NULL;
1807                 }
1808                 result = (*call)(func, arg, kw);
1809                 Py_LeaveRecursiveCall();
1810                 if (result == NULL && !PyErr_Occurred())
1811                         PyErr_SetString(
1812                                 PyExc_SystemError,
1813                                 "NULL result without error in PyObject_Call");
1814                 return result;
1815         }
1816         PyErr_Format(PyExc_TypeError, "'%.200s' object is not callable",
1817                      func->ob_type->tp_name);
1818         return NULL;
1819 }
1820
1821 static PyObject*
1822 call_function_tail(PyObject *callable, PyObject *args)
1823 {
1824         PyObject *retval;
1825
1826         if (args == NULL)
1827                 return NULL;
1828
1829         if (!PyTuple_Check(args)) {
1830                 PyObject *a;
1831
1832                 a = PyTuple_New(1);
1833                 if (a == NULL) {
1834                         Py_DECREF(args);
1835                         return NULL;
1836                 }
1837                 PyTuple_SET_ITEM(a, 0, args);
1838                 args = a;
1839         }
1840         retval = PyObject_Call(callable, args, NULL);
1841
1842         Py_DECREF(args);
1843
1844         return retval;
1845 }
1846
1847 PyObject *
1848 PyObject_CallFunction(PyObject *callable, char *format, ...)
1849 {
1850         va_list va;
1851         PyObject *args;
1852
1853         if (callable == NULL)
1854                 return null_error();
1855
1856         if (format && *format) {
1857                 va_start(va, format);
1858                 args = Py_VaBuildValue(format, va);
1859                 va_end(va);
1860         }
1861         else
1862                 args = PyTuple_New(0);
1863
1864         return call_function_tail(callable, args);
1865 }
1866
1867 PyObject *
1868 _PyObject_CallFunction_SizeT(PyObject *callable, char *format, ...)
1869 {
1870         va_list va;
1871         PyObject *args;
1872
1873         if (callable == NULL)
1874                 return null_error();
1875
1876         if (format && *format) {
1877                 va_start(va, format);
1878                 args = _Py_VaBuildValue_SizeT(format, va);
1879                 va_end(va);
1880         }
1881         else
1882                 args = PyTuple_New(0);
1883
1884         return call_function_tail(callable, args);
1885 }
1886
1887 PyObject *
1888 PyObject_CallMethod(PyObject *o, char *name, char *format, ...)
1889 {
1890         va_list va;
1891         PyObject *args;
1892         PyObject *func = NULL;
1893         PyObject *retval = NULL;
1894
1895         if (o == NULL || name == NULL)
1896                 return null_error();
1897
1898         func = PyObject_GetAttrString(o, name);
1899         if (func == NULL) {
1900                 PyErr_SetString(PyExc_AttributeError, name);
1901                 return 0;
1902         }
1903
1904         if (!PyCallable_Check(func)) {
1905                 type_error("attribute of type '%.200s' is not callable", func);
1906                 goto exit;
1907         }
1908
1909         if (format && *format) {
1910                 va_start(va, format);
1911                 args = Py_VaBuildValue(format, va);
1912                 va_end(va);
1913         }
1914         else
1915                 args = PyTuple_New(0);
1916
1917         retval = call_function_tail(func, args);
1918
1919   exit:
1920         /* args gets consumed in call_function_tail */
1921         Py_XDECREF(func);
1922
1923         return retval;
1924 }
1925
1926 PyObject *
1927 _PyObject_CallMethod_SizeT(PyObject *o, char *name, char *format, ...)
1928 {
1929         va_list va;
1930         PyObject *args;
1931         PyObject *func = NULL;
1932         PyObject *retval = NULL;
1933
1934         if (o == NULL || name == NULL)
1935                 return null_error();
1936
1937         func = PyObject_GetAttrString(o, name);
1938         if (func == NULL) {
1939                 PyErr_SetString(PyExc_AttributeError, name);
1940                 return 0;
1941         }
1942
1943         if (!PyCallable_Check(func)) {
1944                 type_error("attribute of type '%.200s' is not callable", func);
1945                 goto exit;
1946         }
1947
1948         if (format && *format) {
1949                 va_start(va, format);
1950                 args = _Py_VaBuildValue_SizeT(format, va);
1951                 va_end(va);
1952         }
1953         else
1954                 args = PyTuple_New(0);
1955
1956         retval = call_function_tail(func, args);
1957
1958   exit:
1959         /* args gets consumed in call_function_tail */
1960         Py_XDECREF(func);
1961
1962         return retval;
1963 }
1964
1965
1966 static PyObject *
1967 objargs_mktuple(va_list va)
1968 {
1969         int i, n = 0;
1970         va_list countva;
1971         PyObject *result, *tmp;
1972
1973 #ifdef VA_LIST_IS_ARRAY
1974         memcpy(countva, va, sizeof(va_list));
1975 #else
1976 #ifdef __va_copy
1977         __va_copy(countva, va);
1978 #else
1979         countva = va;
1980 #endif
1981 #endif
1982
1983         while (((PyObject *)va_arg(countva, PyObject *)) != NULL)
1984                 ++n;
1985         result = PyTuple_New(n);
1986         if (result != NULL && n > 0) {
1987                 for (i = 0; i < n; ++i) {
1988                         tmp = (PyObject *)va_arg(va, PyObject *);
1989                         PyTuple_SET_ITEM(result, i, tmp);
1990                         Py_INCREF(tmp);
1991                 }
1992         }
1993         return result;
1994 }
1995
1996 PyObject *
1997 PyObject_CallMethodObjArgs(PyObject *callable, PyObject *name, ...)
1998 {
1999         PyObject *args, *tmp;
2000         va_list vargs;
2001
2002         if (callable == NULL || name == NULL)
2003                 return null_error();
2004
2005         callable = PyObject_GetAttr(callable, name);
2006         if (callable == NULL)
2007                 return NULL;
2008
2009         /* count the args */
2010         va_start(vargs, name);
2011         args = objargs_mktuple(vargs);
2012         va_end(vargs);
2013         if (args == NULL) {
2014                 Py_DECREF(callable);
2015                 return NULL;
2016         }
2017         tmp = PyObject_Call(callable, args, NULL);
2018         Py_DECREF(args);
2019         Py_DECREF(callable);
2020
2021         return tmp;
2022 }
2023
2024 PyObject *
2025 PyObject_CallFunctionObjArgs(PyObject *callable, ...)
2026 {
2027         PyObject *args, *tmp;
2028         va_list vargs;
2029
2030         if (callable == NULL)
2031                 return null_error();
2032
2033         /* count the args */
2034         va_start(vargs, callable);
2035         args = objargs_mktuple(vargs);
2036         va_end(vargs);
2037         if (args == NULL)
2038                 return NULL;
2039         tmp = PyObject_Call(callable, args, NULL);
2040         Py_DECREF(args);
2041
2042         return tmp;
2043 }
2044
2045
2046 /* isinstance(), issubclass() */
2047
2048 /* abstract_get_bases() has logically 4 return states, with a sort of 0th
2049  * state that will almost never happen.
2050  *
2051  * 0. creating the __bases__ static string could get a MemoryError
2052  * 1. getattr(cls, '__bases__') could raise an AttributeError
2053  * 2. getattr(cls, '__bases__') could raise some other exception
2054  * 3. getattr(cls, '__bases__') could return a tuple
2055  * 4. getattr(cls, '__bases__') could return something other than a tuple
2056  *
2057  * Only state #3 is a non-error state and only it returns a non-NULL object
2058  * (it returns the retrieved tuple).
2059  *
2060  * Any raised AttributeErrors are masked by clearing the exception and
2061  * returning NULL.  If an object other than a tuple comes out of __bases__,
2062  * then again, the return value is NULL.  So yes, these two situations
2063  * produce exactly the same results: NULL is returned and no error is set.
2064  *
2065  * If some exception other than AttributeError is raised, then NULL is also
2066  * returned, but the exception is not cleared.  That's because we want the
2067  * exception to be propagated along.
2068  *
2069  * Callers are expected to test for PyErr_Occurred() when the return value
2070  * is NULL to decide whether a valid exception should be propagated or not.
2071  * When there's no exception to propagate, it's customary for the caller to
2072  * set a TypeError.
2073  */
2074 static PyObject *
2075 abstract_get_bases(PyObject *cls)
2076 {
2077         static PyObject *__bases__ = NULL;
2078         PyObject *bases;
2079
2080         if (__bases__ == NULL) {
2081                 __bases__ = PyString_FromString("__bases__");
2082                 if (__bases__ == NULL)
2083                         return NULL;
2084         }
2085         bases = PyObject_GetAttr(cls, __bases__);
2086         if (bases == NULL) {
2087                 if (PyErr_ExceptionMatches(PyExc_AttributeError))
2088                         PyErr_Clear();
2089                 return NULL;
2090         }
2091         if (!PyTuple_Check(bases)) {
2092                 Py_DECREF(bases);
2093                 return NULL;
2094         }
2095         return bases;
2096 }
2097
2098
2099 static int
2100 abstract_issubclass(PyObject *derived, PyObject *cls)
2101 {
2102         PyObject *bases;
2103         Py_ssize_t i, n;
2104         int r = 0;
2105
2106
2107         if (derived == cls)
2108                 return 1;
2109
2110         if (PyTuple_Check(cls)) {
2111                 /* Not a general sequence -- that opens up the road to
2112                    recursion and stack overflow. */
2113                 n = PyTuple_GET_SIZE(cls);
2114                 for (i = 0; i < n; i++) {
2115                         if (derived == PyTuple_GET_ITEM(cls, i))
2116                                 return 1;
2117                 }
2118         }
2119         bases = abstract_get_bases(derived);
2120         if (bases == NULL) {
2121                 if (PyErr_Occurred())
2122                         return -1;
2123                 return 0;
2124         }
2125         n = PyTuple_GET_SIZE(bases);
2126         for (i = 0; i < n; i++) {
2127                 r = abstract_issubclass(PyTuple_GET_ITEM(bases, i), cls);
2128                 if (r != 0)
2129                         break;
2130         }
2131
2132         Py_DECREF(bases);
2133
2134         return r;
2135 }
2136
2137 static int
2138 check_class(PyObject *cls, const char *error)
2139 {
2140         PyObject *bases = abstract_get_bases(cls);
2141         if (bases == NULL) {
2142                 /* Do not mask errors. */
2143                 if (!PyErr_Occurred())
2144                         PyErr_SetString(PyExc_TypeError, error);
2145                 return 0;
2146         }
2147         Py_DECREF(bases);
2148         return -1;
2149 }
2150
2151 static int
2152 recursive_isinstance(PyObject *inst, PyObject *cls, int recursion_depth)
2153 {
2154         PyObject *icls;
2155         static PyObject *__class__ = NULL;
2156         int retval = 0;
2157
2158         if (__class__ == NULL) {
2159                 __class__ = PyString_FromString("__class__");
2160                 if (__class__ == NULL)
2161                         return -1;
2162         }
2163
2164         if (PyClass_Check(cls) && PyInstance_Check(inst)) {
2165                 PyObject *inclass =
2166                         (PyObject*)((PyInstanceObject*)inst)->in_class;
2167                 retval = PyClass_IsSubclass(inclass, cls);
2168         }
2169         else if (PyType_Check(cls)) {
2170                 retval = PyObject_TypeCheck(inst, (PyTypeObject *)cls);
2171                 if (retval == 0) {
2172                         PyObject *c = PyObject_GetAttr(inst, __class__);
2173                         if (c == NULL) {
2174                                 PyErr_Clear();
2175                         }
2176                         else {
2177                                 if (c != (PyObject *)(inst->ob_type) &&
2178                                     PyType_Check(c))
2179                                         retval = PyType_IsSubtype(
2180                                                 (PyTypeObject *)c,
2181                                                 (PyTypeObject *)cls);
2182                                 Py_DECREF(c);
2183                         }
2184                 }
2185         }
2186         else if (PyTuple_Check(cls)) {
2187                 Py_ssize_t i, n;
2188
2189                 if (!recursion_depth) {
2190                     PyErr_SetString(PyExc_RuntimeError,
2191                                     "nest level of tuple too deep");
2192                     return -1;
2193                 }
2194
2195                 n = PyTuple_GET_SIZE(cls);
2196                 for (i = 0; i < n; i++) {
2197                         retval = recursive_isinstance(
2198                                     inst,
2199                                     PyTuple_GET_ITEM(cls, i),
2200                                     recursion_depth-1);
2201                         if (retval != 0)
2202                                 break;
2203                 }
2204         }
2205         else {
2206                 if (!check_class(cls,
2207                         "isinstance() arg 2 must be a class, type,"
2208                         " or tuple of classes and types"))
2209                         return -1;
2210                 icls = PyObject_GetAttr(inst, __class__);
2211                 if (icls == NULL) {
2212                         PyErr_Clear();
2213                         retval = 0;
2214                 }
2215                 else {
2216                         retval = abstract_issubclass(icls, cls);
2217                         Py_DECREF(icls);
2218                 }
2219         }
2220
2221         return retval;
2222 }
2223
2224 int
2225 PyObject_IsInstance(PyObject *inst, PyObject *cls)
2226 {
2227     return recursive_isinstance(inst, cls, Py_GetRecursionLimit());
2228 }
2229
2230 static  int
2231 recursive_issubclass(PyObject *derived, PyObject *cls, int recursion_depth)
2232 {
2233         int retval;
2234
2235         if (!PyClass_Check(derived) || !PyClass_Check(cls)) {
2236                 if (!check_class(derived,
2237                                  "issubclass() arg 1 must be a class"))
2238                         return -1;
2239
2240                 if (PyTuple_Check(cls)) {
2241                         Py_ssize_t i;
2242                         Py_ssize_t n = PyTuple_GET_SIZE(cls);
2243
2244                         if (!recursion_depth) {
2245                             PyErr_SetString(PyExc_RuntimeError,
2246                                             "nest level of tuple too deep");
2247                             return -1;
2248                         }
2249                         for (i = 0; i < n; ++i) {
2250                                 retval = recursive_issubclass(
2251                                             derived,
2252                                             PyTuple_GET_ITEM(cls, i),
2253                                             recursion_depth-1);
2254                                 if (retval != 0) {
2255                                         /* either found it, or got an error */
2256                                         return retval;
2257                                 }
2258                         }
2259                         return 0;
2260                 }
2261                 else {
2262                         if (!check_class(cls,
2263                                         "issubclass() arg 2 must be a class"
2264                                         " or tuple of classes"))
2265                                 return -1;
2266                 }
2267
2268                 retval = abstract_issubclass(derived, cls);
2269         }
2270         else {
2271                 /* shortcut */
2272                 if (!(retval = (derived == cls)))
2273                         retval = PyClass_IsSubclass(derived, cls);
2274         }
2275
2276         return retval;
2277 }
2278
2279 int
2280 PyObject_IsSubclass(PyObject *derived, PyObject *cls)
2281 {
2282     return recursive_issubclass(derived, cls, Py_GetRecursionLimit());
2283 }
2284
2285
2286 PyObject *
2287 PyObject_GetIter(PyObject *o)
2288 {
2289         PyTypeObject *t = o->ob_type;
2290         getiterfunc f = NULL;
2291         if (PyType_HasFeature(t, Py_TPFLAGS_HAVE_ITER))
2292                 f = t->tp_iter;
2293         if (f == NULL) {
2294                 if (PySequence_Check(o))
2295                         return PySeqIter_New(o);
2296                 return type_error("'%.200s' object is not iterable", o);
2297         }
2298         else {
2299                 PyObject *res = (*f)(o);
2300                 if (res != NULL && !PyIter_Check(res)) {
2301                         PyErr_Format(PyExc_TypeError,
2302                                      "iter() returned non-iterator "
2303                                      "of type '%.100s'",
2304                                      res->ob_type->tp_name);
2305                         Py_DECREF(res);
2306                         res = NULL;
2307                 }
2308                 return res;
2309         }
2310 }
2311
2312 /* Return next item.
2313  * If an error occurs, return NULL.  PyErr_Occurred() will be true.
2314  * If the iteration terminates normally, return NULL and clear the
2315  * PyExc_StopIteration exception (if it was set).  PyErr_Occurred()
2316  * will be false.
2317  * Else return the next object.  PyErr_Occurred() will be false.
2318  */
2319 PyObject *
2320 PyIter_Next(PyObject *iter)
2321 {
2322         PyObject *result;
2323         assert(PyIter_Check(iter));
2324         result = (*iter->ob_type->tp_iternext)(iter);
2325         if (result == NULL &&
2326             PyErr_Occurred() &&
2327             PyErr_ExceptionMatches(PyExc_StopIteration))
2328                 PyErr_Clear();
2329         return result;
2330 }