Objects/abstract.c

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