Objects/object.c

   1
   2 /* Generic object operations; and implementation of None (NoObject) */
   3
   4 #include "Python.h"
   5
   6 #ifdef macintosh
   7 #include "macglue.h"
   8 #endif
   9
  10 /* just for trashcan: */
  11 #include "compile.h"
  12 #include "frameobject.h"
  13 #include "traceback.h"
  14
  15 #if defined( Py_TRACE_REFS ) || defined( Py_REF_DEBUG )
  16 DL_IMPORT(long) _Py_RefTotal;
  17 #endif
  18
  19 DL_IMPORT(int) Py_DivisionWarningFlag;
  20
  21 /* Object allocation routines used by NEWOBJ and NEWVAROBJ macros.
  22    These are used by the individual routines for object creation.
  23    Do not call them otherwise, they do not initialize the object! */
  24
  25 #ifdef COUNT_ALLOCS
  26 static PyTypeObject *type_list;
  27 extern int tuple_zero_allocs, fast_tuple_allocs;
  28 extern int quick_int_allocs, quick_neg_int_allocs;
  29 extern int null_strings, one_strings;
  30 void
  31 dump_counts(void)
  32 {
  33         PyTypeObject *tp;
  34
  35         for (tp = type_list; tp; tp = tp->tp_next)
  36                 fprintf(stderr, "%s alloc'd: %d, freed: %d, max in use: %d\n",
  37                         tp->tp_name, tp->tp_allocs, tp->tp_frees,
  38                         tp->tp_maxalloc);
  39         fprintf(stderr, "fast tuple allocs: %d, empty: %d\n",
  40                 fast_tuple_allocs, tuple_zero_allocs);
  41         fprintf(stderr, "fast int allocs: pos: %d, neg: %d\n",
  42                 quick_int_allocs, quick_neg_int_allocs);
  43         fprintf(stderr, "null strings: %d, 1-strings: %d\n",
  44                 null_strings, one_strings);
  45 }
  46
  47 PyObject *
  48 get_counts(void)
  49 {
  50         PyTypeObject *tp;
  51         PyObject *result;
  52         PyObject *v;
  53
  54         result = PyList_New(0);
  55         if (result == NULL)
  56                 return NULL;
  57         for (tp = type_list; tp; tp = tp->tp_next) {
  58                 v = Py_BuildValue("(siii)", tp->tp_name, tp->tp_allocs,
  59                                   tp->tp_frees, tp->tp_maxalloc);
  60                 if (v == NULL) {
  61                         Py_DECREF(result);
  62                         return NULL;
  63                 }
  64                 if (PyList_Append(result, v) < 0) {
  65                         Py_DECREF(v);
  66                         Py_DECREF(result);
  67                         return NULL;
  68                 }
  69                 Py_DECREF(v);
  70         }
  71         return result;
  72 }
  73
  74 void
  75 inc_count(PyTypeObject *tp)
  76 {
  77         if (tp->tp_allocs == 0) {
  78                 /* first time; insert in linked list */
  79                 if (tp->tp_next != NULL) /* sanity check */
  80                         Py_FatalError("XXX inc_count sanity check");
  81                 tp->tp_next = type_list;
  82                 type_list = tp;
  83         }
  84         tp->tp_allocs++;
  85         if (tp->tp_allocs - tp->tp_frees > tp->tp_maxalloc)
  86                 tp->tp_maxalloc = tp->tp_allocs - tp->tp_frees;
  87 }
  88 #endif
  89
  90 PyObject *
  91 PyObject_Init(PyObject *op, PyTypeObject *tp)
  92 {
  93         if (op == NULL) {
  94                 PyErr_SetString(PyExc_SystemError,
  95                                 "NULL object passed to PyObject_Init");
  96                 return op;
  97         }
  98         /* Any changes should be reflected in PyObject_INIT (objimpl.h) */
  99         op->ob_type = tp;
 100         _Py_NewReference(op);
 101         return op;
 102 }
 103
 104 PyVarObject *
 105 PyObject_InitVar(PyVarObject *op, PyTypeObject *tp, int size)
 106 {
 107         if (op == NULL) {
 108                 PyErr_SetString(PyExc_SystemError,
 109                                 "NULL object passed to PyObject_InitVar");
 110                 return op;
 111         }
 112         /* Any changes should be reflected in PyObject_INIT_VAR */
 113         op->ob_size = size;
 114         op->ob_type = tp;
 115         _Py_NewReference((PyObject *)op);
 116         return op;
 117 }
 118
 119 PyObject *
 120 _PyObject_New(PyTypeObject *tp)
 121 {
 122         PyObject *op;
 123         op = (PyObject *) PyObject_MALLOC(_PyObject_SIZE(tp));
 124         if (op == NULL)
 125                 return PyErr_NoMemory();
 126         return PyObject_INIT(op, tp);
 127 }
 128
 129 PyVarObject *
 130 _PyObject_NewVar(PyTypeObject *tp, int nitems)
 131 {
 132         PyVarObject *op;
 133         const size_t size = _PyObject_VAR_SIZE(tp, nitems);
 134         op = (PyVarObject *) PyObject_MALLOC(size);
 135         if (op == NULL)
 136                 return (PyVarObject *)PyErr_NoMemory();
 137         return PyObject_INIT_VAR(op, tp, nitems);
 138 }
 139
 140 void
 141 _PyObject_Del(PyObject *op)
 142 {
 143         PyObject_FREE(op);
 144 }
 145
 146 int
 147 PyObject_Print(PyObject *op, FILE *fp, int flags)
 148 {
 149         int ret = 0;
 150         if (PyErr_CheckSignals())
 151                 return -1;
 152 #ifdef USE_STACKCHECK
 153         if (PyOS_CheckStack()) {
 154                 PyErr_SetString(PyExc_MemoryError, "stack overflow");
 155                 return -1;
 156         }
 157 #endif
 158         clearerr(fp); /* Clear any previous error condition */
 159         if (op == NULL) {
 160                 fprintf(fp, "<nil>");
 161         }
 162         else {
 163                 if (op->ob_refcnt <= 0)
 164                         fprintf(fp, "<refcnt %u at %p>",
 165                                 op->ob_refcnt, op);
 166                 else if (op->ob_type->tp_print == NULL) {
 167                         PyObject *s;
 168                         if (flags & Py_PRINT_RAW)
 169                                 s = PyObject_Str(op);
 170                         else
 171                                 s = PyObject_Repr(op);
 172                         if (s == NULL)
 173                                 ret = -1;
 174                         else {
 175                                 ret = PyObject_Print(s, fp, Py_PRINT_RAW);
 176                         }
 177                         Py_XDECREF(s);
 178                 }
 179                 else
 180                         ret = (*op->ob_type->tp_print)(op, fp, flags);
 181         }
 182         if (ret == 0) {
 183                 if (ferror(fp)) {
 184                         PyErr_SetFromErrno(PyExc_IOError);
 185                         clearerr(fp);
 186                         ret = -1;
 187                 }
 188         }
 189         return ret;
 190 }
 191
 192 /* For debugging convenience.  See Misc/gdbinit for some useful gdb hooks */
 193 void _PyObject_Dump(PyObject* op)
 194 {
 195         if (op == NULL)
 196                 fprintf(stderr, "NULL\n");
 197         else {
 198                 fprintf(stderr, "object  : ");
 199                 (void)PyObject_Print(op, stderr, 0);
 200                 fprintf(stderr, "\n"
 201                         "type    : %s\n"
 202                         "refcount: %d\n"
 203                         "address : %p\n",
 204                         op->ob_type==NULL ? "NULL" : op->ob_type->tp_name,
 205                         op->ob_refcnt,
 206                         op);
 207         }
 208 }
 209
 210 PyObject *
 211 PyObject_Repr(PyObject *v)
 212 {
 213         if (PyErr_CheckSignals())
 214                 return NULL;
 215 #ifdef USE_STACKCHECK
 216         if (PyOS_CheckStack()) {
 217                 PyErr_SetString(PyExc_MemoryError, "stack overflow");
 218                 return NULL;
 219         }
 220 #endif
 221         if (v == NULL)
 222                 return PyString_FromString("<NULL>");
 223         else if (v->ob_type->tp_repr == NULL)
 224                 return PyString_FromFormat("<%s object at %p>",
 225                                            v->ob_type->tp_name, v);
 226         else {
 227                 PyObject *res;
 228                 res = (*v->ob_type->tp_repr)(v);
 229                 if (res == NULL)
 230                         return NULL;
 231 #ifdef Py_USING_UNICODE
 232                 if (PyUnicode_Check(res)) {
 233                         PyObject* str;
 234                         str = PyUnicode_AsUnicodeEscapeString(res);
 235                         Py_DECREF(res);
 236                         if (str)
 237                                 res = str;
 238                         else
 239                                 return NULL;
 240                 }
 241 #endif
 242                 if (!PyString_Check(res)) {
 243                         PyErr_Format(PyExc_TypeError,
 244                                      "__repr__ returned non-string (type %.200s)",
 245                                      res->ob_type->tp_name);
 246                         Py_DECREF(res);
 247                         return NULL;
 248                 }
 249                 return res;
 250         }
 251 }
 252
 253 PyObject *
 254 PyObject_Str(PyObject *v)
 255 {
 256         PyObject *res;
 257
 258         if (v == NULL)
 259                 return PyString_FromString("<NULL>");
 260         if (PyString_CheckExact(v)) {
 261                 Py_INCREF(v);
 262                 return v;
 263         }
 264         if (v->ob_type->tp_str == NULL)
 265                 return PyObject_Repr(v);
 266
 267         res = (*v->ob_type->tp_str)(v);
 268         if (res == NULL)
 269                 return NULL;
 270 #ifdef Py_USING_UNICODE
 271         if (PyUnicode_Check(res)) {
 272                 PyObject* str;
 273                 str = PyUnicode_AsEncodedString(res, NULL, NULL);
 274                 Py_DECREF(res);
 275                 if (str)
 276                         res = str;
 277                 else
 278                         return NULL;
 279         }
 280 #endif
 281         if (!PyString_Check(res)) {
 282                 PyErr_Format(PyExc_TypeError,
 283                              "__str__ returned non-string (type %.200s)",
 284                              res->ob_type->tp_name);
 285                 Py_DECREF(res);
 286                 return NULL;
 287         }
 288         return res;
 289 }
 290
 291 #ifdef Py_USING_UNICODE
 292 PyObject *
 293 PyObject_Unicode(PyObject *v)
 294 {
 295         PyObject *res;
 296
 297         if (v == NULL)
 298                 res = PyString_FromString("<NULL>");
 299         if (PyUnicode_CheckExact(v)) {
 300                 Py_INCREF(v);
 301                 return v;
 302         }
 303         if (PyUnicode_Check(v)) {
 304                 /* For a Unicode subtype that's not a Unicode object,
 305                    return a true Unicode object with the same data. */
 306                 return PyUnicode_FromUnicode(PyUnicode_AS_UNICODE(v),
 307                                              PyUnicode_GET_SIZE(v));
 308         }
 309         if (PyString_Check(v)) {
 310                 Py_INCREF(v);
 311                 res = v;
 312         }
 313         else {
 314                 PyObject *func;
 315                 static PyObject *unicodestr;
 316                 /* XXX As soon as we have a tp_unicode slot, we should
 317                        check this before trying the __unicode__
 318                        method. */
 319                 if (unicodestr == NULL) {
 320                         unicodestr= PyString_InternFromString(
 321                                                        "__unicode__");
 322                         if (unicodestr == NULL)
 323                                 return NULL;
 324                 }
 325                 func = PyObject_GetAttr(v, unicodestr);
 326                 if (func != NULL) {
 327                         res = PyEval_CallObject(func, (PyObject *)NULL);
 328                         Py_DECREF(func);
 329                 }
 330                 else {
 331                         PyErr_Clear();
 332                         if (v->ob_type->tp_str != NULL)
 333                                 res = (*v->ob_type->tp_str)(v);
 334                         else
 335                                 res = PyObject_Repr(v);
 336                 }
 337         }
 338         if (res == NULL)
 339                 return NULL;
 340         if (!PyUnicode_Check(res)) {
 341                 PyObject *str;
 342                 str = PyUnicode_FromEncodedObject(res, NULL, "strict");
 343                 Py_DECREF(res);
 344                 if (str)
 345                         res = str;
 346                 else
 347                         return NULL;
 348         }
 349         return res;
 350 }
 351 #endif
 352
 353
 354 /* Macro to get the tp_richcompare field of a type if defined */
 355 #define RICHCOMPARE(t) (PyType_HasFeature((t), Py_TPFLAGS_HAVE_RICHCOMPARE) \
 356                          ? (t)->tp_richcompare : NULL)
 357
 358 /* Map rich comparison operators to their swapped version, e.g. LT --> GT */
 359 static int swapped_op[] = {Py_GT, Py_GE, Py_EQ, Py_NE, Py_LT, Py_LE};
 360
 361 /* Try a genuine rich comparison, returning an object.  Return:
 362    NULL for exception;
 363    NotImplemented if this particular rich comparison is not implemented or
 364      undefined;
 365    some object not equal to NotImplemented if it is implemented
 366      (this latter object may not be a Boolean).
 367 */
 368 static PyObject *
 369 try_rich_compare(PyObject *v, PyObject *w, int op)
 370 {
 371         richcmpfunc f;
 372         PyObject *res;
 373
 374         if (v->ob_type != w->ob_type &&
 375             PyType_IsSubtype(w->ob_type, v->ob_type) &&
 376             (f = RICHCOMPARE(w->ob_type)) != NULL) {
 377                 res = (*f)(w, v, swapped_op[op]);
 378                 if (res != Py_NotImplemented)
 379                         return res;
 380                 Py_DECREF(res);
 381         }
 382         if ((f = RICHCOMPARE(v->ob_type)) != NULL) {
 383                 res = (*f)(v, w, op);
 384                 if (res != Py_NotImplemented)
 385                         return res;
 386                 Py_DECREF(res);
 387         }
 388         if ((f = RICHCOMPARE(w->ob_type)) != NULL) {
 389                 return (*f)(w, v, swapped_op[op]);
 390         }
 391         res = Py_NotImplemented;
 392         Py_INCREF(res);
 393         return res;
 394 }
 395
 396 /* Try a genuine rich comparison, returning an int.  Return:
 397    -1 for exception (including the case where try_rich_compare() returns an
 398       object that's not a Boolean);
 399     0 if the outcome is false;
 400     1 if the outcome is true;
 401     2 if this particular rich comparison is not implemented or undefined.
 402 */
 403 static int
 404 try_rich_compare_bool(PyObject *v, PyObject *w, int op)
 405 {
 406         PyObject *res;
 407         int ok;
 408
 409         if (RICHCOMPARE(v->ob_type) == NULL && RICHCOMPARE(w->ob_type) == NULL)
 410                 return 2; /* Shortcut, avoid INCREF+DECREF */
 411         res = try_rich_compare(v, w, op);
 412         if (res == NULL)
 413                 return -1;
 414         if (res == Py_NotImplemented) {
 415                 Py_DECREF(res);
 416                 return 2;
 417         }
 418         ok = PyObject_IsTrue(res);
 419         Py_DECREF(res);
 420         return ok;
 421 }
 422
 423 /* Try rich comparisons to determine a 3-way comparison.  Return:
 424    -2 for an exception;
 425    -1 if v  < w;
 426     0 if v == w;
 427     1 if v  > w;
 428     2 if this particular rich comparison is not implemented or undefined.
 429 */
 430 static int
 431 try_rich_to_3way_compare(PyObject *v, PyObject *w)
 432 {
 433         static struct { int op; int outcome; } tries[3] = {
 434                 /* Try this operator, and if it is true, use this outcome: */
 435                 {Py_EQ, 0},
 436                 {Py_LT, -1},
 437                 {Py_GT, 1},
 438         };
 439         int i;
 440
 441         if (RICHCOMPARE(v->ob_type) == NULL && RICHCOMPARE(w->ob_type) == NULL)
 442                 return 2; /* Shortcut */
 443
 444         for (i = 0; i < 3; i++) {
 445                 switch (try_rich_compare_bool(v, w, tries[i].op)) {
 446                 case -1:
 447                         return -2;
 448                 case 1:
 449                         return tries[i].outcome;
 450                 }
 451         }
 452
 453         return 2;
 454 }
 455
 456 /* Try a 3-way comparison, returning an int.  Return:
 457    -2 for an exception;
 458    -1 if v <  w;
 459     0 if v == w;
 460     1 if v  > w;
 461     2 if this particular 3-way comparison is not implemented or undefined.
 462 */
 463 static int
 464 try_3way_compare(PyObject *v, PyObject *w)
 465 {
 466         int c;
 467         cmpfunc f;
 468
 469         /* Comparisons involving instances are given to instance_compare,
 470            which has the same return conventions as this function. */
 471
 472         f = v->ob_type->tp_compare;
 473         if (PyInstance_Check(v))
 474                 return (*f)(v, w);
 475         if (PyInstance_Check(w))
 476                 return (*w->ob_type->tp_compare)(v, w);
 477
 478         /* If both have the same (non-NULL) tp_compare, use it. */
 479         if (f != NULL && f == w->ob_type->tp_compare) {
 480                 c = (*f)(v, w);
 481                 if (c < 0 && PyErr_Occurred())
 482                         return -1;
 483                 return c < 0 ? -1 : c > 0 ? 1 : 0;
 484         }
 485
 486         /* If either tp_compare is _PyObject_SlotCompare, that's safe. */
 487         if (f == _PyObject_SlotCompare ||
 488             w->ob_type->tp_compare == _PyObject_SlotCompare)
 489                 return _PyObject_SlotCompare(v, w);
 490
 491         /* Try coercion; if it fails, give up */
 492         c = PyNumber_CoerceEx(&v, &w);
 493         if (c < 0)
 494                 return -2;
 495         if (c > 0)
 496                 return 2;
 497
 498         /* Try v's comparison, if defined */
 499         if ((f = v->ob_type->tp_compare) != NULL) {
 500                 c = (*f)(v, w);
 501                 Py_DECREF(v);
 502                 Py_DECREF(w);
 503                 if (c < 0 && PyErr_Occurred())
 504                         return -2;
 505                 return c < 0 ? -1 : c > 0 ? 1 : 0;
 506         }
 507
 508         /* Try w's comparison, if defined */
 509         if ((f = w->ob_type->tp_compare) != NULL) {
 510                 c = (*f)(w, v); /* swapped! */
 511                 Py_DECREF(v);
 512                 Py_DECREF(w);
 513                 if (c < 0 && PyErr_Occurred())
 514                         return -2;
 515                 return c < 0 ? 1 : c > 0 ? -1 : 0; /* negated! */
 516         }
 517
 518         /* No comparison defined */
 519         Py_DECREF(v);
 520         Py_DECREF(w);
 521         return 2;
 522 }
 523
 524 /* Final fallback 3-way comparison, returning an int.  Return:
 525    -2 if an error occurred;
 526    -1 if v <  w;
 527     0 if v == w;
 528     1 if v >  w.
 529 */
 530 static int
 531 default_3way_compare(PyObject *v, PyObject *w)
 532 {
 533         int c;
 534         char *vname, *wname;
 535
 536         if (v->ob_type == w->ob_type) {
 537                 /* When comparing these pointers, they must be cast to
 538                  * integer types (i.e. Py_uintptr_t, our spelling of C9X's
 539                  * uintptr_t).  ANSI specifies that pointer compares other
 540                  * than == and != to non-related structures are undefined.
 541                  */
 542                 Py_uintptr_t vv = (Py_uintptr_t)v;
 543                 Py_uintptr_t ww = (Py_uintptr_t)w;
 544                 return (vv < ww) ? -1 : (vv > ww) ? 1 : 0;
 545         }
 546
 547 #ifdef Py_USING_UNICODE
 548         /* Special case for Unicode */
 549         if (PyUnicode_Check(v) || PyUnicode_Check(w)) {
 550                 c = PyUnicode_Compare(v, w);
 551                 if (!PyErr_Occurred())
 552                         return c;
 553                 /* TypeErrors are ignored: if Unicode coercion fails due
 554                    to one of the arguments not having the right type, we
 555                    continue as defined by the coercion protocol (see
 556                    above).  Luckily, decoding errors are reported as
 557                    ValueErrors and are not masked by this technique. */
 558                 if (!PyErr_ExceptionMatches(PyExc_TypeError))
 559                         return -2;
 560                 PyErr_Clear();
 561         }
 562 #endif
 563
 564         /* None is smaller than anything */
 565         if (v == Py_None)
 566                 return -1;
 567         if (w == Py_None)
 568                 return 1;
 569
 570         /* different type: compare type names */
 571         if (v->ob_type->tp_as_number)
 572                 vname = "";
 573         else
 574                 vname = v->ob_type->tp_name;
 575         if (w->ob_type->tp_as_number)
 576                 wname = "";
 577         else
 578                 wname = w->ob_type->tp_name;
 579         c = strcmp(vname, wname);
 580         if (c < 0)
 581                 return -1;
 582         if (c > 0)
 583                 return 1;
 584         /* Same type name, or (more likely) incomparable numeric types */
 585         return ((Py_uintptr_t)(v->ob_type) < (
 586                 Py_uintptr_t)(w->ob_type)) ? -1 : 1;
 587 }
 588
 589 #define CHECK_TYPES(o) PyType_HasFeature((o)->ob_type, Py_TPFLAGS_CHECKTYPES)
 590
 591 /* Do a 3-way comparison, by hook or by crook.  Return:
 592    -2 for an exception;
 593    -1 if v <  w;
 594     0 if v == w;
 595     1 if v >  w;
 596    If the object implements a tp_compare function, it returns
 597    whatever this function returns (whether with an exception or not).
 598 */
 599 static int
 600 do_cmp(PyObject *v, PyObject *w)
 601 {
 602         int c;
 603         cmpfunc f;
 604
 605         if (v->ob_type == w->ob_type
 606             && (f = v->ob_type->tp_compare) != NULL) {
 607                 c = (*f)(v, w);
 608                 if (c != 2 || !PyInstance_Check(v))
 609                         return c;
 610         }
 611         c = try_rich_to_3way_compare(v, w);
 612         if (c < 2)
 613                 return c;
 614         c = try_3way_compare(v, w);
 615         if (c < 2)
 616                 return c;
 617         return default_3way_compare(v, w);
 618 }
 619
 620 /* compare_nesting is incremented before calling compare (for
 621    some types) and decremented on exit.  If the count exceeds the
 622    nesting limit, enable code to detect circular data structures.
 623
 624    This is a tunable parameter that should only affect the performance
 625    of comparisons, nothing else.  Setting it high makes comparing deeply
 626    nested non-cyclical data structures faster, but makes comparing cyclical
 627    data structures slower.
 628 */
 629 #define NESTING_LIMIT 20
 630
 631 static int compare_nesting = 0;
 632
 633 static PyObject*
 634 get_inprogress_dict(void)
 635 {
 636         static PyObject *key;
 637         PyObject *tstate_dict, *inprogress;
 638
 639         if (key == NULL) {
 640                 key = PyString_InternFromString("cmp_state");
 641                 if (key == NULL)
 642                         return NULL;
 643         }
 644
 645         tstate_dict = PyThreadState_GetDict();
 646         if (tstate_dict == NULL) {
 647                 PyErr_BadInternalCall();
 648                 return NULL;
 649         }
 650
 651         inprogress = PyDict_GetItem(tstate_dict, key);
 652         if (inprogress == NULL) {
 653                 inprogress = PyDict_New();
 654                 if (inprogress == NULL)
 655                         return NULL;
 656                 if (PyDict_SetItem(tstate_dict, key, inprogress) == -1) {
 657                     Py_DECREF(inprogress);
 658                     return NULL;
 659                 }
 660                 Py_DECREF(inprogress);
 661         }
 662
 663         return inprogress;
 664 }
 665
 666 static PyObject *
 667 check_recursion(PyObject *v, PyObject *w, int op)
 668 {
 669         PyObject *inprogress;
 670         PyObject *token;
 671         Py_uintptr_t iv = (Py_uintptr_t)v;
 672         Py_uintptr_t iw = (Py_uintptr_t)w;
 673         PyObject *x, *y, *z;
 674
 675         inprogress = get_inprogress_dict();
 676         if (inprogress == NULL)
 677                 return NULL;
 678
 679         token = PyTuple_New(3);
 680         if (token == NULL)
 681                 return NULL;
 682
 683         if (iv <= iw) {
 684                 PyTuple_SET_ITEM(token, 0, x = PyLong_FromVoidPtr((void *)v));
 685                 PyTuple_SET_ITEM(token, 1, y = PyLong_FromVoidPtr((void *)w));
 686                 if (op >= 0)
 687                         op = swapped_op[op];
 688         } else {
 689                 PyTuple_SET_ITEM(token, 0, x = PyLong_FromVoidPtr((void *)w));
 690                 PyTuple_SET_ITEM(token, 1, y = PyLong_FromVoidPtr((void *)v));
 691         }
 692         PyTuple_SET_ITEM(token, 2, z = PyInt_FromLong((long)op));
 693         if (x == NULL || y == NULL || z == NULL) {
 694                 Py_DECREF(token);
 695                 return NULL;
 696         }
 697
 698         if (PyDict_GetItem(inprogress, token) != NULL) {
 699                 Py_DECREF(token);
 700                 return Py_None; /* Without INCREF! */
 701         }
 702
 703         if (PyDict_SetItem(inprogress, token, token) < 0) {
 704                 Py_DECREF(token);
 705                 return NULL;
 706         }
 707
 708         return token;
 709 }
 710
 711 static void
 712 delete_token(PyObject *token)
 713 {
 714         PyObject *inprogress;
 715
 716         if (token == NULL || token == Py_None)
 717                 return;
 718         inprogress = get_inprogress_dict();
 719         if (inprogress == NULL)
 720                 PyErr_Clear();
 721         else
 722                 PyDict_DelItem(inprogress, token);
 723         Py_DECREF(token);
 724 }
 725
 726 /* Compare v to w.  Return
 727    -1 if v <  w or exception (PyErr_Occurred() true in latter case).
 728     0 if v == w.
 729     1 if v > w.
 730    XXX The docs (C API manual) say the return value is undefined in case
 731    XXX of error.
 732 */
 733 int
 734 PyObject_Compare(PyObject *v, PyObject *w)
 735 {
 736         PyTypeObject *vtp;
 737         int result;
 738
 739 #if defined(USE_STACKCHECK)
 740         if (PyOS_CheckStack()) {
 741                 PyErr_SetString(PyExc_MemoryError, "Stack overflow");
 742                 return -1;
 743         }
 744 #endif
 745         if (v == NULL || w == NULL) {
 746                 PyErr_BadInternalCall();
 747                 return -1;
 748         }
 749         if (v == w)
 750                 return 0;
 751         vtp = v->ob_type;
 752         compare_nesting++;
 753         if (compare_nesting > NESTING_LIMIT &&
 754                 (vtp->tp_as_mapping
 755                  || (vtp->tp_as_sequence
 756                      && !PyString_Check(v)
 757                      && !PyTuple_Check(v)))) {
 758                 /* try to detect circular data structures */
 759                 PyObject *token = check_recursion(v, w, -1);
 760
 761                 if (token == NULL) {
 762                         result = -1;
 763                 }
 764                 else if (token == Py_None) {
 765                         /* already comparing these objects.  assume
 766                            they're equal until shown otherwise */
 767                         result = 0;
 768                 }
 769                 else {
 770                         result = do_cmp(v, w);
 771                         delete_token(token);
 772                 }
 773         }
 774         else {
 775                 result = do_cmp(v, w);
 776         }
 777         compare_nesting--;
 778         return result < 0 ? -1 : result;
 779 }
 780
 781 /* Return (new reference to) Py_True or Py_False. */
 782 static PyObject *
 783 convert_3way_to_object(int op, int c)
 784 {
 785         PyObject *result;
 786         switch (op) {
 787         case Py_LT: c = c <  0; break;
 788         case Py_LE: c = c <= 0; break;
 789         case Py_EQ: c = c == 0; break;
 790         case Py_NE: c = c != 0; break;
 791         case Py_GT: c = c >  0; break;
 792         case Py_GE: c = c >= 0; break;
 793         }
 794         result = c ? Py_True : Py_False;
 795         Py_INCREF(result);
 796         return result;
 797 }
 798
 799 /* We want a rich comparison but don't have one.  Try a 3-way cmp instead.
 800    Return
 801    NULL      if error
 802    Py_True   if v op w
 803    Py_False  if not (v op w)
 804 */
 805 static PyObject *
 806 try_3way_to_rich_compare(PyObject *v, PyObject *w, int op)
 807 {
 808         int c;
 809
 810         c = try_3way_compare(v, w);
 811         if (c >= 2)
 812                 c = default_3way_compare(v, w);
 813         if (c <= -2)
 814                 return NULL;
 815         return convert_3way_to_object(op, c);
 816 }
 817
 818 /* Do rich comparison on v and w.  Return
 819    NULL      if error
 820    Else a new reference to an object other than Py_NotImplemented, usually(?):
 821    Py_True   if v op w
 822    Py_False  if not (v op w)
 823 */
 824 static PyObject *
 825 do_richcmp(PyObject *v, PyObject *w, int op)
 826 {
 827         PyObject *res;
 828
 829         res = try_rich_compare(v, w, op);
 830         if (res != Py_NotImplemented)
 831                 return res;
 832         Py_DECREF(res);
 833
 834         return try_3way_to_rich_compare(v, w, op);
 835 }
 836
 837 /* Return:
 838    NULL for exception;
 839    some object not equal to NotImplemented if it is implemented
 840      (this latter object may not be a Boolean).
 841 */
 842 PyObject *
 843 PyObject_RichCompare(PyObject *v, PyObject *w, int op)
 844 {
 845         PyObject *res;
 846
 847         assert(Py_LT <= op && op <= Py_GE);
 848
 849         compare_nesting++;
 850         if (compare_nesting > NESTING_LIMIT &&
 851                 (v->ob_type->tp_as_mapping
 852                  || (v->ob_type->tp_as_sequence
 853                      && !PyString_Check(v)
 854                      && !PyTuple_Check(v)))) {
 855
 856                 /* try to detect circular data structures */
 857                 PyObject *token = check_recursion(v, w, op);
 858                 if (token == NULL) {
 859                         res = NULL;
 860                         goto Done;
 861                 }
 862                 else if (token == Py_None) {
 863                         /* already comparing these objects with this operator.
 864                            assume they're equal until shown otherwise */
 865                         if (op == Py_EQ)
 866                                 res = Py_True;
 867                         else if (op == Py_NE)
 868                                 res = Py_False;
 869                         else {
 870                                 PyErr_SetString(PyExc_ValueError,
 871                                         "can't order recursive values");
 872                                 res = NULL;
 873                         }
 874                         Py_XINCREF(res);
 875                 }
 876                 else {
 877                         res = do_richcmp(v, w, op);
 878                         delete_token(token);
 879                 }
 880                 goto Done;
 881         }
 882
 883         /* No nesting extremism.
 884            If the types are equal, and not old-style instances, try to
 885            get out cheap (don't bother with coercions etc.). */
 886         if (v->ob_type == w->ob_type && !PyInstance_Check(v)) {
 887                 cmpfunc fcmp;
 888                 richcmpfunc frich = RICHCOMPARE(v->ob_type);
 889                 /* If the type has richcmp, try it first.  try_rich_compare
 890                    tries it two-sided, which is not needed since we've a
 891                    single type only. */
 892                 if (frich != NULL) {
 893                         res = (*frich)(v, w, op);
 894                         if (res != Py_NotImplemented)
 895                                 goto Done;
 896                         Py_DECREF(res);
 897                 }
 898                 /* No richcmp, or this particular richmp not implemented.
 899                    Try 3-way cmp. */
 900                 fcmp = v->ob_type->tp_compare;
 901                 if (fcmp != NULL) {
 902                         int c = (*fcmp)(v, w);
 903                         if (c < 0 && PyErr_Occurred()) {
 904                                 res = NULL;
 905                                 goto Done;
 906                         }
 907                         res = convert_3way_to_object(op, c);
 908                         goto Done;
 909                 }
 910         }
 911
 912         /* Fast path not taken, or couldn't deliver a useful result. */
 913         res = do_richcmp(v, w, op);
 914 Done:
 915         compare_nesting--;
 916         return res;
 917 }
 918
 919 /* Return -1 if error; 1 if v op w; 0 if not (v op w). */
 920 int
 921 PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
 922 {
 923         PyObject *res = PyObject_RichCompare(v, w, op);
 924         int ok;
 925
 926         if (res == NULL)
 927                 return -1;
 928         ok = PyObject_IsTrue(res);
 929         Py_DECREF(res);
 930         return ok;
 931 }
 932
 933 /* Set of hash utility functions to help maintaining the invariant that
 934         iff a==b then hash(a)==hash(b)
 935
 936    All the utility functions (_Py_Hash*()) return "-1" to signify an error.
 937 */
 938
 939 long
 940 _Py_HashDouble(double v)
 941 {
 942         double intpart, fractpart;
 943         int expo;
 944         long hipart;
 945         long x;         /* the final hash value */
 946         /* This is designed so that Python numbers of different types
 947          * that compare equal hash to the same value; otherwise comparisons
 948          * of mapping keys will turn out weird.
 949          */
 950
 951 #ifdef MPW /* MPW C modf expects pointer to extended as second argument */
 952 {
 953         extended e;
 954         fractpart = modf(v, &e);
 955         intpart = e;
 956 }
 957 #else
 958         fractpart = modf(v, &intpart);
 959 #endif
 960         if (fractpart == 0.0) {
 961                 /* This must return the same hash as an equal int or long. */
 962                 if (intpart > LONG_MAX || -intpart > LONG_MAX) {
 963                         /* Convert to long and use its hash. */
 964                         PyObject *plong;        /* converted to Python long */
 965                         if (Py_IS_INFINITY(intpart))
 966                                 /* can't convert to long int -- arbitrary */
 967                                 v = v < 0 ? -271828.0 : 314159.0;
 968                         plong = PyLong_FromDouble(v);
 969                         if (plong == NULL)
 970                                 return -1;
 971                         x = PyObject_Hash(plong);
 972                         Py_DECREF(plong);
 973                         return x;
 974                 }
 975                 /* Fits in a C long == a Python int, so is its own hash. */
 976                 x = (long)intpart;
 977                 if (x == -1)
 978                         x = -2;
 979                 return x;
 980         }
 981         /* The fractional part is non-zero, so we don't have to worry about
 982          * making this match the hash of some other type.
 983          * Use frexp to get at the bits in the double.
 984          * Since the VAX D double format has 56 mantissa bits, which is the
 985          * most of any double format in use, each of these parts may have as
 986          * many as (but no more than) 56 significant bits.
 987          * So, assuming sizeof(long) >= 4, each part can be broken into two
 988          * longs; frexp and multiplication are used to do that.
 989          * Also, since the Cray double format has 15 exponent bits, which is
 990          * the most of any double format in use, shifting the exponent field
 991          * left by 15 won't overflow a long (again assuming sizeof(long) >= 4).
 992          */
 993         v = frexp(v, &expo);
 994         v *= 2147483648.0;      /* 2**31 */
 995         hipart = (long)v;       /* take the top 32 bits */
 996         v = (v - (double)hipart) * 2147483648.0; /* get the next 32 bits */
 997         x = hipart + (long)v + (expo << 15);
 998         if (x == -1)
 999                 x = -2;
1000         return x;
1001 }
1002
1003 long
1004 _Py_HashPointer(void *p)
1005 {
1006 #if SIZEOF_LONG >= SIZEOF_VOID_P
1007         return (long)p;
1008 #else
1009         /* convert to a Python long and hash that */
1010         PyObject* longobj;
1011         long x;
1012
1013         if ((longobj = PyLong_FromVoidPtr(p)) == NULL) {
1014                 x = -1;
1015                 goto finally;
1016         }
1017         x = PyObject_Hash(longobj);
1018
1019 finally:
1020         Py_XDECREF(longobj);
1021         return x;
1022 #endif
1023 }
1024
1025
1026 long
1027 PyObject_Hash(PyObject *v)
1028 {
1029         PyTypeObject *tp = v->ob_type;
1030         if (tp->tp_hash != NULL)
1031                 return (*tp->tp_hash)(v);
1032         if (tp->tp_compare == NULL && RICHCOMPARE(tp) == NULL) {
1033                 return _Py_HashPointer(v); /* Use address as hash value */
1034         }
1035         /* If there's a cmp but no hash defined, the object can't be hashed */
1036         PyErr_SetString(PyExc_TypeError, "unhashable type");
1037         return -1;
1038 }
1039
1040 PyObject *
1041 PyObject_GetAttrString(PyObject *v, char *name)
1042 {
1043         PyObject *w, *res;
1044
1045         if (v->ob_type->tp_getattr != NULL)
1046                 return (*v->ob_type->tp_getattr)(v, name);
1047         w = PyString_InternFromString(name);
1048         if (w == NULL)
1049                 return NULL;
1050         res = PyObject_GetAttr(v, w);
1051         Py_XDECREF(w);
1052         return res;
1053 }
1054
1055 int
1056 PyObject_HasAttrString(PyObject *v, char *name)
1057 {
1058         PyObject *res = PyObject_GetAttrString(v, name);
1059         if (res != NULL) {
1060                 Py_DECREF(res);
1061                 return 1;
1062         }
1063         PyErr_Clear();
1064         return 0;
1065 }
1066
1067 int
1068 PyObject_SetAttrString(PyObject *v, char *name, PyObject *w)
1069 {
1070         PyObject *s;
1071         int res;
1072
1073         if (v->ob_type->tp_setattr != NULL)
1074                 return (*v->ob_type->tp_setattr)(v, name, w);
1075         s = PyString_InternFromString(name);
1076         if (s == NULL)
1077                 return -1;
1078         res = PyObject_SetAttr(v, s, w);
1079         Py_XDECREF(s);
1080         return res;
1081 }
1082
1083 PyObject *
1084 PyObject_GetAttr(PyObject *v, PyObject *name)
1085 {
1086         PyTypeObject *tp = v->ob_type;
1087
1088 #ifdef Py_USING_UNICODE
1089         /* The Unicode to string conversion is done here because the
1090            existing tp_getattro slots expect a string object as name
1091            and we wouldn't want to break those. */
1092         if (PyUnicode_Check(name)) {
1093                 name = _PyUnicode_AsDefaultEncodedString(name, NULL);
1094                 if (name == NULL)
1095                         return NULL;
1096         }
1097         else
1098 #endif
1099         if (!PyString_Check(name)) {
1100                 PyErr_SetString(PyExc_TypeError,
1101                                 "attribute name must be string");
1102                 return NULL;
1103         }
1104         if (tp->tp_getattro != NULL)
1105                 return (*tp->tp_getattro)(v, name);
1106         if (tp->tp_getattr != NULL)
1107                 return (*tp->tp_getattr)(v, PyString_AS_STRING(name));
1108         PyErr_Format(PyExc_AttributeError,
1109                      "'%.50s' object has no attribute '%.400s'",
1110                      tp->tp_name, PyString_AS_STRING(name));
1111         return NULL;
1112 }
1113
1114 int
1115 PyObject_HasAttr(PyObject *v, PyObject *name)
1116 {
1117         PyObject *res = PyObject_GetAttr(v, name);
1118         if (res != NULL) {
1119                 Py_DECREF(res);
1120                 return 1;
1121         }
1122         PyErr_Clear();
1123         return 0;
1124 }
1125
1126 int
1127 PyObject_SetAttr(PyObject *v, PyObject *name, PyObject *value)
1128 {
1129         PyTypeObject *tp = v->ob_type;
1130         int err;
1131
1132 #ifdef Py_USING_UNICODE
1133         /* The Unicode to string conversion is done here because the
1134            existing tp_setattro slots expect a string object as name
1135            and we wouldn't want to break those. */
1136         if (PyUnicode_Check(name)) {
1137                 name = PyUnicode_AsEncodedString(name, NULL, NULL);
1138                 if (name == NULL)
1139                         return -1;
1140         }
1141         else
1142 #endif
1143         if (!PyString_Check(name)){
1144                 PyErr_SetString(PyExc_TypeError,
1145                                 "attribute name must be string");
1146                 return -1;
1147         }
1148         else
1149                 Py_INCREF(name);
1150
1151         PyString_InternInPlace(&name);
1152         if (tp->tp_setattro != NULL) {
1153                 err = (*tp->tp_setattro)(v, name, value);
1154                 Py_DECREF(name);
1155                 return err;
1156         }
1157         if (tp->tp_setattr != NULL) {
1158                 err = (*tp->tp_setattr)(v, PyString_AS_STRING(name), value);
1159                 Py_DECREF(name);
1160                 return err;
1161         }
1162         Py_DECREF(name);
1163         if (tp->tp_getattr == NULL && tp->tp_getattro == NULL)
1164                 PyErr_Format(PyExc_TypeError,
1165                              "'%.100s' object has no attributes "
1166                              "(%s .%.100s)",
1167                              tp->tp_name,
1168                              value==NULL ? "del" : "assign to",
1169                              PyString_AS_STRING(name));
1170         else
1171                 PyErr_Format(PyExc_TypeError,
1172                              "'%.100s' object has only read-only attributes "
1173                              "(%s .%.100s)",
1174                              tp->tp_name,
1175                              value==NULL ? "del" : "assign to",
1176                              PyString_AS_STRING(name));
1177         return -1;
1178 }
1179
1180 /* Helper to get a pointer to an object's __dict__ slot, if any */
1181
1182 PyObject **
1183 _PyObject_GetDictPtr(PyObject *obj)
1184 {
1185         long dictoffset;
1186         PyTypeObject *tp = obj->ob_type;
1187
1188         if (!(tp->tp_flags & Py_TPFLAGS_HAVE_CLASS))
1189                 return NULL;
1190         dictoffset = tp->tp_dictoffset;
1191         if (dictoffset == 0)
1192                 return NULL;
1193         if (dictoffset < 0) {
1194                 const size_t size = _PyObject_VAR_SIZE(tp,
1195                                         ((PyVarObject *)obj)->ob_size);
1196                 dictoffset += (long)size;
1197                 assert(dictoffset > 0);
1198                 assert(dictoffset % SIZEOF_VOID_P == 0);
1199         }
1200         return (PyObject **) ((char *)obj + dictoffset);
1201 }
1202
1203 /* Generic GetAttr functions - put these in your tp_[gs]etattro slot */
1204
1205 PyObject *
1206 PyObject_GenericGetAttr(PyObject *obj, PyObject *name)
1207 {
1208         PyTypeObject *tp = obj->ob_type;
1209         PyObject *descr;
1210         PyObject *res = NULL;
1211         descrgetfunc f;
1212         PyObject **dictptr;
1213
1214 #ifdef Py_USING_UNICODE
1215         /* The Unicode to string conversion is done here because the
1216            existing tp_setattro slots expect a string object as name
1217            and we wouldn't want to break those. */
1218         if (PyUnicode_Check(name)) {
1219                 name = PyUnicode_AsEncodedString(name, NULL, NULL);
1220                 if (name == NULL)
1221                         return NULL;
1222         }
1223         else
1224 #endif
1225         if (!PyString_Check(name)){
1226                 PyErr_SetString(PyExc_TypeError,
1227                                 "attribute name must be string");
1228                 return NULL;
1229         }
1230         else
1231                 Py_INCREF(name);
1232
1233         if (tp->tp_dict == NULL) {
1234                 if (PyType_Ready(tp) < 0)
1235                         goto done;
1236         }
1237
1238         descr = _PyType_Lookup(tp, name);
1239         f = NULL;
1240         if (descr != NULL) {
1241                 f = descr->ob_type->tp_descr_get;
1242                 if (f != NULL && PyDescr_IsData(descr)) {
1243                         res = f(descr, obj, (PyObject *)obj->ob_type);
1244                         goto done;
1245                 }
1246         }
1247
1248         dictptr = _PyObject_GetDictPtr(obj);
1249         if (dictptr != NULL) {
1250                 PyObject *dict = *dictptr;
1251                 if (dict != NULL) {
1252                         res = PyDict_GetItem(dict, name);
1253                         if (res != NULL) {
1254                                 Py_INCREF(res);
1255                                 goto done;
1256                         }
1257                 }
1258         }
1259
1260         if (f != NULL) {
1261                 res = f(descr, obj, (PyObject *)obj->ob_type);
1262                 goto done;
1263         }
1264
1265         if (descr != NULL) {
1266                 Py_INCREF(descr);
1267                 res = descr;
1268                 goto done;
1269         }
1270
1271         PyErr_Format(PyExc_AttributeError,
1272                      "'%.50s' object has no attribute '%.400s'",
1273                      tp->tp_name, PyString_AS_STRING(name));
1274   done:
1275         Py_DECREF(name);
1276         return res;
1277 }
1278
1279 int
1280 PyObject_GenericSetAttr(PyObject *obj, PyObject *name, PyObject *value)
1281 {
1282         PyTypeObject *tp = obj->ob_type;
1283         PyObject *descr;
1284         descrsetfunc f;
1285         PyObject **dictptr;
1286         int res = -1;
1287
1288 #ifdef Py_USING_UNICODE
1289         /* The Unicode to string conversion is done here because the
1290            existing tp_setattro slots expect a string object as name
1291            and we wouldn't want to break those. */
1292         if (PyUnicode_Check(name)) {
1293                 name = PyUnicode_AsEncodedString(name, NULL, NULL);
1294                 if (name == NULL)
1295                         return -1;
1296         }
1297         else
1298 #endif
1299         if (!PyString_Check(name)){
1300                 PyErr_SetString(PyExc_TypeError,
1301                                 "attribute name must be string");
1302                 return -1;
1303         }
1304         else
1305                 Py_INCREF(name);
1306
1307         if (tp->tp_dict == NULL) {
1308                 if (PyType_Ready(tp) < 0)
1309                         goto done;
1310         }
1311
1312         descr = _PyType_Lookup(tp, name);
1313         f = NULL;
1314         if (descr != NULL) {
1315                 f = descr->ob_type->tp_descr_set;
1316                 if (f != NULL && PyDescr_IsData(descr)) {
1317                         res = f(descr, obj, value);
1318                         goto done;
1319                 }
1320         }
1321
1322         dictptr = _PyObject_GetDictPtr(obj);
1323         if (dictptr != NULL) {
1324                 PyObject *dict = *dictptr;
1325                 if (dict == NULL && value != NULL) {
1326                         dict = PyDict_New();
1327                         if (dict == NULL)
1328                                 goto done;
1329                         *dictptr = dict;
1330                 }
1331                 if (dict != NULL) {
1332                         if (value == NULL)
1333                                 res = PyDict_DelItem(dict, name);
1334                         else
1335                                 res = PyDict_SetItem(dict, name, value);
1336                         if (res < 0 && PyErr_ExceptionMatches(PyExc_KeyError))
1337                                 PyErr_SetObject(PyExc_AttributeError, name);
1338                         goto done;
1339                 }
1340         }
1341
1342         if (f != NULL) {
1343                 res = f(descr, obj, value);
1344                 goto done;
1345         }
1346
1347         if (descr == NULL) {
1348                 PyErr_Format(PyExc_AttributeError,
1349                              "'%.50s' object has no attribute '%.400s'",
1350                              tp->tp_name, PyString_AS_STRING(name));
1351                 goto done;
1352         }
1353
1354         PyErr_Format(PyExc_AttributeError,
1355                      "'%.50s' object attribute '%.400s' is read-only",
1356                      tp->tp_name, PyString_AS_STRING(name));
1357   done:
1358         Py_DECREF(name);
1359         return res;
1360 }
1361
1362 /* Test a value used as condition, e.g., in a for or if statement.
1363    Return -1 if an error occurred */
1364
1365 int
1366 PyObject_IsTrue(PyObject *v)
1367 {
1368         int res;
1369         if (v == Py_None)
1370                 res = 0;
1371         else if (v->ob_type->tp_as_number != NULL &&
1372                  v->ob_type->tp_as_number->nb_nonzero != NULL)
1373                 res = (*v->ob_type->tp_as_number->nb_nonzero)(v);
1374         else if (v->ob_type->tp_as_mapping != NULL &&
1375                  v->ob_type->tp_as_mapping->mp_length != NULL)
1376                 res = (*v->ob_type->tp_as_mapping->mp_length)(v);
1377         else if (v->ob_type->tp_as_sequence != NULL &&
1378                  v->ob_type->tp_as_sequence->sq_length != NULL)
1379                 res = (*v->ob_type->tp_as_sequence->sq_length)(v);
1380         else
1381                 res = 1;
1382         if (res > 0)
1383                 res = 1;
1384         return res;
1385 }
1386
1387 /* equivalent of 'not v'
1388    Return -1 if an error occurred */
1389
1390 int
1391 PyObject_Not(PyObject *v)
1392 {
1393         int res;
1394         res = PyObject_IsTrue(v);
1395         if (res < 0)
1396                 return res;
1397         return res == 0;
1398 }
1399
1400 /* Coerce two numeric types to the "larger" one.
1401    Increment the reference count on each argument.
1402    Return value:
1403    -1 if an error occurred;
1404    0 if the coercion succeeded (and then the reference counts are increased);
1405    1 if no coercion is possible (and no error is raised).
1406 */
1407 int
1408 PyNumber_CoerceEx(PyObject **pv, PyObject **pw)
1409 {
1410         register PyObject *v = *pv;
1411         register PyObject *w = *pw;
1412         int res;
1413
1414         if (v->ob_type == w->ob_type && !PyInstance_Check(v)) {
1415                 Py_INCREF(v);
1416                 Py_INCREF(w);
1417                 return 0;
1418         }
1419         if (v->ob_type->tp_as_number && v->ob_type->tp_as_number->nb_coerce) {
1420                 res = (*v->ob_type->tp_as_number->nb_coerce)(pv, pw);
1421                 if (res <= 0)
1422                         return res;
1423         }
1424         if (w->ob_type->tp_as_number && w->ob_type->tp_as_number->nb_coerce) {
1425                 res = (*w->ob_type->tp_as_number->nb_coerce)(pw, pv);
1426                 if (res <= 0)
1427                         return res;
1428         }
1429         return 1;
1430 }
1431
1432 /* Coerce two numeric types to the "larger" one.
1433    Increment the reference count on each argument.
1434    Return -1 and raise an exception if no coercion is possible
1435    (and then no reference count is incremented).
1436 */
1437 int
1438 PyNumber_Coerce(PyObject **pv, PyObject **pw)
1439 {
1440         int err = PyNumber_CoerceEx(pv, pw);
1441         if (err <= 0)
1442                 return err;
1443         PyErr_SetString(PyExc_TypeError, "number coercion failed");
1444         return -1;
1445 }
1446
1447
1448 /* Test whether an object can be called */
1449
1450 int
1451 PyCallable_Check(PyObject *x)
1452 {
1453         if (x == NULL)
1454                 return 0;
1455         if (PyInstance_Check(x)) {
1456                 PyObject *call = PyObject_GetAttrString(x, "__call__");
1457                 if (call == NULL) {
1458                         PyErr_Clear();
1459                         return 0;
1460                 }
1461                 /* Could test recursively but don't, for fear of endless
1462                    recursion if some joker sets self.__call__ = self */
1463                 Py_DECREF(call);
1464                 return 1;
1465         }
1466         else {
1467                 return x->ob_type->tp_call != NULL;
1468         }
1469 }
1470
1471 /* Helper for PyObject_Dir.
1472    Merge the __dict__ of aclass into dict, and recursively also all
1473    the __dict__s of aclass's base classes.  The order of merging isn't
1474    defined, as it's expected that only the final set of dict keys is
1475    interesting.
1476    Return 0 on success, -1 on error.
1477 */
1478
1479 static int
1480 merge_class_dict(PyObject* dict, PyObject* aclass)
1481 {
1482         PyObject *classdict;
1483         PyObject *bases;
1484
1485         assert(PyDict_Check(dict));
1486         assert(aclass);
1487
1488         /* Merge in the type's dict (if any). */
1489         classdict = PyObject_GetAttrString(aclass, "__dict__");
1490         if (classdict == NULL)
1491                 PyErr_Clear();
1492         else {
1493                 int status = PyDict_Update(dict, classdict);
1494                 Py_DECREF(classdict);
1495                 if (status < 0)
1496                         return -1;
1497         }
1498
1499         /* Recursively merge in the base types' (if any) dicts. */
1500         bases = PyObject_GetAttrString(aclass, "__bases__");
1501         if (bases == NULL)
1502                 PyErr_Clear();
1503         else {
1504                 int i, n;
1505                 assert(PyTuple_Check(bases));
1506                 n = PyTuple_GET_SIZE(bases);
1507                 for (i = 0; i < n; i++) {
1508                         PyObject *base = PyTuple_GET_ITEM(bases, i);
1509                         if (merge_class_dict(dict, base) < 0) {
1510                                 Py_DECREF(bases);
1511                                 return -1;
1512                         }
1513                 }
1514                 Py_DECREF(bases);
1515         }
1516         return 0;
1517 }
1518
1519 /* Helper for PyObject_Dir.
1520    If obj has an attr named attrname that's a list, merge its string
1521    elements into keys of dict.
1522    Return 0 on success, -1 on error.  Errors due to not finding the attr,
1523    or the attr not being a list, are suppressed.
1524 */
1525
1526 static int
1527 merge_list_attr(PyObject* dict, PyObject* obj, char *attrname)
1528 {
1529         PyObject *list;
1530         int result = 0;
1531
1532         assert(PyDict_Check(dict));
1533         assert(obj);
1534         assert(attrname);
1535
1536         list = PyObject_GetAttrString(obj, attrname);
1537         if (list == NULL)
1538                 PyErr_Clear();
1539
1540         else if (PyList_Check(list)) {
1541                 int i;
1542                 for (i = 0; i < PyList_GET_SIZE(list); ++i) {
1543                         PyObject *item = PyList_GET_ITEM(list, i);
1544                         if (PyString_Check(item)) {
1545                                 result = PyDict_SetItem(dict, item, Py_None);
1546                                 if (result < 0)
1547                                         break;
1548                         }
1549                 }
1550         }
1551
1552         Py_XDECREF(list);
1553         return result;
1554 }
1555
1556 /* Like __builtin__.dir(arg).  See bltinmodule.c's builtin_dir for the
1557    docstring, which should be kept in synch with this implementation. */
1558
1559 PyObject *
1560 PyObject_Dir(PyObject *arg)
1561 {
1562         /* Set exactly one of these non-NULL before the end. */
1563         PyObject *result = NULL;        /* result list */
1564         PyObject *masterdict = NULL;    /* result is masterdict.keys() */
1565
1566         /* If NULL arg, return the locals. */
1567         if (arg == NULL) {
1568                 PyObject *locals = PyEval_GetLocals();
1569                 if (locals == NULL)
1570                         goto error;
1571                 result = PyDict_Keys(locals);
1572                 if (result == NULL)
1573                         goto error;
1574         }
1575
1576         /* Elif this is some form of module, we only want its dict. */
1577         else if (PyModule_Check(arg)) {
1578                 masterdict = PyObject_GetAttrString(arg, "__dict__");
1579                 if (masterdict == NULL)
1580                         goto error;
1581                 if (!PyDict_Check(masterdict)) {
1582                         PyErr_SetString(PyExc_TypeError,
1583                                         "module.__dict__ is not a dictionary");
1584                         goto error;
1585                 }
1586         }
1587
1588         /* Elif some form of type or class, grab its dict and its bases.
1589            We deliberately don't suck up its __class__, as methods belonging
1590            to the metaclass would probably be more confusing than helpful. */
1591         else if (PyType_Check(arg) || PyClass_Check(arg)) {
1592                 masterdict = PyDict_New();
1593                 if (masterdict == NULL)
1594                         goto error;
1595                 if (merge_class_dict(masterdict, arg) < 0)
1596                         goto error;
1597         }
1598
1599         /* Else look at its dict, and the attrs reachable from its class. */
1600         else {
1601                 PyObject *itsclass;
1602                 /* Create a dict to start with.  CAUTION:  Not everything
1603                    responding to __dict__ returns a dict! */
1604                 masterdict = PyObject_GetAttrString(arg, "__dict__");
1605                 if (masterdict == NULL) {
1606                         PyErr_Clear();
1607                         masterdict = PyDict_New();
1608                 }
1609                 else if (!PyDict_Check(masterdict)) {
1610                         Py_DECREF(masterdict);
1611                         masterdict = PyDict_New();
1612                 }
1613                 else {
1614                         /* The object may have returned a reference to its
1615                            dict, so copy it to avoid mutating it. */
1616                         PyObject *temp = PyDict_Copy(masterdict);
1617                         Py_DECREF(masterdict);
1618                         masterdict = temp;
1619                 }
1620                 if (masterdict == NULL)
1621                         goto error;
1622
1623                 /* Merge in __members__ and __methods__ (if any).
1624                    XXX Would like this to go away someday; for now, it's
1625                    XXX needed to get at im_self etc of method objects. */
1626                 if (merge_list_attr(masterdict, arg, "__members__") < 0)
1627                         goto error;
1628                 if (merge_list_attr(masterdict, arg, "__methods__") < 0)
1629                         goto error;
1630
1631                 /* Merge in attrs reachable from its class.
1632                    CAUTION:  Not all objects have a __class__ attr. */
1633                 itsclass = PyObject_GetAttrString(arg, "__class__");
1634                 if (itsclass == NULL)
1635                         PyErr_Clear();
1636                 else {
1637                         int status = merge_class_dict(masterdict, itsclass);
1638                         Py_DECREF(itsclass);
1639                         if (status < 0)
1640                                 goto error;
1641                 }
1642         }
1643
1644         assert((result == NULL) ^ (masterdict == NULL));
1645         if (masterdict != NULL) {
1646                 /* The result comes from its keys. */
1647                 assert(result == NULL);
1648                 result = PyDict_Keys(masterdict);
1649                 if (result == NULL)
1650                         goto error;
1651         }
1652
1653         assert(result);
1654         if (PyList_Sort(result) != 0)
1655                 goto error;
1656         else
1657                 goto normal_return;
1658
1659   error:
1660         Py_XDECREF(result);
1661         result = NULL;
1662         /* fall through */
1663   normal_return:
1664         Py_XDECREF(masterdict);
1665         return result;
1666 }
1667
1668 /*
1669 NoObject is usable as a non-NULL undefined value, used by the macro None.
1670 There is (and should be!) no way to create other objects of this type,
1671 so there is exactly one (which is indestructible, by the way).
1672 (XXX This type and the type of NotImplemented below should be unified.)
1673 */
1674
1675 /* ARGSUSED */
1676 static PyObject *
1677 none_repr(PyObject *op)
1678 {
1679         return PyString_FromString("None");
1680 }
1681
1682 /* ARGUSED */
1683 static void
1684 none_dealloc(PyObject* ignore)
1685 {
1686         /* This should never get called, but we also don't want to SEGV if
1687          * we accidently decref None out of existance.
1688          */
1689         abort();
1690 }
1691
1692
1693 static PyTypeObject PyNone_Type = {
1694         PyObject_HEAD_INIT(&PyType_Type)
1695         0,
1696         "NoneType",
1697         0,
1698         0,
1699         (destructor)none_dealloc,            /*tp_dealloc*/ /*never called*/
1700         0,              /*tp_print*/
1701         0,              /*tp_getattr*/
1702         0,              /*tp_setattr*/
1703         0,              /*tp_compare*/
1704         (reprfunc)none_repr, /*tp_repr*/
1705         0,              /*tp_as_number*/
1706         0,              /*tp_as_sequence*/
1707         0,              /*tp_as_mapping*/
1708         0,              /*tp_hash */
1709 };
1710
1711 PyObject _Py_NoneStruct = {
1712         PyObject_HEAD_INIT(&PyNone_Type)
1713 };
1714
1715 /* NotImplemented is an object that can be used to signal that an
1716    operation is not implemented for the given type combination. */
1717
1718 static PyObject *
1719 NotImplemented_repr(PyObject *op)
1720 {
1721         return PyString_FromString("NotImplemented");
1722 }
1723
1724 static PyTypeObject PyNotImplemented_Type = {
1725         PyObject_HEAD_INIT(&PyType_Type)
1726         0,
1727         "NotImplementedType",
1728         0,
1729         0,
1730         (destructor)none_dealloc,            /*tp_dealloc*/ /*never called*/
1731         0,              /*tp_print*/
1732         0,              /*tp_getattr*/
1733         0,              /*tp_setattr*/
1734         0,              /*tp_compare*/
1735         (reprfunc)NotImplemented_repr, /*tp_repr*/
1736         0,              /*tp_as_number*/
1737         0,              /*tp_as_sequence*/
1738         0,              /*tp_as_mapping*/
1739         0,              /*tp_hash */
1740 };
1741
1742 PyObject _Py_NotImplementedStruct = {
1743         PyObject_HEAD_INIT(&PyNotImplemented_Type)
1744 };
1745
1746 void
1747 _Py_ReadyTypes(void)
1748 {
1749         if (PyType_Ready(&PyType_Type) < 0)
1750                 Py_FatalError("Can't initialize 'type'");
1751
1752         if (PyType_Ready(&PyList_Type) < 0)
1753                 Py_FatalError("Can't initialize 'list'");
1754
1755         if (PyType_Ready(&PyNone_Type) < 0)
1756                 Py_FatalError("Can't initialize type(None)");
1757
1758         if (PyType_Ready(&PyNotImplemented_Type) < 0)
1759                 Py_FatalError("Can't initialize type(NotImplemented)");
1760 }
1761
1762
1763 #ifdef Py_TRACE_REFS
1764
1765 static PyObject refchain = {&refchain, &refchain};
1766
1767 void
1768 _Py_ResetReferences(void)
1769 {
1770         refchain._ob_prev = refchain._ob_next = &refchain;
1771         _Py_RefTotal = 0;
1772 }
1773
1774 void
1775 _Py_NewReference(PyObject *op)
1776 {
1777         _Py_RefTotal++;
1778         op->ob_refcnt = 1;
1779         op->_ob_next = refchain._ob_next;
1780         op->_ob_prev = &refchain;
1781         refchain._ob_next->_ob_prev = op;
1782         refchain._ob_next = op;
1783 #ifdef COUNT_ALLOCS
1784         inc_count(op->ob_type);
1785 #endif
1786 }
1787
1788 void
1789 _Py_ForgetReference(register PyObject *op)
1790 {
1791 #ifdef SLOW_UNREF_CHECK
1792         register PyObject *p;
1793 #endif
1794         if (op->ob_refcnt < 0)
1795                 Py_FatalError("UNREF negative refcnt");
1796         if (op == &refchain ||
1797             op->_ob_prev->_ob_next != op || op->_ob_next->_ob_prev != op)
1798                 Py_FatalError("UNREF invalid object");
1799 #ifdef SLOW_UNREF_CHECK
1800         for (p = refchain._ob_next; p != &refchain; p = p->_ob_next) {
1801                 if (p == op)
1802                         break;
1803         }
1804         if (p == &refchain) /* Not found */
1805                 Py_FatalError("UNREF unknown object");
1806 #endif
1807         op->_ob_next->_ob_prev = op->_ob_prev;
1808         op->_ob_prev->_ob_next = op->_ob_next;
1809         op->_ob_next = op->_ob_prev = NULL;
1810 #ifdef COUNT_ALLOCS
1811         op->ob_type->tp_frees++;
1812 #endif
1813 }
1814
1815 void
1816 _Py_Dealloc(PyObject *op)
1817 {
1818         destructor dealloc = op->ob_type->tp_dealloc;
1819         _Py_ForgetReference(op);
1820         (*dealloc)(op);
1821 }
1822
1823 void
1824 _Py_PrintReferences(FILE *fp)
1825 {
1826         PyObject *op;
1827         fprintf(fp, "Remaining objects:\n");
1828         for (op = refchain._ob_next; op != &refchain; op = op->_ob_next) {
1829                 fprintf(fp, "[%d] ", op->ob_refcnt);
1830                 if (PyObject_Print(op, fp, 0) != 0)
1831                         PyErr_Clear();
1832                 putc('\n', fp);
1833         }
1834 }
1835
1836 PyObject *
1837 _Py_GetObjects(PyObject *self, PyObject *args)
1838 {
1839         int i, n;
1840         PyObject *t = NULL;
1841         PyObject *res, *op;
1842
1843         if (!PyArg_ParseTuple(args, "i|O", &n, &t))
1844                 return NULL;
1845         op = refchain._ob_next;
1846         res = PyList_New(0);
1847         if (res == NULL)
1848                 return NULL;
1849         for (i = 0; (n == 0 || i < n) && op != &refchain; i++) {
1850                 while (op == self || op == args || op == res || op == t ||
1851                        (t != NULL && op->ob_type != (PyTypeObject *) t)) {
1852                         op = op->_ob_next;
1853                         if (op == &refchain)
1854                                 return res;
1855                 }
1856                 if (PyList_Append(res, op) < 0) {
1857                         Py_DECREF(res);
1858                         return NULL;
1859                 }
1860                 op = op->_ob_next;
1861         }
1862         return res;
1863 }
1864
1865 #endif
1866
1867
1868 /* Hack to force loading of cobject.o */
1869 PyTypeObject *_Py_cobject_hack = &PyCObject_Type;
1870
1871
1872 /* Hack to force loading of abstract.o */
1873 int (*_Py_abstract_hack)(PyObject *) = &PyObject_Size;
1874
1875
1876 /* Python's malloc wrappers (see pymem.h) */
1877
1878 void *
1879 PyMem_Malloc(size_t nbytes)
1880 {
1881 #if _PyMem_EXTRA > 0
1882         if (nbytes == 0)
1883                 nbytes = _PyMem_EXTRA;
1884 #endif
1885         return PyMem_MALLOC(nbytes);
1886 }
1887
1888 void *
1889 PyMem_Realloc(void *p, size_t nbytes)
1890 {
1891 #if _PyMem_EXTRA > 0
1892         if (nbytes == 0)
1893                 nbytes = _PyMem_EXTRA;
1894 #endif
1895         return PyMem_REALLOC(p, nbytes);
1896 }
1897
1898 void
1899 PyMem_Free(void *p)
1900 {
1901         PyMem_FREE(p);
1902 }
1903
1904
1905 /* Python's object malloc wrappers (see objimpl.h) */
1906
1907 void *
1908 PyObject_Malloc(size_t nbytes)
1909 {
1910         return PyObject_MALLOC(nbytes);
1911 }
1912
1913 void *
1914 PyObject_Realloc(void *p, size_t nbytes)
1915 {
1916         return PyObject_REALLOC(p, nbytes);
1917 }
1918
1919 void
1920 PyObject_Free(void *p)
1921 {
1922         PyObject_FREE(p);
1923 }
1924
1925
1926 /* These methods are used to control infinite recursion in repr, str, print,
1927    etc.  Container objects that may recursively contain themselves,
1928    e.g. builtin dictionaries and lists, should used Py_ReprEnter() and
1929    Py_ReprLeave() to avoid infinite recursion.
1930
1931    Py_ReprEnter() returns 0 the first time it is called for a particular
1932    object and 1 every time thereafter.  It returns -1 if an exception
1933    occurred.  Py_ReprLeave() has no return value.
1934
1935    See dictobject.c and listobject.c for examples of use.
1936 */
1937
1938 #define KEY "Py_Repr"
1939
1940 int
1941 Py_ReprEnter(PyObject *obj)
1942 {
1943         PyObject *dict;
1944         PyObject *list;
1945         int i;
1946
1947         dict = PyThreadState_GetDict();
1948         if (dict == NULL)
1949                 return -1;
1950         list = PyDict_GetItemString(dict, KEY);
1951         if (list == NULL) {
1952                 list = PyList_New(0);
1953                 if (list == NULL)
1954                         return -1;
1955                 if (PyDict_SetItemString(dict, KEY, list) < 0)
1956                         return -1;
1957                 Py_DECREF(list);
1958         }
1959         i = PyList_GET_SIZE(list);
1960         while (--i >= 0) {
1961                 if (PyList_GET_ITEM(list, i) == obj)
1962                         return 1;
1963         }
1964         PyList_Append(list, obj);
1965         return 0;
1966 }
1967
1968 void
1969 Py_ReprLeave(PyObject *obj)
1970 {
1971         PyObject *dict;
1972         PyObject *list;
1973         int i;
1974
1975         dict = PyThreadState_GetDict();
1976         if (dict == NULL)
1977                 return;
1978         list = PyDict_GetItemString(dict, KEY);
1979         if (list == NULL || !PyList_Check(list))
1980                 return;
1981         i = PyList_GET_SIZE(list);
1982         /* Count backwards because we always expect obj to be list[-1] */
1983         while (--i >= 0) {
1984                 if (PyList_GET_ITEM(list, i) == obj) {
1985                         PyList_SetSlice(list, i, i + 1, NULL);
1986                         break;
1987                 }
1988         }
1989 }
1990
1991 /*
1992   trashcan
1993   CT 2k0130
1994   non-recursively destroy nested objects
1995
1996   CT 2k0223
1997   everything is now done in a macro.
1998
1999   CT 2k0305
2000   modified to use functions, after Tim Peter's suggestion.
2001
2002   CT 2k0309
2003   modified to restore a possible error.
2004
2005   CT 2k0325
2006   added better safe than sorry check for threadstate
2007
2008   CT 2k0422
2009   complete rewrite. We now build a chain via ob_type
2010   and save the limited number of types in ob_refcnt.
2011   This is perfect since we don't need any memory.
2012   A patch for free-threading would need just a lock.
2013 */
2014
2015 #define Py_TRASHCAN_TUPLE       1
2016 #define Py_TRASHCAN_LIST        2
2017 #define Py_TRASHCAN_DICT        3
2018 #define Py_TRASHCAN_FRAME       4
2019 #define Py_TRASHCAN_TRACEBACK   5
2020 /* extend here if other objects want protection */
2021
2022 int _PyTrash_delete_nesting = 0;
2023
2024 PyObject * _PyTrash_delete_later = NULL;
2025
2026 void
2027 _PyTrash_deposit_object(PyObject *op)
2028 {
2029         int typecode;
2030
2031         if (PyTuple_Check(op))
2032                 typecode = Py_TRASHCAN_TUPLE;
2033         else if (PyList_Check(op))
2034                 typecode = Py_TRASHCAN_LIST;
2035         else if (PyDict_Check(op))
2036                 typecode = Py_TRASHCAN_DICT;
2037         else if (PyFrame_Check(op))
2038                 typecode = Py_TRASHCAN_FRAME;
2039         else if (PyTraceBack_Check(op))
2040                 typecode = Py_TRASHCAN_TRACEBACK;
2041         else /* We have a bug here -- those are the only types in GC */ {
2042                 Py_FatalError("Type not supported in GC -- internal bug");
2043                 return; /* pacify compiler -- execution never here */
2044         }
2045         op->ob_refcnt = typecode;
2046
2047         op->ob_type = (PyTypeObject*)_PyTrash_delete_later;
2048         _PyTrash_delete_later = op;
2049 }
2050
2051 void
2052 _PyTrash_destroy_chain(void)
2053 {
2054         while (_PyTrash_delete_later) {
2055                 PyObject *shredder = _PyTrash_delete_later;
2056                 _PyTrash_delete_later = (PyObject*) shredder->ob_type;
2057
2058                 switch (shredder->ob_refcnt) {
2059                 case Py_TRASHCAN_TUPLE:
2060                         shredder->ob_type = &PyTuple_Type;
2061                         break;
2062                 case Py_TRASHCAN_LIST:
2063                         shredder->ob_type = &PyList_Type;
2064                         break;
2065                 case Py_TRASHCAN_DICT:
2066                         shredder->ob_type = &PyDict_Type;
2067                         break;
2068                 case Py_TRASHCAN_FRAME:
2069                         shredder->ob_type = &PyFrame_Type;
2070                         break;
2071                 case Py_TRASHCAN_TRACEBACK:
2072                         shredder->ob_type = &PyTraceBack_Type;
2073                         break;
2074                 }
2075                 _Py_NewReference(shredder);
2076
2077                 ++_PyTrash_delete_nesting;
2078                 Py_DECREF(shredder);
2079                 --_PyTrash_delete_nesting;
2080         }
2081 }
2082
2083 #ifdef WITH_PYMALLOC
2084 #include "obmalloc.c"
2085 #endif