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 /* Shorthands to return certain errors */
  12
  13 static PyObject *
  14 type_error(const char *msg)
  15 {
  16         PyErr_SetString(PyExc_TypeError, msg);
  17         return NULL;
  18 }
  19
  20 static PyObject *
  21 null_error(void)
  22 {
  23         if (!PyErr_Occurred())
  24                 PyErr_SetString(PyExc_SystemError,
  25                                 "null argument to internal routine");
  26         return NULL;
  27 }
  28
  29 /* Operations on any object */
  30
  31 int
  32 PyObject_Cmp(PyObject *o1, PyObject *o2, int *result)
  33 {
  34         int r;
  35
  36         if (o1 == NULL || o2 == NULL) {
  37                 null_error();
  38                 return -1;
  39         }
  40         r = PyObject_Compare(o1, o2);
  41         if (PyErr_Occurred())
  42                 return -1;
  43         *result = r;
  44         return 0;
  45 }
  46
  47 PyObject *
  48 PyObject_Type(PyObject *o)
  49 {
  50         PyObject *v;
  51
  52         if (o == NULL)
  53                 return null_error();
  54         v = (PyObject *)o->ob_type;
  55         Py_INCREF(v);
  56         return v;
  57 }
  58
  59 int
  60 PyObject_Size(PyObject *o)
  61 {
  62         PySequenceMethods *m;
  63
  64         if (o == NULL) {
  65                 null_error();
  66                 return -1;
  67         }
  68
  69         m = o->ob_type->tp_as_sequence;
  70         if (m && m->sq_length)
  71                 return m->sq_length(o);
  72
  73         return PyMapping_Size(o);
  74 }
  75
  76 #undef PyObject_Length
  77 int
  78 PyObject_Length(PyObject *o)
  79 {
  80         return PyObject_Size(o);
  81 }
  82 #define PyObject_Length PyObject_Size
  83
  84 PyObject *
  85 PyObject_GetItem(PyObject *o, PyObject *key)
  86 {
  87         PyMappingMethods *m;
  88
  89         if (o == NULL || key == NULL)
  90                 return null_error();
  91
  92         m = o->ob_type->tp_as_mapping;
  93         if (m && m->mp_subscript)
  94                 return m->mp_subscript(o, key);
  95
  96         if (o->ob_type->tp_as_sequence) {
  97                 if (PyInt_Check(key))
  98                         return PySequence_GetItem(o, PyInt_AsLong(key));
  99                 else if (PyLong_Check(key)) {
 100                         long key_value = PyLong_AsLong(key);
 101                         if (key_value == -1 && PyErr_Occurred())
 102                                 return NULL;
 103                         return PySequence_GetItem(o, key_value);
 104                 }
 105                 else if (o->ob_type->tp_as_sequence->sq_item)
 106                         return type_error("sequence index must be integer");
 107         }
 108
 109         return type_error("unsubscriptable object");
 110 }
 111
 112 int
 113 PyObject_SetItem(PyObject *o, PyObject *key, PyObject *value)
 114 {
 115         PyMappingMethods *m;
 116
 117         if (o == NULL || key == NULL || value == NULL) {
 118                 null_error();
 119                 return -1;
 120         }
 121         m = o->ob_type->tp_as_mapping;
 122         if (m && m->mp_ass_subscript)
 123                 return m->mp_ass_subscript(o, key, value);
 124
 125         if (o->ob_type->tp_as_sequence) {
 126                 if (PyInt_Check(key))
 127                         return PySequence_SetItem(o, PyInt_AsLong(key), value);
 128                 else if (PyLong_Check(key)) {
 129                         long key_value = PyLong_AsLong(key);
 130                         if (key_value == -1 && PyErr_Occurred())
 131                                 return -1;
 132                         return PySequence_SetItem(o, key_value, value);
 133                 }
 134                 else if (o->ob_type->tp_as_sequence->sq_ass_item) {
 135                         type_error("sequence index must be integer");
 136                         return -1;
 137                 }
 138         }
 139
 140         type_error("object does not support item assignment");
 141         return -1;
 142 }
 143
 144 int
 145 PyObject_DelItem(PyObject *o, PyObject *key)
 146 {
 147         PyMappingMethods *m;
 148
 149         if (o == NULL || key == NULL) {
 150                 null_error();
 151                 return -1;
 152         }
 153         m = o->ob_type->tp_as_mapping;
 154         if (m && m->mp_ass_subscript)
 155                 return m->mp_ass_subscript(o, key, (PyObject*)NULL);
 156
 157         if (o->ob_type->tp_as_sequence) {
 158                 if (PyInt_Check(key))
 159                         return PySequence_DelItem(o, PyInt_AsLong(key));
 160                 else if (PyLong_Check(key)) {
 161                         long key_value = PyLong_AsLong(key);
 162                         if (key_value == -1 && PyErr_Occurred())
 163                                 return -1;
 164                         return PySequence_DelItem(o, key_value);
 165                 }
 166                 else if (o->ob_type->tp_as_sequence->sq_ass_item) {
 167                         type_error("sequence index must be integer");
 168                         return -1;
 169                 }
 170         }
 171
 172         type_error("object does not support item deletion");
 173         return -1;
 174 }
 175
 176 int
 177 PyObject_DelItemString(PyObject *o, char *key)
 178 {
 179         PyObject *okey;
 180         int ret;
 181
 182         if (o == NULL || key == NULL) {
 183                 null_error();
 184                 return -1;
 185         }
 186         okey = PyString_FromString(key);
 187         if (okey == NULL)
 188                 return -1;
 189         ret = PyObject_DelItem(o, okey);
 190         Py_DECREF(okey);
 191         return ret;
 192 }
 193
 194 int PyObject_AsCharBuffer(PyObject *obj,
 195                           const char **buffer,
 196                           int *buffer_len)
 197 {
 198         PyBufferProcs *pb;
 199         const char *pp;
 200         int len;
 201
 202         if (obj == NULL || buffer == NULL || buffer_len == NULL) {
 203                 null_error();
 204                 return -1;
 205         }
 206         pb = obj->ob_type->tp_as_buffer;
 207         if (pb == NULL ||
 208              pb->bf_getcharbuffer == NULL ||
 209              pb->bf_getsegcount == NULL) {
 210                 PyErr_SetString(PyExc_TypeError,
 211                                 "expected a character buffer object");
 212                 return -1;
 213         }
 214         if ((*pb->bf_getsegcount)(obj,NULL) != 1) {
 215                 PyErr_SetString(PyExc_TypeError,
 216                                 "expected a single-segment buffer object");
 217                 return -1;
 218         }
 219         len = (*pb->bf_getcharbuffer)(obj, 0, &pp);
 220         if (len < 0)
 221                 return -1;
 222         *buffer = pp;
 223         *buffer_len = len;
 224         return 0;
 225 }
 226
 227 int
 228 PyObject_CheckReadBuffer(PyObject *obj)
 229 {
 230         PyBufferProcs *pb = obj->ob_type->tp_as_buffer;
 231
 232         if (pb == NULL ||
 233             pb->bf_getreadbuffer == NULL ||
 234             pb->bf_getsegcount == NULL ||
 235             (*pb->bf_getsegcount)(obj, NULL) != 1)
 236                 return 0;
 237         return 1;
 238 }
 239
 240 int PyObject_AsReadBuffer(PyObject *obj,
 241                           const void **buffer,
 242                           int *buffer_len)
 243 {
 244         PyBufferProcs *pb;
 245         void *pp;
 246         int len;
 247
 248         if (obj == NULL || buffer == NULL || buffer_len == NULL) {
 249                 null_error();
 250                 return -1;
 251         }
 252         pb = obj->ob_type->tp_as_buffer;
 253         if (pb == NULL ||
 254              pb->bf_getreadbuffer == NULL ||
 255              pb->bf_getsegcount == NULL) {
 256                 PyErr_SetString(PyExc_TypeError,
 257                                 "expected a readable buffer object");
 258                 return -1;
 259         }
 260         if ((*pb->bf_getsegcount)(obj, NULL) != 1) {
 261                 PyErr_SetString(PyExc_TypeError,
 262                                 "expected a single-segment buffer object");
 263                 return -1;
 264         }
 265         len = (*pb->bf_getreadbuffer)(obj, 0, &pp);
 266         if (len < 0)
 267                 return -1;
 268         *buffer = pp;
 269         *buffer_len = len;
 270         return 0;
 271 }
 272
 273 int PyObject_AsWriteBuffer(PyObject *obj,
 274                            void **buffer,
 275                            int *buffer_len)
 276 {
 277         PyBufferProcs *pb;
 278         void*pp;
 279         int len;
 280
 281         if (obj == NULL || buffer == NULL || buffer_len == NULL) {
 282                 null_error();
 283                 return -1;
 284         }
 285         pb = obj->ob_type->tp_as_buffer;
 286         if (pb == NULL ||
 287              pb->bf_getwritebuffer == NULL ||
 288              pb->bf_getsegcount == NULL) {
 289                 PyErr_SetString(PyExc_TypeError,
 290                                 "expected a writeable buffer object");
 291                 return -1;
 292         }
 293         if ((*pb->bf_getsegcount)(obj, NULL) != 1) {
 294                 PyErr_SetString(PyExc_TypeError,
 295                                 "expected a single-segment buffer object");
 296                 return -1;
 297         }
 298         len = (*pb->bf_getwritebuffer)(obj,0,&pp);
 299         if (len < 0)
 300                 return -1;
 301         *buffer = pp;
 302         *buffer_len = len;
 303         return 0;
 304 }
 305
 306 /* Operations on numbers */
 307
 308 int
 309 PyNumber_Check(PyObject *o)
 310 {
 311         return o && o->ob_type->tp_as_number &&
 312                (o->ob_type->tp_as_number->nb_int ||
 313                 o->ob_type->tp_as_number->nb_float);
 314 }
 315
 316 /* Binary operators */
 317
 318 /* New style number protocol support */
 319
 320 #define NB_SLOT(x) offsetof(PyNumberMethods, x)
 321 #define NB_BINOP(nb_methods, slot) \
 322                 (*(binaryfunc*)(& ((char*)nb_methods)[slot]))
 323 #define NB_TERNOP(nb_methods, slot) \
 324                 (*(ternaryfunc*)(& ((char*)nb_methods)[slot]))
 325
 326 /*
 327   Calling scheme used for binary operations:
 328
 329   v     w       Action
 330   -------------------------------------------------------------------
 331   new   new     w.op(v,w)[*], v.op(v,w), w.op(v,w)
 332   new   old     v.op(v,w), coerce(v,w), v.op(v,w)
 333   old   new     w.op(v,w), coerce(v,w), v.op(v,w)
 334   old   old     coerce(v,w), v.op(v,w)
 335
 336   [*] only when v->ob_type != w->ob_type && w->ob_type is a subclass of
 337       v->ob_type
 338
 339   Legend:
 340   -------
 341   * new == new style number
 342   * old == old style number
 343   * Action indicates the order in which operations are tried until either
 344     a valid result is produced or an error occurs.
 345
 346  */
 347
 348 static PyObject *
 349 binary_op1(PyObject *v, PyObject *w, const int op_slot)
 350 {
 351         PyObject *x;
 352         binaryfunc slotv = NULL;
 353         binaryfunc slotw = NULL;
 354
 355         if (v->ob_type->tp_as_number != NULL && NEW_STYLE_NUMBER(v))
 356                 slotv = NB_BINOP(v->ob_type->tp_as_number, op_slot);
 357         if (w->ob_type != v->ob_type &&
 358             w->ob_type->tp_as_number != NULL && NEW_STYLE_NUMBER(w)) {
 359                 slotw = NB_BINOP(w->ob_type->tp_as_number, op_slot);
 360                 if (slotw == slotv)
 361                         slotw = NULL;
 362         }
 363         if (slotv) {
 364                 if (slotw && PyType_IsSubtype(w->ob_type, v->ob_type)) {
 365                         x = slotw(v, w);
 366                         if (x != Py_NotImplemented)
 367                                 return x;
 368                         Py_DECREF(x); /* can't do it */
 369                         slotw = NULL;
 370                 }
 371                 x = slotv(v, w);
 372                 if (x != Py_NotImplemented)
 373                         return x;
 374                 Py_DECREF(x); /* can't do it */
 375         }
 376         if (slotw) {
 377                 x = slotw(v, w);
 378                 if (x != Py_NotImplemented)
 379                         return x;
 380                 Py_DECREF(x); /* can't do it */
 381         }
 382         if (!NEW_STYLE_NUMBER(v) || !NEW_STYLE_NUMBER(w)) {
 383                 int err = PyNumber_CoerceEx(&v, &w);
 384                 if (err < 0) {
 385                         return NULL;
 386                 }
 387                 if (err == 0) {
 388                         PyNumberMethods *mv = v->ob_type->tp_as_number;
 389                         if (mv) {
 390                                 binaryfunc slot;
 391                                 slot = NB_BINOP(mv, op_slot);
 392                                 if (slot) {
 393                                         PyObject *x = slot(v, w);
 394                                         Py_DECREF(v);
 395                                         Py_DECREF(w);
 396                                         return x;
 397                                 }
 398                         }
 399                         /* CoerceEx incremented the reference counts */
 400                         Py_DECREF(v);
 401                         Py_DECREF(w);
 402                 }
 403         }
 404         Py_INCREF(Py_NotImplemented);
 405         return Py_NotImplemented;
 406 }
 407
 408 static PyObject *
 409 binop_type_error(PyObject *v, PyObject *w, const char *op_name)
 410 {
 411         PyErr_Format(PyExc_TypeError,
 412                      "unsupported operand type(s) for %s: '%s' and '%s'",
 413                      op_name,
 414                      v->ob_type->tp_name,
 415                      w->ob_type->tp_name);
 416         return NULL;
 417 }
 418
 419 static PyObject *
 420 binary_op(PyObject *v, PyObject *w, const int op_slot, const char *op_name)
 421 {
 422         PyObject *result = binary_op1(v, w, op_slot);
 423         if (result == Py_NotImplemented) {
 424                 Py_DECREF(result);
 425                 return binop_type_error(v, w, op_name);
 426         }
 427         return result;
 428 }
 429
 430
 431 /*
 432   Calling scheme used for ternary operations:
 433
 434   *** In some cases, w.op is called before v.op; see binary_op1. ***
 435
 436   v     w       z       Action
 437   -------------------------------------------------------------------
 438   new   new     new     v.op(v,w,z), w.op(v,w,z), z.op(v,w,z)
 439   new   old     new     v.op(v,w,z), z.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 440   old   new     new     w.op(v,w,z), z.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 441   old   old     new     z.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 442   new   new     old     v.op(v,w,z), w.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 443   new   old     old     v.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 444   old   new     old     w.op(v,w,z), coerce(v,w,z), v.op(v,w,z)
 445   old   old     old     coerce(v,w,z), v.op(v,w,z)
 446
 447   Legend:
 448   -------
 449   * new == new style number
 450   * old == old style number
 451   * Action indicates the order in which operations are tried until either
 452     a valid result is produced or an error occurs.
 453   * coerce(v,w,z) actually does: coerce(v,w), coerce(v,z), coerce(w,z) and
 454     only if z != Py_None; if z == Py_None, then it is treated as absent
 455     variable and only coerce(v,w) is tried.
 456
 457  */
 458
 459 static PyObject *
 460 ternary_op(PyObject *v,
 461            PyObject *w,
 462            PyObject *z,
 463            const int op_slot,
 464            const char *op_name)
 465 {
 466         PyNumberMethods *mv, *mw, *mz;
 467         PyObject *x = NULL;
 468         ternaryfunc slotv = NULL;
 469         ternaryfunc slotw = NULL;
 470         ternaryfunc slotz = NULL;
 471
 472         mv = v->ob_type->tp_as_number;
 473         mw = w->ob_type->tp_as_number;
 474         if (mv != NULL && NEW_STYLE_NUMBER(v))
 475                 slotv = NB_TERNOP(mv, op_slot);
 476         if (w->ob_type != v->ob_type &&
 477             mw != NULL && NEW_STYLE_NUMBER(w)) {
 478                 slotw = NB_TERNOP(mw, op_slot);
 479                 if (slotw == slotv)
 480                         slotw = NULL;
 481         }
 482         if (slotv) {
 483                 if (slotw && PyType_IsSubtype(w->ob_type, v->ob_type)) {
 484                         x = slotw(v, w, z);
 485                         if (x != Py_NotImplemented)
 486                                 return x;
 487                         Py_DECREF(x); /* can't do it */
 488                         slotw = NULL;
 489                 }
 490                 x = slotv(v, w, z);
 491                 if (x != Py_NotImplemented)
 492                         return x;
 493                 Py_DECREF(x); /* can't do it */
 494         }
 495         if (slotw) {
 496                 x = slotw(v, w, z);
 497                 if (x != Py_NotImplemented)
 498                         return x;
 499                 Py_DECREF(x); /* can't do it */
 500         }
 501         mz = z->ob_type->tp_as_number;
 502         if (mz != NULL && NEW_STYLE_NUMBER(z)) {
 503                 slotz = NB_TERNOP(mz, op_slot);
 504                 if (slotz == slotv || slotz == slotw)
 505                         slotz = NULL;
 506                 if (slotz) {
 507                         x = slotz(v, w, z);
 508                         if (x != Py_NotImplemented)
 509                                 return x;
 510                         Py_DECREF(x); /* can't do it */
 511                 }
 512         }
 513
 514         if (!NEW_STYLE_NUMBER(v) || !NEW_STYLE_NUMBER(w) ||
 515                         (z != Py_None && !NEW_STYLE_NUMBER(z))) {
 516                 /* we have an old style operand, coerce */
 517                 PyObject *v1, *z1, *w2, *z2;
 518                 int c;
 519
 520                 c = PyNumber_Coerce(&v, &w);
 521                 if (c != 0)
 522                         goto error3;
 523
 524                 /* Special case: if the third argument is None, it is
 525                    treated as absent argument and not coerced. */
 526                 if (z == Py_None) {
 527                         if (v->ob_type->tp_as_number) {
 528                                 slotz = NB_TERNOP(v->ob_type->tp_as_number,
 529                                                   op_slot);
 530                                 if (slotz)
 531                                         x = slotz(v, w, z);
 532                                 else
 533                                         c = -1;
 534                         }
 535                         else
 536                                 c = -1;
 537                         goto error2;
 538                 }
 539                 v1 = v;
 540                 z1 = z;
 541                 c = PyNumber_Coerce(&v1, &z1);
 542                 if (c != 0)
 543                         goto error2;
 544                 w2 = w;
 545                 z2 = z1;
 546                 c = PyNumber_Coerce(&w2, &z2);
 547                 if (c != 0)
 548                         goto error1;
 549
 550                 if (v1->ob_type->tp_as_number != NULL) {
 551                         slotv = NB_TERNOP(v1->ob_type->tp_as_number,
 552                                           op_slot);
 553                         if (slotv)
 554                                 x = slotv(v1, w2, z2);
 555                         else
 556                                 c = -1;
 557                 }
 558                 else
 559                         c = -1;
 560
 561                 Py_DECREF(w2);
 562                 Py_DECREF(z2);
 563         error1:
 564                 Py_DECREF(v1);
 565                 Py_DECREF(z1);
 566         error2:
 567                 Py_DECREF(v);
 568                 Py_DECREF(w);
 569         error3:
 570                 if (c >= 0)
 571                         return x;
 572         }
 573
 574         if (z == Py_None)
 575                 PyErr_Format(
 576                         PyExc_TypeError,
 577                         "unsupported operand type(s) for ** or pow(): "
 578                         "'%s' and '%s'",
 579                         v->ob_type->tp_name,
 580                         w->ob_type->tp_name);
 581         else
 582                 PyErr_Format(
 583                         PyExc_TypeError,
 584                         "unsupported operand type(s) for pow(): "
 585                         "'%s', '%s', '%s'",
 586                         v->ob_type->tp_name,
 587                         w->ob_type->tp_name,
 588                         z->ob_type->tp_name);
 589         return NULL;
 590 }
 591
 592 #define BINARY_FUNC(func, op, op_name) \
 593     PyObject * \
 594     func(PyObject *v, PyObject *w) { \
 595             return binary_op(v, w, NB_SLOT(op), op_name); \
 596     }
 597
 598 BINARY_FUNC(PyNumber_Or, nb_or, "|")
 599 BINARY_FUNC(PyNumber_Xor, nb_xor, "^")
 600 BINARY_FUNC(PyNumber_And, nb_and, "&")
 601 BINARY_FUNC(PyNumber_Lshift, nb_lshift, "<<")
 602 BINARY_FUNC(PyNumber_Rshift, nb_rshift, ">>")
 603 BINARY_FUNC(PyNumber_Subtract, nb_subtract, "-")
 604 BINARY_FUNC(PyNumber_Divide, nb_divide, "/")
 605 BINARY_FUNC(PyNumber_Divmod, nb_divmod, "divmod()")
 606
 607 PyObject *
 608 PyNumber_Add(PyObject *v, PyObject *w)
 609 {
 610         PyObject *result = binary_op1(v, w, NB_SLOT(nb_add));
 611         if (result == Py_NotImplemented) {
 612                 PySequenceMethods *m = v->ob_type->tp_as_sequence;
 613                 if (m && m->sq_concat) {
 614                         Py_DECREF(result);
 615                         result = (*m->sq_concat)(v, w);
 616                 }
 617                 if (result == Py_NotImplemented) {
 618                         Py_DECREF(result);
 619                         return binop_type_error(v, w, "+");
 620                 }
 621         }
 622         return result;
 623 }
 624
 625 static PyObject *
 626 sequence_repeat(intargfunc repeatfunc, PyObject *seq, PyObject *n)
 627 {
 628         long count;
 629         if (PyInt_Check(n)) {
 630                 count  = PyInt_AsLong(n);
 631         }
 632         else if (PyLong_Check(n)) {
 633                 count = PyLong_AsLong(n);
 634                 if (count == -1 && PyErr_Occurred())
 635                         return NULL;
 636         }
 637         else {
 638                 return type_error(
 639                         "can't multiply sequence to non-int");
 640         }
 641 #if LONG_MAX != INT_MAX
 642         if (count > INT_MAX) {
 643                 PyErr_SetString(PyExc_ValueError,
 644                                 "sequence repeat count too large");
 645                 return NULL;
 646         }
 647         else if (count < INT_MIN)
 648                 count = INT_MIN;
 649         /* XXX Why don't I either
 650
 651            - set count to -1 whenever it's negative (after all,
 652              sequence repeat usually treats negative numbers
 653              as zero(); or
 654
 655            - raise an exception when it's less than INT_MIN?
 656
 657            I'm thinking about a hypothetical use case where some
 658            sequence type might use a negative value as a flag of
 659            some kind.  In those cases I don't want to break the
 660            code by mapping all negative values to -1.  But I also
 661            don't want to break e.g. []*(-sys.maxint), which is
 662            perfectly safe, returning [].  As a compromise, I do
 663            map out-of-range negative values.
 664         */
 665 #endif
 666         return (*repeatfunc)(seq, (int)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                 intargfunc 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 -");
 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 +");
 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 ~");
 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()");
 920 }
 921
 922 /* Add a check for embedded NULL-bytes in the argument. */
 923 static PyObject *
 924 int_from_string(const char *s, int 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 PyObject *
 942 PyNumber_Int(PyObject *o)
 943 {
 944         PyNumberMethods *m;
 945         const char *buffer;
 946         int buffer_len;
 947
 948         if (o == NULL)
 949                 return null_error();
 950         if (PyInt_CheckExact(o)) {
 951                 Py_INCREF(o);
 952                 return o;
 953         }
 954         if (PyInt_Check(o)) {
 955                 PyIntObject *io = (PyIntObject*)o;
 956                 return PyInt_FromLong(io->ob_ival);
 957         }
 958         if (PyString_Check(o))
 959                 return int_from_string(PyString_AS_STRING(o),
 960                                        PyString_GET_SIZE(o));
 961 #ifdef Py_USING_UNICODE
 962         if (PyUnicode_Check(o))
 963                 return PyInt_FromUnicode(PyUnicode_AS_UNICODE(o),
 964                                          PyUnicode_GET_SIZE(o),
 965                                          10);
 966 #endif
 967         m = o->ob_type->tp_as_number;
 968         if (m && m->nb_int)
 969                 return m->nb_int(o);
 970         if (!PyObject_AsCharBuffer(o, &buffer, &buffer_len))
 971                 return int_from_string((char*)buffer, buffer_len);
 972
 973         return type_error("int() argument must be a string or a number");
 974 }
 975
 976 /* Add a check for embedded NULL-bytes in the argument. */
 977 static PyObject *
 978 long_from_string(const char *s, int len)
 979 {
 980         char *end;
 981         PyObject *x;
 982
 983         x = PyLong_FromString((char*)s, &end, 10);
 984         if (x == NULL)
 985                 return NULL;
 986         if (end != s + len) {
 987                 PyErr_SetString(PyExc_ValueError,
 988                                 "null byte in argument for long()");
 989                 Py_DECREF(x);
 990                 return NULL;
 991         }
 992         return x;
 993 }
 994
 995 PyObject *
 996 PyNumber_Long(PyObject *o)
 997 {
 998         PyNumberMethods *m;
 999         const char *buffer;
1000         int buffer_len;
1001
1002         if (o == NULL)
1003                 return null_error();
1004         if (PyLong_CheckExact(o)) {
1005                 Py_INCREF(o);
1006                 return o;
1007         }
1008         if (PyLong_Check(o))
1009                 return _PyLong_Copy((PyLongObject *)o);
1010         if (PyString_Check(o))
1011                 /* need to do extra error checking that PyLong_FromString()
1012                  * doesn't do.  In particular long('9.5') must raise an
1013                  * exception, not truncate the float.
1014                  */
1015                 return long_from_string(PyString_AS_STRING(o),
1016                                         PyString_GET_SIZE(o));
1017 #ifdef Py_USING_UNICODE
1018         if (PyUnicode_Check(o))
1019                 /* The above check is done in PyLong_FromUnicode(). */
1020                 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(o),
1021                                           PyUnicode_GET_SIZE(o),
1022                                           10);
1023 #endif
1024         m = o->ob_type->tp_as_number;
1025         if (m && m->nb_long)
1026                 return m->nb_long(o);
1027         if (!PyObject_AsCharBuffer(o, &buffer, &buffer_len))
1028                 return long_from_string(buffer, buffer_len);
1029
1030         return type_error("long() argument must be a string or a number");
1031 }
1032
1033 PyObject *
1034 PyNumber_Float(PyObject *o)
1035 {
1036         PyNumberMethods *m;
1037
1038         if (o == NULL)
1039                 return null_error();
1040         if (PyFloat_CheckExact(o)) {
1041                 Py_INCREF(o);
1042                 return o;
1043         }
1044         if (PyFloat_Check(o)) {
1045                 PyFloatObject *po = (PyFloatObject *)o;
1046                 return PyFloat_FromDouble(po->ob_fval);
1047         }
1048         if (!PyString_Check(o)) {
1049                 m = o->ob_type->tp_as_number;
1050                 if (m && m->nb_float)
1051                         return m->nb_float(o);
1052         }
1053         return PyFloat_FromString(o, NULL);
1054 }
1055
1056 /* Operations on sequences */
1057
1058 int
1059 PySequence_Check(PyObject *s)
1060 {
1061         return s != NULL && s->ob_type->tp_as_sequence &&
1062                 s->ob_type->tp_as_sequence->sq_item != NULL;
1063 }
1064
1065 int
1066 PySequence_Size(PyObject *s)
1067 {
1068         PySequenceMethods *m;
1069
1070         if (s == NULL) {
1071                 null_error();
1072                 return -1;
1073         }
1074
1075         m = s->ob_type->tp_as_sequence;
1076         if (m && m->sq_length)
1077                 return m->sq_length(s);
1078
1079         type_error("len() of unsized object");
1080         return -1;
1081 }
1082
1083 #undef PySequence_Length
1084 int
1085 PySequence_Length(PyObject *s)
1086 {
1087         return PySequence_Size(s);
1088 }
1089 #define PySequence_Length PySequence_Size
1090
1091 PyObject *
1092 PySequence_Concat(PyObject *s, PyObject *o)
1093 {
1094         PySequenceMethods *m;
1095
1096         if (s == NULL || o == NULL)
1097                 return null_error();
1098
1099         m = s->ob_type->tp_as_sequence;
1100         if (m && m->sq_concat)
1101                 return m->sq_concat(s, o);
1102
1103         return type_error("object can't be concatenated");
1104 }
1105
1106 PyObject *
1107 PySequence_Repeat(PyObject *o, int count)
1108 {
1109         PySequenceMethods *m;
1110
1111         if (o == NULL)
1112                 return null_error();
1113
1114         m = o->ob_type->tp_as_sequence;
1115         if (m && m->sq_repeat)
1116                 return m->sq_repeat(o, count);
1117
1118         return type_error("object can't be repeated");
1119 }
1120
1121 PyObject *
1122 PySequence_InPlaceConcat(PyObject *s, PyObject *o)
1123 {
1124         PySequenceMethods *m;
1125
1126         if (s == NULL || o == NULL)
1127                 return null_error();
1128
1129         m = s->ob_type->tp_as_sequence;
1130         if (m && HASINPLACE(s) && m->sq_inplace_concat)
1131                 return m->sq_inplace_concat(s, o);
1132         if (m && m->sq_concat)
1133                 return m->sq_concat(s, o);
1134
1135         return type_error("object can't be concatenated");
1136 }
1137
1138 PyObject *
1139 PySequence_InPlaceRepeat(PyObject *o, int count)
1140 {
1141         PySequenceMethods *m;
1142
1143         if (o == NULL)
1144                 return null_error();
1145
1146         m = o->ob_type->tp_as_sequence;
1147         if (m && HASINPLACE(o) && m->sq_inplace_repeat)
1148                 return m->sq_inplace_repeat(o, count);
1149         if (m && m->sq_repeat)
1150                 return m->sq_repeat(o, count);
1151
1152         return type_error("object can't be repeated");
1153 }
1154
1155 PyObject *
1156 PySequence_GetItem(PyObject *s, int i)
1157 {
1158         PySequenceMethods *m;
1159
1160         if (s == NULL)
1161                 return null_error();
1162
1163         m = s->ob_type->tp_as_sequence;
1164         if (m && m->sq_item) {
1165                 if (i < 0) {
1166                         if (m->sq_length) {
1167                                 int l = (*m->sq_length)(s);
1168                                 if (l < 0)
1169                                         return NULL;
1170                                 i += l;
1171                         }
1172                 }
1173                 return m->sq_item(s, i);
1174         }
1175
1176         return type_error("unindexable object");
1177 }
1178
1179 static PyObject *
1180 sliceobj_from_intint(int i, int j)
1181 {
1182         PyObject *start, *end, *slice;
1183         start = PyInt_FromLong((long)i);
1184         if (!start)
1185                 return NULL;
1186         end = PyInt_FromLong((long)j);
1187         if (!end) {
1188                 Py_DECREF(start);
1189                 return NULL;
1190         }
1191         slice = PySlice_New(start, end, NULL);
1192         Py_DECREF(start);
1193         Py_DECREF(end);
1194         return slice;
1195 }
1196
1197 PyObject *
1198 PySequence_GetSlice(PyObject *s, int i1, int i2)
1199 {
1200         PySequenceMethods *m;
1201         PyMappingMethods *mp;
1202
1203         if (!s) return null_error();
1204
1205         m = s->ob_type->tp_as_sequence;
1206         if (m && m->sq_slice) {
1207                 if (i1 < 0 || i2 < 0) {
1208                         if (m->sq_length) {
1209                                 int l = (*m->sq_length)(s);
1210                                 if (l < 0)
1211                                         return NULL;
1212                                 if (i1 < 0)
1213                                         i1 += l;
1214                                 if (i2 < 0)
1215                                         i2 += l;
1216                         }
1217                 }
1218                 return m->sq_slice(s, i1, i2);
1219         } else if ((mp = s->ob_type->tp_as_mapping) && mp->mp_subscript) {
1220                 PyObject *res;
1221                 PyObject *slice = sliceobj_from_intint(i1, i2);
1222                 if (!slice)
1223                         return NULL;
1224                 res = mp->mp_subscript(s, slice);
1225                 Py_DECREF(slice);
1226                 return res;
1227         }
1228
1229         return type_error("unsliceable object");
1230 }
1231
1232 int
1233 PySequence_SetItem(PyObject *s, int i, PyObject *o)
1234 {
1235         PySequenceMethods *m;
1236
1237         if (s == NULL) {
1238                 null_error();
1239                 return -1;
1240         }
1241
1242         m = s->ob_type->tp_as_sequence;
1243         if (m && m->sq_ass_item) {
1244                 if (i < 0) {
1245                         if (m->sq_length) {
1246                                 int l = (*m->sq_length)(s);
1247                                 if (l < 0)
1248                                         return -1;
1249                                 i += l;
1250                         }
1251                 }
1252                 return m->sq_ass_item(s, i, o);
1253         }
1254
1255         type_error("object doesn't support item assignment");
1256         return -1;
1257 }
1258
1259 int
1260 PySequence_DelItem(PyObject *s, int i)
1261 {
1262         PySequenceMethods *m;
1263
1264         if (s == NULL) {
1265                 null_error();
1266                 return -1;
1267         }
1268
1269         m = s->ob_type->tp_as_sequence;
1270         if (m && m->sq_ass_item) {
1271                 if (i < 0) {
1272                         if (m->sq_length) {
1273                                 int l = (*m->sq_length)(s);
1274                                 if (l < 0)
1275                                         return -1;
1276                                 i += l;
1277                         }
1278                 }
1279                 return m->sq_ass_item(s, i, (PyObject *)NULL);
1280         }
1281
1282         type_error("object doesn't support item deletion");
1283         return -1;
1284 }
1285
1286 int
1287 PySequence_SetSlice(PyObject *s, int i1, int i2, PyObject *o)
1288 {
1289         PySequenceMethods *m;
1290         PyMappingMethods *mp;
1291
1292         if (s == NULL) {
1293                 null_error();
1294                 return -1;
1295         }
1296
1297         m = s->ob_type->tp_as_sequence;
1298         if (m && m->sq_ass_slice) {
1299                 if (i1 < 0 || i2 < 0) {
1300                         if (m->sq_length) {
1301                                 int l = (*m->sq_length)(s);
1302                                 if (l < 0)
1303                                         return -1;
1304                                 if (i1 < 0)
1305                                         i1 += l;
1306                                 if (i2 < 0)
1307                                         i2 += l;
1308                         }
1309                 }
1310                 return m->sq_ass_slice(s, i1, i2, o);
1311         } else if ((mp = s->ob_type->tp_as_mapping) && mp->mp_ass_subscript) {
1312                 int res;
1313                 PyObject *slice = sliceobj_from_intint(i1, i2);
1314                 if (!slice)
1315                         return -1;
1316                 res = mp->mp_ass_subscript(s, slice, o);
1317                 Py_DECREF(slice);
1318                 return res;
1319         }
1320
1321         type_error("object doesn't support slice assignment");
1322         return -1;
1323 }
1324
1325 int
1326 PySequence_DelSlice(PyObject *s, int i1, int i2)
1327 {
1328         PySequenceMethods *m;
1329
1330         if (s == NULL) {
1331                 null_error();
1332                 return -1;
1333         }
1334
1335         m = s->ob_type->tp_as_sequence;
1336         if (m && m->sq_ass_slice) {
1337                 if (i1 < 0 || i2 < 0) {
1338                         if (m->sq_length) {
1339                                 int l = (*m->sq_length)(s);
1340                                 if (l < 0)
1341                                         return -1;
1342                                 if (i1 < 0)
1343                                         i1 += l;
1344                                 if (i2 < 0)
1345                                         i2 += l;
1346                         }
1347                 }
1348                 return m->sq_ass_slice(s, i1, i2, (PyObject *)NULL);
1349         }
1350         type_error("object doesn't support slice deletion");
1351         return -1;
1352 }
1353
1354 PyObject *
1355 PySequence_Tuple(PyObject *v)
1356 {
1357         PyObject *it;  /* iter(v) */
1358         int n;         /* guess for result tuple size */
1359         PyObject *result;
1360         int j;
1361
1362         if (v == NULL)
1363                 return null_error();
1364
1365         /* Special-case the common tuple and list cases, for efficiency. */
1366         if (PyTuple_CheckExact(v)) {
1367                 /* Note that we can't know whether it's safe to return
1368                    a tuple *subclass* instance as-is, hence the restriction
1369                    to exact tuples here.  In contrast, lists always make
1370                    a copy, so there's no need for exactness below. */
1371                 Py_INCREF(v);
1372                 return v;
1373         }
1374         if (PyList_Check(v))
1375                 return PyList_AsTuple(v);
1376
1377         /* Get iterator. */
1378         it = PyObject_GetIter(v);
1379         if (it == NULL)
1380                 return NULL;
1381
1382         /* Guess result size and allocate space. */
1383         n = PySequence_Size(v);
1384         if (n < 0) {
1385                 PyErr_Clear();
1386                 n = 10;  /* arbitrary */
1387         }
1388         result = PyTuple_New(n);
1389         if (result == NULL)
1390                 goto Fail;
1391
1392         /* Fill the tuple. */
1393         for (j = 0; ; ++j) {
1394                 PyObject *item = PyIter_Next(it);
1395                 if (item == NULL) {
1396                         if (PyErr_Occurred())
1397                                 goto Fail;
1398                         break;
1399                 }
1400                 if (j >= n) {
1401                         if (n < 500)
1402                                 n += 10;
1403                         else
1404                                 n += 100;
1405                         if (_PyTuple_Resize(&result, n) != 0) {
1406                                 Py_DECREF(item);
1407                                 goto Fail;
1408                         }
1409                 }
1410                 PyTuple_SET_ITEM(result, j, item);
1411         }
1412
1413         /* Cut tuple back if guess was too large. */
1414         if (j < n &&
1415             _PyTuple_Resize(&result, j) != 0)
1416                 goto Fail;
1417
1418         Py_DECREF(it);
1419         return result;
1420
1421 Fail:
1422         Py_XDECREF(result);
1423         Py_DECREF(it);
1424         return NULL;
1425 }
1426
1427 PyObject *
1428 PySequence_List(PyObject *v)
1429 {
1430         PyObject *it;      /* iter(v) */
1431         PyObject *result;  /* result list */
1432         int n;             /* guess for result list size */
1433         int i;
1434
1435         if (v == NULL)
1436                 return null_error();
1437
1438         /* Special-case list(a_list), for speed. */
1439         if (PyList_Check(v))
1440                 return PyList_GetSlice(v, 0, PyList_GET_SIZE(v));
1441
1442         /* Get iterator.  There may be some low-level efficiency to be gained
1443          * by caching the tp_iternext slot instead of using PyIter_Next()
1444          * later, but premature optimization is the root etc.
1445          */
1446         it = PyObject_GetIter(v);
1447         if (it == NULL)
1448                 return NULL;
1449
1450         /* Guess a result list size. */
1451         n = -1;  /* unknown */
1452         if (PySequence_Check(v) &&
1453             v->ob_type->tp_as_sequence->sq_length) {
1454                 n = PySequence_Size(v);
1455                 if (n < 0)
1456                         PyErr_Clear();
1457         }
1458         if (n < 0)
1459                 n = 8;  /* arbitrary */
1460         result = PyList_New(n);
1461         if (result == NULL) {
1462                 Py_DECREF(it);
1463                 return NULL;
1464         }
1465
1466         /* Run iterator to exhaustion. */
1467         for (i = 0; ; i++) {
1468                 PyObject *item = PyIter_Next(it);
1469                 if (item == NULL) {
1470                         if (PyErr_Occurred()) {
1471                                 Py_DECREF(result);
1472                                 result = NULL;
1473                         }
1474                         break;
1475                 }
1476                 if (i < n)
1477                         PyList_SET_ITEM(result, i, item); /* steals ref */
1478                 else {
1479                         int status = PyList_Append(result, item);
1480                         Py_DECREF(item);  /* append creates a new ref */
1481                         if (status < 0) {
1482                                 Py_DECREF(result);
1483                                 result = NULL;
1484                                 break;
1485                         }
1486                 }
1487         }
1488
1489         /* Cut back result list if initial guess was too large. */
1490         if (i < n && result != NULL) {
1491                 if (PyList_SetSlice(result, i, n, (PyObject *)NULL) != 0) {
1492                         Py_DECREF(result);
1493                         result = NULL;
1494                 }
1495         }
1496         Py_DECREF(it);
1497         return result;
1498 }
1499
1500 PyObject *
1501 PySequence_Fast(PyObject *v, const char *m)
1502 {
1503         if (v == NULL)
1504                 return null_error();
1505
1506         if (PyList_CheckExact(v) || PyTuple_CheckExact(v)) {
1507                 Py_INCREF(v);
1508                 return v;
1509         }
1510
1511         v = PySequence_Tuple(v);
1512         if (v == NULL && PyErr_ExceptionMatches(PyExc_TypeError))
1513                 return type_error(m);
1514
1515         return v;
1516 }
1517
1518 /* Iterate over seq.  Result depends on the operation:
1519    PY_ITERSEARCH_COUNT:  -1 if error, else # of times obj appears in seq.
1520    PY_ITERSEARCH_INDEX:  0-based index of first occurence of obj in seq;
1521         set ValueError and return -1 if none found; also return -1 on error.
1522    Py_ITERSEARCH_CONTAINS:  return 1 if obj in seq, else 0; -1 on error.
1523 */
1524 int
1525 _PySequence_IterSearch(PyObject *seq, PyObject *obj, int operation)
1526 {
1527         int n;
1528         int wrapped;  /* for PY_ITERSEARCH_INDEX, true iff n wrapped around */
1529         PyObject *it;  /* iter(seq) */
1530
1531         if (seq == NULL || obj == NULL) {
1532                 null_error();
1533                 return -1;
1534         }
1535
1536         it = PyObject_GetIter(seq);
1537         if (it == NULL) {
1538                 type_error("iterable argument required");
1539                 return -1;
1540         }
1541
1542         n = wrapped = 0;
1543         for (;;) {
1544                 int cmp;
1545                 PyObject *item = PyIter_Next(it);
1546                 if (item == NULL) {
1547                         if (PyErr_Occurred())
1548                                 goto Fail;
1549                         break;
1550                 }
1551
1552                 cmp = PyObject_RichCompareBool(obj, item, Py_EQ);
1553                 Py_DECREF(item);
1554                 if (cmp < 0)
1555                         goto Fail;
1556                 if (cmp > 0) {
1557                         switch (operation) {
1558                         case PY_ITERSEARCH_COUNT:
1559                                 ++n;
1560                                 if (n <= 0) {
1561                                         PyErr_SetString(PyExc_OverflowError,
1562                                                 "count exceeds C int size");
1563                                         goto Fail;
1564                                 }
1565                                 break;
1566
1567                         case PY_ITERSEARCH_INDEX:
1568                                 if (wrapped) {
1569                                         PyErr_SetString(PyExc_OverflowError,
1570                                                 "index exceeds C int size");
1571                                         goto Fail;
1572                                 }
1573                                 goto Done;
1574
1575                         case PY_ITERSEARCH_CONTAINS:
1576                                 n = 1;
1577                                 goto Done;
1578
1579                         default:
1580                                 assert(!"unknown operation");
1581                         }
1582                 }
1583
1584                 if (operation == PY_ITERSEARCH_INDEX) {
1585                         ++n;
1586                         if (n <= 0)
1587                                 wrapped = 1;
1588                 }
1589         }
1590
1591         if (operation != PY_ITERSEARCH_INDEX)
1592                 goto Done;
1593
1594         PyErr_SetString(PyExc_ValueError,
1595                         "sequence.index(x): x not in sequence");
1596         /* fall into failure code */
1597 Fail:
1598         n = -1;
1599         /* fall through */
1600 Done:
1601         Py_DECREF(it);
1602         return n;
1603
1604 }
1605
1606 /* Return # of times o appears in s. */
1607 int
1608 PySequence_Count(PyObject *s, PyObject *o)
1609 {
1610         return _PySequence_IterSearch(s, o, PY_ITERSEARCH_COUNT);
1611 }
1612
1613 /* Return -1 if error; 1 if ob in seq; 0 if ob not in seq.
1614  * Use sq_contains if possible, else defer to _PySequence_IterSearch().
1615  */
1616 int
1617 PySequence_Contains(PyObject *seq, PyObject *ob)
1618 {
1619         if (PyType_HasFeature(seq->ob_type, Py_TPFLAGS_HAVE_SEQUENCE_IN)) {
1620                 PySequenceMethods *sqm = seq->ob_type->tp_as_sequence;
1621                 if (sqm != NULL && sqm->sq_contains != NULL)
1622                         return (*sqm->sq_contains)(seq, ob);
1623         }
1624         return _PySequence_IterSearch(seq, ob, PY_ITERSEARCH_CONTAINS);
1625 }
1626
1627 /* Backwards compatibility */
1628 #undef PySequence_In
1629 int
1630 PySequence_In(PyObject *w, PyObject *v)
1631 {
1632         return PySequence_Contains(w, v);
1633 }
1634
1635 int
1636 PySequence_Index(PyObject *s, PyObject *o)
1637 {
1638         return _PySequence_IterSearch(s, o, PY_ITERSEARCH_INDEX);
1639 }
1640
1641 /* Operations on mappings */
1642
1643 int
1644 PyMapping_Check(PyObject *o)
1645 {
1646         return o && o->ob_type->tp_as_mapping &&
1647                 o->ob_type->tp_as_mapping->mp_subscript;
1648 }
1649
1650 int
1651 PyMapping_Size(PyObject *o)
1652 {
1653         PyMappingMethods *m;
1654
1655         if (o == NULL) {
1656                 null_error();
1657                 return -1;
1658         }
1659
1660         m = o->ob_type->tp_as_mapping;
1661         if (m && m->mp_length)
1662                 return m->mp_length(o);
1663
1664         type_error("len() of unsized object");
1665         return -1;
1666 }
1667
1668 #undef PyMapping_Length
1669 int
1670 PyMapping_Length(PyObject *o)
1671 {
1672         return PyMapping_Size(o);
1673 }
1674 #define PyMapping_Length PyMapping_Size
1675
1676 PyObject *
1677 PyMapping_GetItemString(PyObject *o, char *key)
1678 {
1679         PyObject *okey, *r;
1680
1681         if (key == NULL)
1682                 return null_error();
1683
1684         okey = PyString_FromString(key);
1685         if (okey == NULL)
1686                 return NULL;
1687         r = PyObject_GetItem(o, okey);
1688         Py_DECREF(okey);
1689         return r;
1690 }
1691
1692 int
1693 PyMapping_SetItemString(PyObject *o, char *key, PyObject *value)
1694 {
1695         PyObject *okey;
1696         int r;
1697
1698         if (key == NULL) {
1699                 null_error();
1700                 return -1;
1701         }
1702
1703         okey = PyString_FromString(key);
1704         if (okey == NULL)
1705                 return -1;
1706         r = PyObject_SetItem(o, okey, value);
1707         Py_DECREF(okey);
1708         return r;
1709 }
1710
1711 int
1712 PyMapping_HasKeyString(PyObject *o, char *key)
1713 {
1714         PyObject *v;
1715
1716         v = PyMapping_GetItemString(o, key);
1717         if (v) {
1718                 Py_DECREF(v);
1719                 return 1;
1720         }
1721         PyErr_Clear();
1722         return 0;
1723 }
1724
1725 int
1726 PyMapping_HasKey(PyObject *o, PyObject *key)
1727 {
1728         PyObject *v;
1729
1730         v = PyObject_GetItem(o, key);
1731         if (v) {
1732                 Py_DECREF(v);
1733                 return 1;
1734         }
1735         PyErr_Clear();
1736         return 0;
1737 }
1738
1739 /* Operations on callable objects */
1740
1741 /* XXX PyCallable_Check() is in object.c */
1742
1743 PyObject *
1744 PyObject_CallObject(PyObject *o, PyObject *a)
1745 {
1746         return PyEval_CallObjectWithKeywords(o, a, NULL);
1747 }
1748
1749 PyObject *
1750 PyObject_Call(PyObject *func, PyObject *arg, PyObject *kw)
1751 {
1752         ternaryfunc call;
1753
1754         if ((call = func->ob_type->tp_call) != NULL) {
1755                 PyObject *result = (*call)(func, arg, kw);
1756                 if (result == NULL && !PyErr_Occurred())
1757                         PyErr_SetString(
1758                                 PyExc_SystemError,
1759                                 "NULL result without error in PyObject_Call");
1760                 return result;
1761         }
1762         PyErr_Format(PyExc_TypeError, "'%s' object is not callable",
1763                      func->ob_type->tp_name);
1764         return NULL;
1765 }
1766
1767 PyObject *
1768 PyObject_CallFunction(PyObject *callable, char *format, ...)
1769 {
1770         va_list va;
1771         PyObject *args, *retval;
1772
1773         if (callable == NULL)
1774                 return null_error();
1775
1776         if (format && *format) {
1777                 va_start(va, format);
1778                 args = Py_VaBuildValue(format, va);
1779                 va_end(va);
1780         }
1781         else
1782                 args = PyTuple_New(0);
1783
1784         if (args == NULL)
1785                 return NULL;
1786
1787         if (!PyTuple_Check(args)) {
1788                 PyObject *a;
1789
1790                 a = PyTuple_New(1);
1791                 if (a == NULL)
1792                         return NULL;
1793                 if (PyTuple_SetItem(a, 0, args) < 0)
1794                         return NULL;
1795                 args = a;
1796         }
1797         retval = PyObject_Call(callable, args, NULL);
1798
1799         Py_DECREF(args);
1800
1801         return retval;
1802 }
1803
1804 PyObject *
1805 PyObject_CallMethod(PyObject *o, char *name, char *format, ...)
1806 {
1807         va_list va;
1808         PyObject *args, *func = 0, *retval;
1809
1810         if (o == NULL || name == NULL)
1811                 return null_error();
1812
1813         func = PyObject_GetAttrString(o, name);
1814         if (func == NULL) {
1815                 PyErr_SetString(PyExc_AttributeError, name);
1816                 return 0;
1817         }
1818
1819         if (!PyCallable_Check(func))
1820                 return type_error("call of non-callable attribute");
1821
1822         if (format && *format) {
1823                 va_start(va, format);
1824                 args = Py_VaBuildValue(format, va);
1825                 va_end(va);
1826         }
1827         else
1828                 args = PyTuple_New(0);
1829
1830         if (!args)
1831                 return NULL;
1832
1833         if (!PyTuple_Check(args)) {
1834                 PyObject *a;
1835
1836                 a = PyTuple_New(1);
1837                 if (a == NULL)
1838                         return NULL;
1839                 if (PyTuple_SetItem(a, 0, args) < 0)
1840                         return NULL;
1841                 args = a;
1842         }
1843
1844         retval = PyObject_Call(func, args, NULL);
1845
1846         Py_DECREF(args);
1847         Py_DECREF(func);
1848
1849         return retval;
1850 }
1851
1852
1853 static PyObject *
1854 objargs_mktuple(va_list va)
1855 {
1856         int i, n = 0;
1857         va_list countva;
1858         PyObject *result, *tmp;
1859
1860 #ifdef VA_LIST_IS_ARRAY
1861         memcpy(countva, va, sizeof(va_list));
1862 #else
1863 #ifdef __va_copy
1864         __va_copy(countva, va);
1865 #else
1866         countva = va;
1867 #endif
1868 #endif
1869
1870         while (((PyObject *)va_arg(countva, PyObject *)) != NULL)
1871                 ++n;
1872         result = PyTuple_New(n);
1873         if (result != NULL && n > 0) {
1874                 for (i = 0; i < n; ++i) {
1875                         tmp = (PyObject *)va_arg(va, PyObject *);
1876                         PyTuple_SET_ITEM(result, i, tmp);
1877                         Py_INCREF(tmp);
1878                 }
1879         }
1880         return result;
1881 }
1882
1883 PyObject *
1884 PyObject_CallMethodObjArgs(PyObject *callable, PyObject *name, ...)
1885 {
1886         PyObject *args, *tmp;
1887         va_list vargs;
1888
1889         if (callable == NULL || name == NULL)
1890                 return null_error();
1891
1892         callable = PyObject_GetAttr(callable, name);
1893         if (callable == NULL)
1894                 return NULL;
1895
1896         /* count the args */
1897         va_start(vargs, name);
1898         args = objargs_mktuple(vargs);
1899         va_end(vargs);
1900         if (args == NULL) {
1901                 Py_DECREF(callable);
1902                 return NULL;
1903         }
1904         tmp = PyObject_Call(callable, args, NULL);
1905         Py_DECREF(args);
1906         Py_DECREF(callable);
1907
1908         return tmp;
1909 }
1910
1911 PyObject *
1912 PyObject_CallFunctionObjArgs(PyObject *callable, ...)
1913 {
1914         PyObject *args, *tmp;
1915         va_list vargs;
1916
1917         if (callable == NULL)
1918                 return null_error();
1919
1920         /* count the args */
1921         va_start(vargs, callable);
1922         args = objargs_mktuple(vargs);
1923         va_end(vargs);
1924         if (args == NULL)
1925                 return NULL;
1926         tmp = PyObject_Call(callable, args, NULL);
1927         Py_DECREF(args);
1928
1929         return tmp;
1930 }
1931
1932
1933 /* isinstance(), issubclass() */
1934
1935 /* abstract_get_bases() has logically 4 return states, with a sort of 0th
1936  * state that will almost never happen.
1937  *
1938  * 0. creating the __bases__ static string could get a MemoryError
1939  * 1. getattr(cls, '__bases__') could raise an AttributeError
1940  * 2. getattr(cls, '__bases__') could raise some other exception
1941  * 3. getattr(cls, '__bases__') could return a tuple
1942  * 4. getattr(cls, '__bases__') could return something other than a tuple
1943  *
1944  * Only state #3 is a non-error state and only it returns a non-NULL object
1945  * (it returns the retrieved tuple).
1946  *
1947  * Any raised AttributeErrors are masked by clearing the exception and
1948  * returning NULL.  If an object other than a tuple comes out of __bases__,
1949  * then again, the return value is NULL.  So yes, these two situations
1950  * produce exactly the same results: NULL is returned and no error is set.
1951  *
1952  * If some exception other than AttributeError is raised, then NULL is also
1953  * returned, but the exception is not cleared.  That's because we want the
1954  * exception to be propagated along.
1955  *
1956  * Callers are expected to test for PyErr_Occurred() when the return value
1957  * is NULL to decide whether a valid exception should be propagated or not.
1958  * When there's no exception to propagate, it's customary for the caller to
1959  * set a TypeError.
1960  */
1961 static PyObject *
1962 abstract_get_bases(PyObject *cls)
1963 {
1964         static PyObject *__bases__ = NULL;
1965         PyObject *bases;
1966
1967         if (__bases__ == NULL) {
1968                 __bases__ = PyString_FromString("__bases__");
1969                 if (__bases__ == NULL)
1970                         return NULL;
1971         }
1972         bases = PyObject_GetAttr(cls, __bases__);
1973         if (bases == NULL) {
1974                 if (PyErr_ExceptionMatches(PyExc_AttributeError))
1975                         PyErr_Clear();
1976                 return NULL;
1977         }
1978         if (!PyTuple_Check(bases)) {
1979                 Py_DECREF(bases);
1980                 return NULL;
1981         }
1982         return bases;
1983 }
1984
1985
1986 static int
1987 abstract_issubclass(PyObject *derived, PyObject *cls)
1988 {
1989         PyObject *bases;
1990         int i, n;
1991         int r = 0;
1992
1993
1994         if (derived == cls)
1995                 return 1;
1996
1997         if (PyTuple_Check(cls)) {
1998                 /* Not a general sequence -- that opens up the road to
1999                    recursion and stack overflow. */
2000                 n = PyTuple_GET_SIZE(cls);
2001                 for (i = 0; i < n; i++) {
2002                         if (derived == PyTuple_GET_ITEM(cls, i))
2003                                 return 1;
2004                 }
2005         }
2006         bases = abstract_get_bases(derived);
2007         if (bases == NULL) {
2008                 if (PyErr_Occurred())
2009                         return -1;
2010                 return 0;
2011         }
2012         n = PyTuple_GET_SIZE(bases);
2013         for (i = 0; i < n; i++) {
2014                 r = abstract_issubclass(PyTuple_GET_ITEM(bases, i), cls);
2015                 if (r != 0)
2016                         break;
2017         }
2018
2019         Py_DECREF(bases);
2020
2021         return r;
2022 }
2023
2024 static int
2025 check_class(PyObject *cls, const char *error)
2026 {
2027         PyObject *bases = abstract_get_bases(cls);
2028         if (bases == NULL) {
2029                 /* Do not mask errors. */
2030                 if (!PyErr_Occurred())
2031                         PyErr_SetString(PyExc_TypeError, error);
2032                 return 0;
2033         }
2034         Py_DECREF(bases);
2035         return -1;
2036 }
2037
2038 int
2039 PyObject_IsInstance(PyObject *inst, PyObject *cls)
2040 {
2041         PyObject *icls;
2042         static PyObject *__class__ = NULL;
2043         int retval = 0;
2044
2045         if (__class__ == NULL) {
2046                 __class__ = PyString_FromString("__class__");
2047                 if (__class__ == NULL)
2048                         return -1;
2049         }
2050
2051         if (PyClass_Check(cls) && PyInstance_Check(inst)) {
2052                 PyObject *inclass =
2053                         (PyObject*)((PyInstanceObject*)inst)->in_class;
2054                 retval = PyClass_IsSubclass(inclass, cls);
2055         }
2056         else if (PyType_Check(cls)) {
2057                 retval = PyObject_TypeCheck(inst, (PyTypeObject *)cls);
2058                 if (retval == 0) {
2059                         PyObject *c = PyObject_GetAttr(inst, __class__);
2060                         if (c == NULL) {
2061                                 PyErr_Clear();
2062                         }
2063                         else {
2064                                 if (c != (PyObject *)(inst->ob_type) &&
2065                                     PyType_Check(c))
2066                                         retval = PyType_IsSubtype(
2067                                                 (PyTypeObject *)c,
2068                                                 (PyTypeObject *)cls);
2069                                 Py_DECREF(c);
2070                         }
2071                 }
2072         }
2073         else if (PyTuple_Check(cls)) {
2074                 /* Not a general sequence -- that opens up the road to
2075                    recursion and stack overflow. */
2076                 int i, n;
2077
2078                 n = PyTuple_GET_SIZE(cls);
2079                 for (i = 0; i < n; i++) {
2080                         retval = PyObject_IsInstance(
2081                                 inst, PyTuple_GET_ITEM(cls, i));
2082                         if (retval != 0)
2083                                 break;
2084                 }
2085         }
2086         else {
2087                 if (!check_class(cls,
2088                         "isinstance() arg 2 must be a class, type,"
2089                         " or tuple of classes and types"))
2090                         return -1;
2091                 icls = PyObject_GetAttr(inst, __class__);
2092                 if (icls == NULL) {
2093                         PyErr_Clear();
2094                         retval = 0;
2095                 }
2096                 else {
2097                         retval = abstract_issubclass(icls, cls);
2098                         Py_DECREF(icls);
2099                 }
2100         }
2101
2102         return retval;
2103 }
2104
2105 int
2106 PyObject_IsSubclass(PyObject *derived, PyObject *cls)
2107 {
2108         int retval;
2109
2110         if (!PyClass_Check(derived) || !PyClass_Check(cls)) {
2111                 if (!check_class(derived,
2112                                  "issubclass() arg 1 must be a class"))
2113                         return -1;
2114
2115                 if (PyTuple_Check(cls)) {
2116                         int i;
2117                         int n = PyTuple_GET_SIZE(cls);
2118                         for (i = 0; i < n; ++i) {
2119                                 retval = PyObject_IsSubclass(
2120                                         derived, PyTuple_GET_ITEM(cls, i));
2121                                 if (retval != 0) {
2122                                         /* either found it, or got an error */
2123                                         return retval;
2124                                 }
2125                         }
2126                         return 0;
2127                 }
2128                 else {
2129                         if (!check_class(cls,
2130                                         "issubclass() arg 2 must be a class"
2131                                         " or tuple of classes"))
2132                                 return -1;
2133                 }
2134
2135                 retval = abstract_issubclass(derived, cls);
2136         }
2137         else {
2138                 /* shortcut */
2139                 if (!(retval = (derived == cls)))
2140                         retval = PyClass_IsSubclass(derived, cls);
2141         }
2142
2143         return retval;
2144 }
2145
2146 PyObject *
2147 PyObject_GetIter(PyObject *o)
2148 {
2149         PyTypeObject *t = o->ob_type;
2150         getiterfunc f = NULL;
2151         if (PyType_HasFeature(t, Py_TPFLAGS_HAVE_ITER))
2152                 f = t->tp_iter;
2153         if (f == NULL) {
2154                 if (PySequence_Check(o))
2155                         return PySeqIter_New(o);
2156                 PyErr_SetString(PyExc_TypeError,
2157                                 "iteration over non-sequence");
2158                 return NULL;
2159         }
2160         else {
2161                 PyObject *res = (*f)(o);
2162                 if (res != NULL && !PyIter_Check(res)) {
2163                         PyErr_Format(PyExc_TypeError,
2164                                      "iter() returned non-iterator "
2165                                      "of type '%.100s'",
2166                                      res->ob_type->tp_name);
2167                         Py_DECREF(res);
2168                         res = NULL;
2169                 }
2170                 return res;
2171         }
2172 }
2173
2174 /* Return next item.
2175  * If an error occurs, return NULL.  PyErr_Occurred() will be true.
2176  * If the iteration terminates normally, return NULL and clear the
2177  * PyExc_StopIteration exception (if it was set).  PyErr_Occurred()
2178  * will be false.
2179  * Else return the next object.  PyErr_Occurred() will be false.
2180  */
2181 PyObject *
2182 PyIter_Next(PyObject *iter)
2183 {
2184         PyObject *result;
2185         assert(PyIter_Check(iter));
2186         result = (*iter->ob_type->tp_iternext)(iter);
2187         if (result == NULL &&
2188             PyErr_Occurred() &&
2189             PyErr_ExceptionMatches(PyExc_StopIteration))
2190                 PyErr_Clear();
2191         return result;
2192 }