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 /* Object allocation routines used by NEWOBJ and NEWVAROBJ macros.
  20    These are used by the individual routines for object creation.
  21    Do not call them otherwise, they do not initialize the object! */
  22
  23 #ifdef COUNT_ALLOCS
  24 static PyTypeObject *type_list;
  25 extern int tuple_zero_allocs, fast_tuple_allocs;
  26 extern int quick_int_allocs, quick_neg_int_allocs;
  27 extern int null_strings, one_strings;
  28 void
  29 dump_counts(void)
  30 {
  31         PyTypeObject *tp;
  32
  33         for (tp = type_list; tp; tp = tp->tp_next)
  34                 fprintf(stderr, "%s alloc'd: %d, freed: %d, max in use: %d\n",
  35                         tp->tp_name, tp->tp_alloc, tp->tp_free,
  36                         tp->tp_maxalloc);
  37         fprintf(stderr, "fast tuple allocs: %d, empty: %d\n",
  38                 fast_tuple_allocs, tuple_zero_allocs);
  39         fprintf(stderr, "fast int allocs: pos: %d, neg: %d\n",
  40                 quick_int_allocs, quick_neg_int_allocs);
  41         fprintf(stderr, "null strings: %d, 1-strings: %d\n",
  42                 null_strings, one_strings);
  43 }
  44
  45 PyObject *
  46 get_counts(void)
  47 {
  48         PyTypeObject *tp;
  49         PyObject *result;
  50         PyObject *v;
  51
  52         result = PyList_New(0);
  53         if (result == NULL)
  54                 return NULL;
  55         for (tp = type_list; tp; tp = tp->tp_next) {
  56                 v = Py_BuildValue("(siii)", tp->tp_name, tp->tp_alloc,
  57                                   tp->tp_free, tp->tp_maxalloc);
  58                 if (v == NULL) {
  59                         Py_DECREF(result);
  60                         return NULL;
  61                 }
  62                 if (PyList_Append(result, v) < 0) {
  63                         Py_DECREF(v);
  64                         Py_DECREF(result);
  65                         return NULL;
  66                 }
  67                 Py_DECREF(v);
  68         }
  69         return result;
  70 }
  71
  72 void
  73 inc_count(PyTypeObject *tp)
  74 {
  75         if (tp->tp_alloc == 0) {
  76                 /* first time; insert in linked list */
  77                 if (tp->tp_next != NULL) /* sanity check */
  78                         Py_FatalError("XXX inc_count sanity check");
  79                 tp->tp_next = type_list;
  80                 type_list = tp;
  81         }
  82         tp->tp_alloc++;
  83         if (tp->tp_alloc - tp->tp_free > tp->tp_maxalloc)
  84                 tp->tp_maxalloc = tp->tp_alloc - tp->tp_free;
  85 }
  86 #endif
  87
  88 PyObject *
  89 PyObject_Init(PyObject *op, PyTypeObject *tp)
  90 {
  91         if (op == NULL) {
  92                 PyErr_SetString(PyExc_SystemError,
  93                                 "NULL object passed to PyObject_Init");
  94                 return op;
  95         }
  96 #ifdef WITH_CYCLE_GC
  97         if (PyType_IS_GC(tp))
  98                 op = (PyObject *) PyObject_FROM_GC(op);
  99 #endif
 100         /* Any changes should be reflected in PyObject_INIT (objimpl.h) */
 101         op->ob_type = tp;
 102         _Py_NewReference(op);
 103         return op;
 104 }
 105
 106 PyVarObject *
 107 PyObject_InitVar(PyVarObject *op, PyTypeObject *tp, int size)
 108 {
 109         if (op == NULL) {
 110                 PyErr_SetString(PyExc_SystemError,
 111                                 "NULL object passed to PyObject_InitVar");
 112                 return op;
 113         }
 114 #ifdef WITH_CYCLE_GC
 115         if (PyType_IS_GC(tp))
 116                 op = (PyVarObject *) PyObject_FROM_GC(op);
 117 #endif
 118         /* Any changes should be reflected in PyObject_INIT_VAR */
 119         op->ob_size = size;
 120         op->ob_type = tp;
 121         _Py_NewReference((PyObject *)op);
 122         return op;
 123 }
 124
 125 PyObject *
 126 _PyObject_New(PyTypeObject *tp)
 127 {
 128         PyObject *op;
 129         op = (PyObject *) PyObject_MALLOC(_PyObject_SIZE(tp));
 130         if (op == NULL)
 131                 return PyErr_NoMemory();
 132 #ifdef WITH_CYCLE_GC
 133         if (PyType_IS_GC(tp))
 134                 op = (PyObject *) PyObject_FROM_GC(op);
 135 #endif
 136         return PyObject_INIT(op, tp);
 137 }
 138
 139 PyVarObject *
 140 _PyObject_NewVar(PyTypeObject *tp, int size)
 141 {
 142         PyVarObject *op;
 143         op = (PyVarObject *) PyObject_MALLOC(_PyObject_VAR_SIZE(tp, size));
 144         if (op == NULL)
 145                 return (PyVarObject *)PyErr_NoMemory();
 146 #ifdef WITH_CYCLE_GC
 147         if (PyType_IS_GC(tp))
 148                 op = (PyVarObject *) PyObject_FROM_GC(op);
 149 #endif
 150         return PyObject_INIT_VAR(op, tp, size);
 151 }
 152
 153 void
 154 _PyObject_Del(PyObject *op)
 155 {
 156 #ifdef WITH_CYCLE_GC
 157         if (op && PyType_IS_GC(op->ob_type)) {
 158                 op = (PyObject *) PyObject_AS_GC(op);
 159         }
 160 #endif
 161         PyObject_FREE(op);
 162 }
 163
 164 #ifndef WITH_CYCLE_GC
 165 /* extension modules might need these */
 166 void _PyGC_Insert(PyObject *op) { }
 167 void _PyGC_Remove(PyObject *op) { }
 168 #endif
 169
 170 int
 171 PyObject_Print(PyObject *op, FILE *fp, int flags)
 172 {
 173         int ret = 0;
 174         if (PyErr_CheckSignals())
 175                 return -1;
 176 #ifdef USE_STACKCHECK
 177         if (PyOS_CheckStack()) {
 178                 PyErr_SetString(PyExc_MemoryError, "stack overflow");
 179                 return -1;
 180         }
 181 #endif
 182         clearerr(fp); /* Clear any previous error condition */
 183         if (op == NULL) {
 184                 fprintf(fp, "<nil>");
 185         }
 186         else {
 187                 if (op->ob_refcnt <= 0)
 188                         fprintf(fp, "<refcnt %u at %p>",
 189                                 op->ob_refcnt, op);
 190                 else if (op->ob_type->tp_print == NULL) {
 191                         PyObject *s;
 192                         if (flags & Py_PRINT_RAW)
 193                                 s = PyObject_Str(op);
 194                         else
 195                                 s = PyObject_Repr(op);
 196                         if (s == NULL)
 197                                 ret = -1;
 198                         else {
 199                                 ret = PyObject_Print(s, fp, Py_PRINT_RAW);
 200                         }
 201                         Py_XDECREF(s);
 202                 }
 203                 else
 204                         ret = (*op->ob_type->tp_print)(op, fp, flags);
 205         }
 206         if (ret == 0) {
 207                 if (ferror(fp)) {
 208                         PyErr_SetFromErrno(PyExc_IOError);
 209                         clearerr(fp);
 210                         ret = -1;
 211                 }
 212         }
 213         return ret;
 214 }
 215
 216 /* For debugging convenience.  See Misc/gdbinit for some useful gdb hooks */
 217 void _PyObject_Dump(PyObject* op)
 218 {
 219         if (op == NULL)
 220                 fprintf(stderr, "NULL\n");
 221         else {
 222                 (void)PyObject_Print(op, stderr, 0);
 223                 fprintf(stderr, "\nrefcounts: %d\n", op->ob_refcnt);
 224                 fprintf(stderr, "address    : %p\n", op);
 225         }
 226 }
 227
 228 #ifdef WITH_CYCLE_GC
 229 void _PyGC_Dump(PyGC_Head* op)
 230 {
 231         _PyObject_Dump(PyObject_FROM_GC(op));
 232 }
 233 #endif /* WITH_CYCLE_GC */
 234
 235 PyObject *
 236 PyObject_Repr(PyObject *v)
 237 {
 238         if (PyErr_CheckSignals())
 239                 return NULL;
 240 #ifdef USE_STACKCHECK
 241         if (PyOS_CheckStack()) {
 242                 PyErr_SetString(PyExc_MemoryError, "stack overflow");
 243                 return NULL;
 244         }
 245 #endif
 246         if (v == NULL)
 247                 return PyString_FromString("<NULL>");
 248         else if (v->ob_type->tp_repr == NULL) {
 249                 char buf[120];
 250                 sprintf(buf, "<%.80s object at %p>",
 251                         v->ob_type->tp_name, v);
 252                 return PyString_FromString(buf);
 253         }
 254         else {
 255                 PyObject *res;
 256                 res = (*v->ob_type->tp_repr)(v);
 257                 if (res == NULL)
 258                         return NULL;
 259                 if (PyUnicode_Check(res)) {
 260                         PyObject* str;
 261                         str = PyUnicode_AsUnicodeEscapeString(res);
 262                         Py_DECREF(res);
 263                         if (str)
 264                                 res = str;
 265                         else
 266                                 return NULL;
 267                 }
 268                 if (!PyString_Check(res)) {
 269                         PyErr_Format(PyExc_TypeError,
 270                                      "__repr__ returned non-string (type %.200s)",
 271                                      res->ob_type->tp_name);
 272                         Py_DECREF(res);
 273                         return NULL;
 274                 }
 275                 return res;
 276         }
 277 }
 278
 279 PyObject *
 280 PyObject_Str(PyObject *v)
 281 {
 282         PyObject *res;
 283
 284         if (v == NULL)
 285                 return PyString_FromString("<NULL>");
 286         if (PyString_Check(v)) {
 287                 Py_INCREF(v);
 288                 return v;
 289         }
 290         if (v->ob_type->tp_str == NULL)
 291                 return PyObject_Repr(v);
 292
 293         res = (*v->ob_type->tp_str)(v);
 294         if (res == NULL)
 295                 return NULL;
 296         if (PyUnicode_Check(res)) {
 297                 PyObject* str;
 298                 str = PyUnicode_AsEncodedString(res, NULL, NULL);
 299                 Py_DECREF(res);
 300                 if (str)
 301                         res = str;
 302                 else
 303                         return NULL;
 304         }
 305         if (!PyString_Check(res)) {
 306                 PyErr_Format(PyExc_TypeError,
 307                              "__str__ returned non-string (type %.200s)",
 308                              res->ob_type->tp_name);
 309                 Py_DECREF(res);
 310                 return NULL;
 311         }
 312         return res;
 313 }
 314
 315 PyObject *
 316 PyObject_Unicode(PyObject *v)
 317 {
 318         PyObject *res;
 319
 320         if (v == NULL)
 321                 res = PyString_FromString("<NULL>");
 322         else if (PyUnicode_Check(v)) {
 323                 Py_INCREF(v);
 324                 return v;
 325         }
 326         else if (PyString_Check(v)) {
 327                 Py_INCREF(v);
 328                 res = v;
 329         }
 330         else if (v->ob_type->tp_str != NULL)
 331                 res = (*v->ob_type->tp_str)(v);
 332         else {
 333                 PyObject *func;
 334                 static PyObject *strstr;
 335                 if (strstr == NULL) {
 336                         strstr= PyString_InternFromString("__str__");
 337                         if (strstr == NULL)
 338                                 return NULL;
 339                 }
 340                 if (!PyInstance_Check(v) ||
 341                     (func = PyObject_GetAttr(v, strstr)) == NULL) {
 342                         PyErr_Clear();
 343                         res = PyObject_Repr(v);
 344                 }
 345                 else {
 346                         res = PyEval_CallObject(func, (PyObject *)NULL);
 347                         Py_DECREF(func);
 348                 }
 349         }
 350         if (res == NULL)
 351                 return NULL;
 352         if (!PyUnicode_Check(res)) {
 353                 PyObject* str;
 354                 str = PyUnicode_FromObject(res);
 355                 Py_DECREF(res);
 356                 if (str)
 357                         res = str;
 358                 else
 359                         return NULL;
 360         }
 361         return res;
 362 }
 363
 364
 365 /* Macro to get the tp_richcompare field of a type if defined */
 366 #define RICHCOMPARE(t) (PyType_HasFeature((t), Py_TPFLAGS_HAVE_RICHCOMPARE) \
 367                          ? (t)->tp_richcompare : NULL)
 368
 369 /* Map rich comparison operators to their swapped version, e.g. LT --> GT */
 370 static int swapped_op[] = {Py_GT, Py_GE, Py_EQ, Py_NE, Py_LT, Py_LE};
 371
 372 /* Try a genuine rich comparison, returning an object.  Return:
 373    NULL for exception;
 374    NotImplemented if this particular rich comparison is not implemented or
 375      undefined;
 376    some object not equal to NotImplemented if it is implemented
 377      (this latter object may not be a Boolean).
 378 */
 379 static PyObject *
 380 try_rich_compare(PyObject *v, PyObject *w, int op)
 381 {
 382         richcmpfunc f;
 383         PyObject *res;
 384
 385         if ((f = RICHCOMPARE(v->ob_type)) != NULL) {
 386                 res = (*f)(v, w, op);
 387                 if (res != Py_NotImplemented)
 388                         return res;
 389                 Py_DECREF(res);
 390         }
 391         if ((f = RICHCOMPARE(w->ob_type)) != NULL) {
 392                 return (*f)(w, v, swapped_op[op]);
 393         }
 394         res = Py_NotImplemented;
 395         Py_INCREF(res);
 396         return res;
 397 }
 398
 399 /* Try a genuine rich comparison, returning an int.  Return:
 400    -1 for exception (including the case where try_rich_compare() returns an
 401       object that's not a Boolean);
 402    0 if the outcome is false;
 403    1 if the outcome is true;
 404    2 if this particular rich comparison is not implemented or undefined.
 405 */
 406 static int
 407 try_rich_compare_bool(PyObject *v, PyObject *w, int op)
 408 {
 409         PyObject *res;
 410         int ok;
 411
 412         if (RICHCOMPARE(v->ob_type) == NULL && RICHCOMPARE(w->ob_type) == NULL)
 413                 return 2; /* Shortcut, avoid INCREF+DECREF */
 414         res = try_rich_compare(v, w, op);
 415         if (res == NULL)
 416                 return -1;
 417         if (res == Py_NotImplemented) {
 418                 Py_DECREF(res);
 419                 return 2;
 420         }
 421         ok = PyObject_IsTrue(res);
 422         Py_DECREF(res);
 423         return ok;
 424 }
 425
 426 /* Try rich comparisons to determine a 3-way comparison.  Return:
 427    -2 for an exception;
 428    -1 if v < w;
 429    0 if v == w;
 430    1 if v > w;
 431    2 if this particular rich comparison is not implemented or undefined.
 432 */
 433 static int
 434 try_rich_to_3way_compare(PyObject *v, PyObject *w)
 435 {
 436         static struct { int op; int outcome; } tries[3] = {
 437                 /* Try this operator, and if it is true, use this outcome: */
 438                 {Py_EQ, 0},
 439                 {Py_LT, -1},
 440                 {Py_GT, 1},
 441         };
 442         int i;
 443
 444         if (RICHCOMPARE(v->ob_type) == NULL && RICHCOMPARE(w->ob_type) == NULL)
 445                 return 2; /* Shortcut */
 446
 447         for (i = 0; i < 3; i++) {
 448                 switch (try_rich_compare_bool(v, w, tries[i].op)) {
 449                 case -1:
 450                         return -2;
 451                 case 1:
 452                         return tries[i].outcome;
 453                 }
 454         }
 455
 456         return 2;
 457 }
 458
 459 /* Try a 3-way comparison, returning an int.  Return:
 460    -2 for an exception;
 461    -1 if v < w;
 462    0 if v == w;
 463    1 if v > w;
 464    2 if this particular 3-way comparison is not implemented or undefined.
 465 */
 466 static int
 467 try_3way_compare(PyObject *v, PyObject *w)
 468 {
 469         int c;
 470         cmpfunc f;
 471
 472         /* Comparisons involving instances are given to instance_compare,
 473            which has the same return conventions as this function. */
 474
 475         if (PyInstance_Check(v))
 476                 return (*v->ob_type->tp_compare)(v, w);
 477         if (PyInstance_Check(w))
 478                 return (*w->ob_type->tp_compare)(v, w);
 479
 480         /* Try coercion; if it fails, give up */
 481         c = PyNumber_CoerceEx(&v, &w);
 482         if (c < 0)
 483                 return -2;
 484         if (c > 0)
 485                 return 2;
 486
 487         /* Try v's comparison, if defined */
 488         if ((f = v->ob_type->tp_compare) != NULL) {
 489                 c = (*f)(v, w);
 490                 Py_DECREF(v);
 491                 Py_DECREF(w);
 492                 if (c < 0 && PyErr_Occurred())
 493                         return -2;
 494                 return c < 0 ? -1 : c > 0 ? 1 : 0;
 495         }
 496
 497         /* Try w's comparison, if defined */
 498         if ((f = w->ob_type->tp_compare) != NULL) {
 499                 c = (*f)(w, v); /* swapped! */
 500                 Py_DECREF(v);
 501                 Py_DECREF(w);
 502                 if (c < 0 && PyErr_Occurred())
 503                         return -2;
 504                 return c < 0 ? 1 : c > 0 ? -1 : 0; /* negated! */
 505         }
 506
 507         /* No comparison defined */
 508         Py_DECREF(v);
 509         Py_DECREF(w);
 510         return 2;
 511 }
 512
 513 /* Final fallback 3-way comparison, returning an int.  Return:
 514    -2 if an error occurred;
 515    -1 if v < w;
 516    0 if v == w;
 517    1 if v > w.
 518 */
 519 static int
 520 default_3way_compare(PyObject *v, PyObject *w)
 521 {
 522         int c;
 523         char *vname, *wname;
 524
 525         if (v->ob_type == w->ob_type) {
 526                 /* When comparing these pointers, they must be cast to
 527                  * integer types (i.e. Py_uintptr_t, our spelling of C9X's
 528                  * uintptr_t).  ANSI specifies that pointer compares other
 529                  * than == and != to non-related structures are undefined.
 530                  */
 531                 Py_uintptr_t vv = (Py_uintptr_t)v;
 532                 Py_uintptr_t ww = (Py_uintptr_t)w;
 533                 return (vv < ww) ? -1 : (vv > ww) ? 1 : 0;
 534         }
 535
 536         /* Special case for Unicode */
 537         if (PyUnicode_Check(v) || PyUnicode_Check(w)) {
 538                 c = PyUnicode_Compare(v, w);
 539                 if (!PyErr_Occurred())
 540                         return c;
 541                 /* TypeErrors are ignored: if Unicode coercion fails due
 542                    to one of the arguments not having the right type, we
 543                    continue as defined by the coercion protocol (see
 544                    above).  Luckily, decoding errors are reported as
 545                    ValueErrors and are not masked by this technique. */
 546                 if (!PyErr_ExceptionMatches(PyExc_TypeError))
 547                         return -2;
 548                 PyErr_Clear();
 549         }
 550
 551         /* None is smaller than anything */
 552         if (v == Py_None)
 553                 return -1;
 554         if (w == Py_None)
 555                 return 1;
 556
 557         /* different type: compare type names */
 558         if (v->ob_type->tp_as_number)
 559                 vname = "";
 560         else
 561                 vname = v->ob_type->tp_name;
 562         if (w->ob_type->tp_as_number)
 563                 wname = "";
 564         else
 565                 wname = w->ob_type->tp_name;
 566         c = strcmp(vname, wname);
 567         if (c < 0)
 568                 return -1;
 569         if (c > 0)
 570                 return 1;
 571         /* Same type name, or (more likely) incomparable numeric types */
 572         return ((Py_uintptr_t)(v->ob_type) < (
 573                 Py_uintptr_t)(w->ob_type)) ? -1 : 1;
 574 }
 575
 576 #define CHECK_TYPES(o) PyType_HasFeature((o)->ob_type, Py_TPFLAGS_CHECKTYPES)
 577
 578 /* Do a 3-way comparison, by hook or by crook.  Return:
 579    -2 for an exception;
 580    -1 if v < w;
 581     0 if v == w;
 582     1 if v > w;
 583    If the object implements a tp_compare function, it returns
 584    whatever this function returns (whether with an exception or not).
 585 */
 586 static int
 587 do_cmp(PyObject *v, PyObject *w)
 588 {
 589         int c;
 590         cmpfunc f;
 591
 592         if (v->ob_type == w->ob_type
 593             && (f = v->ob_type->tp_compare) != NULL)
 594                 return (*f)(v, w);
 595         c = try_rich_to_3way_compare(v, w);
 596         if (c < 2)
 597                 return c;
 598         c = try_3way_compare(v, w);
 599         if (c < 2)
 600                 return c;
 601         return default_3way_compare(v, w);
 602 }
 603
 604 /* compare_nesting is incremented before calling compare (for
 605    some types) and decremented on exit.  If the count exceeds the
 606    nesting limit, enable code to detect circular data structures.
 607
 608    This is a tunable parameter that should only affect the performance
 609    of comparisons, nothing else.  Setting it high makes comparing deeply
 610    nested non-cyclical data structures faster, but makes comparing cyclical
 611    data structures slower.
 612 */
 613 #define NESTING_LIMIT 20
 614
 615 static int compare_nesting = 0;
 616
 617 static PyObject*
 618 get_inprogress_dict(void)
 619 {
 620         static PyObject *key;
 621         PyObject *tstate_dict, *inprogress;
 622
 623         if (key == NULL) {
 624                 key = PyString_InternFromString("cmp_state");
 625                 if (key == NULL)
 626                         return NULL;
 627         }
 628
 629         tstate_dict = PyThreadState_GetDict();
 630         if (tstate_dict == NULL) {
 631                 PyErr_BadInternalCall();
 632                 return NULL;
 633         }
 634
 635         inprogress = PyDict_GetItem(tstate_dict, key);
 636         if (inprogress == NULL) {
 637                 inprogress = PyDict_New();
 638                 if (inprogress == NULL)
 639                         return NULL;
 640                 if (PyDict_SetItem(tstate_dict, key, inprogress) == -1) {
 641                     Py_DECREF(inprogress);
 642                     return NULL;
 643                 }
 644                 Py_DECREF(inprogress);
 645         }
 646
 647         return inprogress;
 648 }
 649
 650 static PyObject *
 651 check_recursion(PyObject *v, PyObject *w, int op)
 652 {
 653         PyObject *inprogress;
 654         PyObject *token;
 655         Py_uintptr_t iv = (Py_uintptr_t)v;
 656         Py_uintptr_t iw = (Py_uintptr_t)w;
 657         PyObject *x, *y, *z;
 658
 659         inprogress = get_inprogress_dict();
 660         if (inprogress == NULL)
 661                 return NULL;
 662
 663         token = PyTuple_New(3);
 664         if (token == NULL)
 665                 return NULL;
 666
 667         if (iv <= iw) {
 668                 PyTuple_SET_ITEM(token, 0, x = PyLong_FromVoidPtr((void *)v));
 669                 PyTuple_SET_ITEM(token, 1, y = PyLong_FromVoidPtr((void *)w));
 670                 if (op >= 0)
 671                         op = swapped_op[op];
 672         } else {
 673                 PyTuple_SET_ITEM(token, 0, x = PyLong_FromVoidPtr((void *)w));
 674                 PyTuple_SET_ITEM(token, 1, y = PyLong_FromVoidPtr((void *)v));
 675         }
 676         PyTuple_SET_ITEM(token, 2, z = PyInt_FromLong((long)op));
 677         if (x == NULL || y == NULL || z == NULL) {
 678                 Py_DECREF(token);
 679                 return NULL;
 680         }
 681
 682         if (PyDict_GetItem(inprogress, token) != NULL) {
 683                 Py_DECREF(token);
 684                 return Py_None; /* Without INCREF! */
 685         }
 686
 687         if (PyDict_SetItem(inprogress, token, token) < 0) {
 688                 Py_DECREF(token);
 689                 return NULL;
 690         }
 691
 692         return token;
 693 }
 694
 695 static void
 696 delete_token(PyObject *token)
 697 {
 698         PyObject *inprogress;
 699
 700         if (token == NULL || token == Py_None)
 701                 return;
 702         inprogress = get_inprogress_dict();
 703         if (inprogress == NULL)
 704                 PyErr_Clear();
 705         else
 706                 PyDict_DelItem(inprogress, token);
 707         Py_DECREF(token);
 708 }
 709
 710 int
 711 PyObject_Compare(PyObject *v, PyObject *w)
 712 {
 713         PyTypeObject *vtp;
 714         int result;
 715
 716 #if defined(USE_STACKCHECK)
 717         if (PyOS_CheckStack()) {
 718                 PyErr_SetString(PyExc_MemoryError, "Stack overflow");
 719         return -1;
 720         }
 721 #endif
 722         if (v == NULL || w == NULL) {
 723                 PyErr_BadInternalCall();
 724                 return -1;
 725         }
 726         if (v == w)
 727                 return 0;
 728         vtp = v->ob_type;
 729         compare_nesting++;
 730         if (compare_nesting > NESTING_LIMIT &&
 731                 (vtp->tp_as_mapping
 732                  || (vtp->tp_as_sequence
 733                      && !PyString_Check(v)
 734                      && !PyTuple_Check(v)))) {
 735                 /* try to detect circular data structures */
 736                 PyObject *token = check_recursion(v, w, -1);
 737
 738                 if (token == NULL) {
 739                         result = -1;
 740                 }
 741                 else if (token == Py_None) {
 742                         /* already comparing these objects.  assume
 743                            they're equal until shown otherwise */
 744                         result = 0;
 745                 }
 746                 else {
 747                         result = do_cmp(v, w);
 748                         delete_token(token);
 749                 }
 750         }
 751         else {
 752                 result = do_cmp(v, w);
 753         }
 754         compare_nesting--;
 755         return result < 0 ? -1 : result;
 756 }
 757
 758 static PyObject *
 759 convert_3way_to_object(int op, int c)
 760 {
 761         PyObject *result;
 762         switch (op) {
 763         case Py_LT: c = c <  0; break;
 764         case Py_LE: c = c <= 0; break;
 765         case Py_EQ: c = c == 0; break;
 766         case Py_NE: c = c != 0; break;
 767         case Py_GT: c = c >  0; break;
 768         case Py_GE: c = c >= 0; break;
 769         }
 770         result = c ? Py_True : Py_False;
 771         Py_INCREF(result);
 772         return result;
 773 }
 774
 775
 776 static PyObject *
 777 try_3way_to_rich_compare(PyObject *v, PyObject *w, int op)
 778 {
 779         int c;
 780
 781         c = try_3way_compare(v, w);
 782         if (c >= 2)
 783                 c = default_3way_compare(v, w);
 784         if (c <= -2)
 785                 return NULL;
 786         return convert_3way_to_object(op, c);
 787 }
 788
 789 static PyObject *
 790 do_richcmp(PyObject *v, PyObject *w, int op)
 791 {
 792         PyObject *res;
 793         cmpfunc f;
 794
 795         /* If the types are equal, don't bother with coercions etc.
 796            Instances are special-cased in try_3way_compare, since
 797            a result of 2 does *not* mean one value being greater
 798            than the other. */
 799         if (v->ob_type == w->ob_type
 800             && (f = v->ob_type->tp_compare) != NULL
 801             && !PyInstance_Check(v)) {
 802                 int c;
 803                 richcmpfunc f1;
 804                 if ((f1 = RICHCOMPARE(v->ob_type)) != NULL) {
 805                         /* If the type has richcmp, try it first.
 806                            try_rich_compare would try it two-sided,
 807                            which is not needed since we've a single
 808                            type only. */
 809                         res = (*f1)(v, w, op);
 810                         if (res != Py_NotImplemented)
 811                                 return res;
 812                         Py_DECREF(res);
 813                 }
 814                 c = (*f)(v, w);
 815                 if (c < 0 && PyErr_Occurred())
 816                         return NULL;
 817                 return convert_3way_to_object(op, c);
 818         }
 819
 820         res = try_rich_compare(v, w, op);
 821         if (res != Py_NotImplemented)
 822                 return res;
 823         Py_DECREF(res);
 824
 825         return try_3way_to_rich_compare(v, w, op);
 826 }
 827
 828 PyObject *
 829 PyObject_RichCompare(PyObject *v, PyObject *w, int op)
 830 {
 831         PyObject *res;
 832
 833         assert(Py_LT <= op && op <= Py_GE);
 834
 835         compare_nesting++;
 836         if (compare_nesting > NESTING_LIMIT &&
 837                 (v->ob_type->tp_as_mapping
 838                  || (v->ob_type->tp_as_sequence
 839                      && !PyString_Check(v)
 840                      && !PyTuple_Check(v)))) {
 841                 /* try to detect circular data structures */
 842                 PyObject *token = check_recursion(v, w, op);
 843
 844                 if (token == NULL) {
 845                         res = NULL;
 846                 }
 847                 else if (token == Py_None) {
 848                         /* already comparing these objects with this operator.
 849                            assume they're equal until shown otherwise */
 850                         if (op == Py_EQ)
 851                                 res = Py_True;
 852                         else if (op == Py_NE)
 853                                 res = Py_False;
 854                         else {
 855                                 PyErr_SetString(PyExc_ValueError,
 856                                         "can't order recursive values");
 857                                 res = NULL;
 858                         }
 859                         Py_XINCREF(res);
 860                 }
 861                 else {
 862                         res = do_richcmp(v, w, op);
 863                         delete_token(token);
 864                 }
 865         }
 866         else {
 867                 res = do_richcmp(v, w, op);
 868         }
 869         compare_nesting--;
 870         return res;
 871 }
 872
 873 /* Return -1 if error; 1 if v op w; 0 if not (v op w). */
 874 int
 875 PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
 876 {
 877         PyObject *res = PyObject_RichCompare(v, w, op);
 878         int ok;
 879
 880         if (res == NULL)
 881                 return -1;
 882         ok = PyObject_IsTrue(res);
 883         Py_DECREF(res);
 884         return ok;
 885 }
 886
 887 /* Set of hash utility functions to help maintaining the invariant that
 888         iff a==b then hash(a)==hash(b)
 889
 890    All the utility functions (_Py_Hash*()) return "-1" to signify an error.
 891 */
 892
 893 long
 894 _Py_HashDouble(double v)
 895 {
 896         double intpart, fractpart;
 897         int expo;
 898         long hipart;
 899         long x;         /* the final hash value */
 900         /* This is designed so that Python numbers of different types
 901          * that compare equal hash to the same value; otherwise comparisons
 902          * of mapping keys will turn out weird.
 903          */
 904
 905 #ifdef MPW /* MPW C modf expects pointer to extended as second argument */
 906 {
 907         extended e;
 908         fractpart = modf(v, &e);
 909         intpart = e;
 910 }
 911 #else
 912         fractpart = modf(v, &intpart);
 913 #endif
 914         if (fractpart == 0.0) {
 915                 /* This must return the same hash as an equal int or long. */
 916                 if (intpart > LONG_MAX || -intpart > LONG_MAX) {
 917                         /* Convert to long and use its hash. */
 918                         PyObject *plong;        /* converted to Python long */
 919                         if (Py_IS_INFINITY(intpart))
 920                                 /* can't convert to long int -- arbitrary */
 921                                 v = v < 0 ? -271828.0 : 314159.0;
 922                         plong = PyLong_FromDouble(v);
 923                         if (plong == NULL)
 924                                 return -1;
 925                         x = PyObject_Hash(plong);
 926                         Py_DECREF(plong);
 927                         return x;
 928                 }
 929                 /* Fits in a C long == a Python int, so is its own hash. */
 930                 x = (long)intpart;
 931                 if (x == -1)
 932                         x = -2;
 933                 return x;
 934         }
 935         /* The fractional part is non-zero, so we don't have to worry about
 936          * making this match the hash of some other type.
 937          * Use frexp to get at the bits in the double.
 938          * Since the VAX D double format has 56 mantissa bits, which is the
 939          * most of any double format in use, each of these parts may have as
 940          * many as (but no more than) 56 significant bits.
 941          * So, assuming sizeof(long) >= 4, each part can be broken into two
 942          * longs; frexp and multiplication are used to do that.
 943          * Also, since the Cray double format has 15 exponent bits, which is
 944          * the most of any double format in use, shifting the exponent field
 945          * left by 15 won't overflow a long (again assuming sizeof(long) >= 4).
 946          */
 947         v = frexp(v, &expo);
 948         v *= 2147483648.0;      /* 2**31 */
 949         hipart = (long)v;       /* take the top 32 bits */
 950         v = (v - (double)hipart) * 2147483648.0; /* get the next 32 bits */
 951         x = hipart + (long)v + (expo << 15);
 952         if (x == -1)
 953                 x = -2;
 954         return x;
 955 }
 956
 957 long
 958 _Py_HashPointer(void *p)
 959 {
 960 #if SIZEOF_LONG >= SIZEOF_VOID_P
 961         return (long)p;
 962 #else
 963         /* convert to a Python long and hash that */
 964         PyObject* longobj;
 965         long x;
 966
 967         if ((longobj = PyLong_FromVoidPtr(p)) == NULL) {
 968                 x = -1;
 969                 goto finally;
 970         }
 971         x = PyObject_Hash(longobj);
 972
 973 finally:
 974         Py_XDECREF(longobj);
 975         return x;
 976 #endif
 977 }
 978
 979
 980 long
 981 PyObject_Hash(PyObject *v)
 982 {
 983         PyTypeObject *tp = v->ob_type;
 984         if (tp->tp_hash != NULL)
 985                 return (*tp->tp_hash)(v);
 986         if (tp->tp_compare == NULL && RICHCOMPARE(tp) == NULL) {
 987                 return _Py_HashPointer(v); /* Use address as hash value */
 988         }
 989         /* If there's a cmp but no hash defined, the object can't be hashed */
 990         PyErr_SetString(PyExc_TypeError, "unhashable type");
 991         return -1;
 992 }
 993
 994 PyObject *
 995 PyObject_GetAttrString(PyObject *v, char *name)
 996 {
 997         if (v->ob_type->tp_getattro != NULL) {
 998                 PyObject *w, *res;
 999                 w = PyString_InternFromString(name);
1000                 if (w == NULL)
1001                         return NULL;
1002                 res = (*v->ob_type->tp_getattro)(v, w);
1003                 Py_XDECREF(w);
1004                 return res;
1005         }
1006
1007         if (v->ob_type->tp_getattr == NULL) {
1008                 PyErr_Format(PyExc_AttributeError,
1009                              "'%.50s' object has no attribute '%.400s'",
1010                              v->ob_type->tp_name,
1011                              name);
1012                 return NULL;
1013         }
1014         else {
1015                 return (*v->ob_type->tp_getattr)(v, name);
1016         }
1017 }
1018
1019 int
1020 PyObject_HasAttrString(PyObject *v, char *name)
1021 {
1022         PyObject *res = PyObject_GetAttrString(v, name);
1023         if (res != NULL) {
1024                 Py_DECREF(res);
1025                 return 1;
1026         }
1027         PyErr_Clear();
1028         return 0;
1029 }
1030
1031 int
1032 PyObject_SetAttrString(PyObject *v, char *name, PyObject *w)
1033 {
1034         if (v->ob_type->tp_setattro != NULL) {
1035                 PyObject *s;
1036                 int res;
1037                 s = PyString_InternFromString(name);
1038                 if (s == NULL)
1039                         return -1;
1040                 res = (*v->ob_type->tp_setattro)(v, s, w);
1041                 Py_XDECREF(s);
1042                 return res;
1043         }
1044
1045         if (v->ob_type->tp_setattr == NULL) {
1046                 if (v->ob_type->tp_getattr == NULL)
1047                         PyErr_SetString(PyExc_TypeError,
1048                                    "attribute-less object (assign or del)");
1049                 else
1050                         PyErr_SetString(PyExc_TypeError,
1051                                    "object has read-only attributes");
1052                 return -1;
1053         }
1054         else {
1055                 return (*v->ob_type->tp_setattr)(v, name, w);
1056         }
1057 }
1058
1059 /* Internal API needed by PyObject_GetAttr(): */
1060 extern
1061 PyObject *_PyUnicode_AsDefaultEncodedString(PyObject *unicode,
1062                                   const char *errors);
1063
1064 PyObject *
1065 PyObject_GetAttr(PyObject *v, PyObject *name)
1066 {
1067         /* The Unicode to string conversion is done here because the
1068            existing tp_getattro slots expect a string object as name
1069            and we wouldn't want to break those. */
1070         if (PyUnicode_Check(name)) {
1071                 name = _PyUnicode_AsDefaultEncodedString(name, NULL);
1072                 if (name == NULL)
1073                         return NULL;
1074         }
1075
1076         if (!PyString_Check(name)) {
1077                 PyErr_SetString(PyExc_TypeError,
1078                                 "attribute name must be string");
1079                 return NULL;
1080         }
1081         if (v->ob_type->tp_getattro != NULL)
1082                 return (*v->ob_type->tp_getattro)(v, name);
1083         else
1084                 return PyObject_GetAttrString(v, PyString_AS_STRING(name));
1085 }
1086
1087 int
1088 PyObject_HasAttr(PyObject *v, PyObject *name)
1089 {
1090         PyObject *res = PyObject_GetAttr(v, name);
1091         if (res != NULL) {
1092                 Py_DECREF(res);
1093                 return 1;
1094         }
1095         PyErr_Clear();
1096         return 0;
1097 }
1098
1099 int
1100 PyObject_SetAttr(PyObject *v, PyObject *name, PyObject *value)
1101 {
1102         int err;
1103
1104         /* The Unicode to string conversion is done here because the
1105            existing tp_setattro slots expect a string object as name
1106            and we wouldn't want to break those. */
1107         if (PyUnicode_Check(name)) {
1108                 name = PyUnicode_AsEncodedString(name, NULL, NULL);
1109                 if (name == NULL)
1110                         return -1;
1111         }
1112         else
1113                 Py_INCREF(name);
1114
1115         if (!PyString_Check(name)){
1116                 PyErr_SetString(PyExc_TypeError,
1117                                 "attribute name must be string");
1118                 err = -1;
1119         }
1120         else {
1121                 PyString_InternInPlace(&name);
1122                 if (v->ob_type->tp_setattro != NULL)
1123                         err = (*v->ob_type->tp_setattro)(v, name, value);
1124                 else
1125                         err = PyObject_SetAttrString(v,
1126                                         PyString_AS_STRING(name), value);
1127         }
1128
1129         Py_DECREF(name);
1130         return err;
1131 }
1132
1133 /* Test a value used as condition, e.g., in a for or if statement.
1134    Return -1 if an error occurred */
1135
1136 int
1137 PyObject_IsTrue(PyObject *v)
1138 {
1139         int res;
1140         if (v == Py_None)
1141                 res = 0;
1142         else if (v->ob_type->tp_as_number != NULL &&
1143                  v->ob_type->tp_as_number->nb_nonzero != NULL)
1144                 res = (*v->ob_type->tp_as_number->nb_nonzero)(v);
1145         else if (v->ob_type->tp_as_mapping != NULL &&
1146                  v->ob_type->tp_as_mapping->mp_length != NULL)
1147                 res = (*v->ob_type->tp_as_mapping->mp_length)(v);
1148         else if (v->ob_type->tp_as_sequence != NULL &&
1149                  v->ob_type->tp_as_sequence->sq_length != NULL)
1150                 res = (*v->ob_type->tp_as_sequence->sq_length)(v);
1151         else
1152                 res = 1;
1153         if (res > 0)
1154                 res = 1;
1155         return res;
1156 }
1157
1158 /* equivalent of 'not v'
1159    Return -1 if an error occurred */
1160
1161 int
1162 PyObject_Not(PyObject *v)
1163 {
1164         int res;
1165         res = PyObject_IsTrue(v);
1166         if (res < 0)
1167                 return res;
1168         return res == 0;
1169 }
1170
1171 /* Coerce two numeric types to the "larger" one.
1172    Increment the reference count on each argument.
1173    Return value:
1174    -1 if an error occurred;
1175    0 if the coercion succeeded (and then the reference counts are increased);
1176    1 if no coercion is possible (and no error is raised).
1177 */
1178 int
1179 PyNumber_CoerceEx(PyObject **pv, PyObject **pw)
1180 {
1181         register PyObject *v = *pv;
1182         register PyObject *w = *pw;
1183         int res;
1184
1185         if (v->ob_type == w->ob_type && !PyInstance_Check(v)) {
1186                 Py_INCREF(v);
1187                 Py_INCREF(w);
1188                 return 0;
1189         }
1190         if (v->ob_type->tp_as_number && v->ob_type->tp_as_number->nb_coerce) {
1191                 res = (*v->ob_type->tp_as_number->nb_coerce)(pv, pw);
1192                 if (res <= 0)
1193                         return res;
1194         }
1195         if (w->ob_type->tp_as_number && w->ob_type->tp_as_number->nb_coerce) {
1196                 res = (*w->ob_type->tp_as_number->nb_coerce)(pw, pv);
1197                 if (res <= 0)
1198                         return res;
1199         }
1200         return 1;
1201 }
1202
1203 /* Coerce two numeric types to the "larger" one.
1204    Increment the reference count on each argument.
1205    Return -1 and raise an exception if no coercion is possible
1206    (and then no reference count is incremented).
1207 */
1208 int
1209 PyNumber_Coerce(PyObject **pv, PyObject **pw)
1210 {
1211         int err = PyNumber_CoerceEx(pv, pw);
1212         if (err <= 0)
1213                 return err;
1214         PyErr_SetString(PyExc_TypeError, "number coercion failed");
1215         return -1;
1216 }
1217
1218
1219 /* Test whether an object can be called */
1220
1221 int
1222 PyCallable_Check(PyObject *x)
1223 {
1224         if (x == NULL)
1225                 return 0;
1226         if (x->ob_type->tp_call != NULL ||
1227             PyFunction_Check(x) ||
1228             PyMethod_Check(x) ||
1229             PyCFunction_Check(x) ||
1230             PyClass_Check(x))
1231                 return 1;
1232         if (PyInstance_Check(x)) {
1233                 PyObject *call = PyObject_GetAttrString(x, "__call__");
1234                 if (call == NULL) {
1235                         PyErr_Clear();
1236                         return 0;
1237                 }
1238                 /* Could test recursively but don't, for fear of endless
1239                    recursion if some joker sets self.__call__ = self */
1240                 Py_DECREF(call);
1241                 return 1;
1242         }
1243         return 0;
1244 }
1245
1246
1247 /*
1248 NoObject is usable as a non-NULL undefined value, used by the macro None.
1249 There is (and should be!) no way to create other objects of this type,
1250 so there is exactly one (which is indestructible, by the way).
1251 */
1252
1253 /* ARGSUSED */
1254 static PyObject *
1255 none_repr(PyObject *op)
1256 {
1257         return PyString_FromString("None");
1258 }
1259
1260 /* ARGUSED */
1261 static void
1262 none_dealloc(PyObject* ignore)
1263 {
1264         /* This should never get called, but we also don't want to SEGV if
1265          * we accidently decref None out of existance.
1266          */
1267         abort();
1268 }
1269
1270
1271 static PyTypeObject PyNothing_Type = {
1272         PyObject_HEAD_INIT(&PyType_Type)
1273         0,
1274         "None",
1275         0,
1276         0,
1277         (destructor)none_dealloc,            /*tp_dealloc*/ /*never called*/
1278         0,              /*tp_print*/
1279         0,              /*tp_getattr*/
1280         0,              /*tp_setattr*/
1281         0,              /*tp_compare*/
1282         (reprfunc)none_repr, /*tp_repr*/
1283         0,              /*tp_as_number*/
1284         0,              /*tp_as_sequence*/
1285         0,              /*tp_as_mapping*/
1286         0,              /*tp_hash */
1287 };
1288
1289 PyObject _Py_NoneStruct = {
1290         PyObject_HEAD_INIT(&PyNothing_Type)
1291 };
1292
1293 /* NotImplemented is an object that can be used to signal that an
1294    operation is not implemented for the given type combination. */
1295
1296 static PyObject *
1297 NotImplemented_repr(PyObject *op)
1298 {
1299         return PyString_FromString("NotImplemented");
1300 }
1301
1302 static PyTypeObject PyNotImplemented_Type = {
1303         PyObject_HEAD_INIT(&PyType_Type)
1304         0,
1305         "NotImplemented",
1306         0,
1307         0,
1308         (destructor)none_dealloc,            /*tp_dealloc*/ /*never called*/
1309         0,              /*tp_print*/
1310         0,              /*tp_getattr*/
1311         0,              /*tp_setattr*/
1312         0,              /*tp_compare*/
1313         (reprfunc)NotImplemented_repr, /*tp_repr*/
1314         0,              /*tp_as_number*/
1315         0,              /*tp_as_sequence*/
1316         0,              /*tp_as_mapping*/
1317         0,              /*tp_hash */
1318 };
1319
1320 PyObject _Py_NotImplementedStruct = {
1321         PyObject_HEAD_INIT(&PyNotImplemented_Type)
1322 };
1323
1324
1325 #ifdef Py_TRACE_REFS
1326
1327 static PyObject refchain = {&refchain, &refchain};
1328
1329 void
1330 _Py_ResetReferences(void)
1331 {
1332         refchain._ob_prev = refchain._ob_next = &refchain;
1333         _Py_RefTotal = 0;
1334 }
1335
1336 void
1337 _Py_NewReference(PyObject *op)
1338 {
1339         _Py_RefTotal++;
1340         op->ob_refcnt = 1;
1341         op->_ob_next = refchain._ob_next;
1342         op->_ob_prev = &refchain;
1343         refchain._ob_next->_ob_prev = op;
1344         refchain._ob_next = op;
1345 #ifdef COUNT_ALLOCS
1346         inc_count(op->ob_type);
1347 #endif
1348 }
1349
1350 void
1351 _Py_ForgetReference(register PyObject *op)
1352 {
1353 #ifdef SLOW_UNREF_CHECK
1354         register PyObject *p;
1355 #endif
1356         if (op->ob_refcnt < 0)
1357                 Py_FatalError("UNREF negative refcnt");
1358         if (op == &refchain ||
1359             op->_ob_prev->_ob_next != op || op->_ob_next->_ob_prev != op)
1360                 Py_FatalError("UNREF invalid object");
1361 #ifdef SLOW_UNREF_CHECK
1362         for (p = refchain._ob_next; p != &refchain; p = p->_ob_next) {
1363                 if (p == op)
1364                         break;
1365         }
1366         if (p == &refchain) /* Not found */
1367                 Py_FatalError("UNREF unknown object");
1368 #endif
1369         op->_ob_next->_ob_prev = op->_ob_prev;
1370         op->_ob_prev->_ob_next = op->_ob_next;
1371         op->_ob_next = op->_ob_prev = NULL;
1372 #ifdef COUNT_ALLOCS
1373         op->ob_type->tp_free++;
1374 #endif
1375 }
1376
1377 void
1378 _Py_Dealloc(PyObject *op)
1379 {
1380         destructor dealloc = op->ob_type->tp_dealloc;
1381         _Py_ForgetReference(op);
1382         (*dealloc)(op);
1383 }
1384
1385 void
1386 _Py_PrintReferences(FILE *fp)
1387 {
1388         PyObject *op;
1389         fprintf(fp, "Remaining objects:\n");
1390         for (op = refchain._ob_next; op != &refchain; op = op->_ob_next) {
1391                 fprintf(fp, "[%d] ", op->ob_refcnt);
1392                 if (PyObject_Print(op, fp, 0) != 0)
1393                         PyErr_Clear();
1394                 putc('\n', fp);
1395         }
1396 }
1397
1398 PyObject *
1399 _Py_GetObjects(PyObject *self, PyObject *args)
1400 {
1401         int i, n;
1402         PyObject *t = NULL;
1403         PyObject *res, *op;
1404
1405         if (!PyArg_ParseTuple(args, "i|O", &n, &t))
1406                 return NULL;
1407         op = refchain._ob_next;
1408         res = PyList_New(0);
1409         if (res == NULL)
1410                 return NULL;
1411         for (i = 0; (n == 0 || i < n) && op != &refchain; i++) {
1412                 while (op == self || op == args || op == res || op == t ||
1413                        t != NULL && op->ob_type != (PyTypeObject *) t) {
1414                         op = op->_ob_next;
1415                         if (op == &refchain)
1416                                 return res;
1417                 }
1418                 if (PyList_Append(res, op) < 0) {
1419                         Py_DECREF(res);
1420                         return NULL;
1421                 }
1422                 op = op->_ob_next;
1423         }
1424         return res;
1425 }
1426
1427 #endif
1428
1429
1430 /* Hack to force loading of cobject.o */
1431 PyTypeObject *_Py_cobject_hack = &PyCObject_Type;
1432
1433
1434 /* Hack to force loading of abstract.o */
1435 int (*_Py_abstract_hack)(PyObject *) = &PyObject_Size;
1436
1437
1438 /* Python's malloc wrappers (see pymem.h) */
1439
1440 void *
1441 PyMem_Malloc(size_t nbytes)
1442 {
1443 #if _PyMem_EXTRA > 0
1444         if (nbytes == 0)
1445                 nbytes = _PyMem_EXTRA;
1446 #endif
1447         return PyMem_MALLOC(nbytes);
1448 }
1449
1450 void *
1451 PyMem_Realloc(void *p, size_t nbytes)
1452 {
1453 #if _PyMem_EXTRA > 0
1454         if (nbytes == 0)
1455                 nbytes = _PyMem_EXTRA;
1456 #endif
1457         return PyMem_REALLOC(p, nbytes);
1458 }
1459
1460 void
1461 PyMem_Free(void *p)
1462 {
1463         PyMem_FREE(p);
1464 }
1465
1466
1467 /* Python's object malloc wrappers (see objimpl.h) */
1468
1469 void *
1470 PyObject_Malloc(size_t nbytes)
1471 {
1472         return PyObject_MALLOC(nbytes);
1473 }
1474
1475 void *
1476 PyObject_Realloc(void *p, size_t nbytes)
1477 {
1478         return PyObject_REALLOC(p, nbytes);
1479 }
1480
1481 void
1482 PyObject_Free(void *p)
1483 {
1484         PyObject_FREE(p);
1485 }
1486
1487
1488 /* Hook to clear up weak references only once the _weakref module is
1489    imported.  We use a dummy implementation to simplify the code at each
1490    call site instead of requiring a test for NULL.
1491 */
1492
1493 static void
1494 empty_clear_weak_refs(PyObject *o)
1495 {
1496     return;
1497 }
1498
1499 void (*PyObject_ClearWeakRefs)(PyObject *) = empty_clear_weak_refs;
1500
1501
1502
1503 /* These methods are used to control infinite recursion in repr, str, print,
1504    etc.  Container objects that may recursively contain themselves,
1505    e.g. builtin dictionaries and lists, should used Py_ReprEnter() and
1506    Py_ReprLeave() to avoid infinite recursion.
1507
1508    Py_ReprEnter() returns 0 the first time it is called for a particular
1509    object and 1 every time thereafter.  It returns -1 if an exception
1510    occurred.  Py_ReprLeave() has no return value.
1511
1512    See dictobject.c and listobject.c for examples of use.
1513 */
1514
1515 #define KEY "Py_Repr"
1516
1517 int
1518 Py_ReprEnter(PyObject *obj)
1519 {
1520         PyObject *dict;
1521         PyObject *list;
1522         int i;
1523
1524         dict = PyThreadState_GetDict();
1525         if (dict == NULL)
1526                 return -1;
1527         list = PyDict_GetItemString(dict, KEY);
1528         if (list == NULL) {
1529                 list = PyList_New(0);
1530                 if (list == NULL)
1531                         return -1;
1532                 if (PyDict_SetItemString(dict, KEY, list) < 0)
1533                         return -1;
1534                 Py_DECREF(list);
1535         }
1536         i = PyList_GET_SIZE(list);
1537         while (--i >= 0) {
1538                 if (PyList_GET_ITEM(list, i) == obj)
1539                         return 1;
1540         }
1541         PyList_Append(list, obj);
1542         return 0;
1543 }
1544
1545 void
1546 Py_ReprLeave(PyObject *obj)
1547 {
1548         PyObject *dict;
1549         PyObject *list;
1550         int i;
1551
1552         dict = PyThreadState_GetDict();
1553         if (dict == NULL)
1554                 return;
1555         list = PyDict_GetItemString(dict, KEY);
1556         if (list == NULL || !PyList_Check(list))
1557                 return;
1558         i = PyList_GET_SIZE(list);
1559         /* Count backwards because we always expect obj to be list[-1] */
1560         while (--i >= 0) {
1561                 if (PyList_GET_ITEM(list, i) == obj) {
1562                         PyList_SetSlice(list, i, i + 1, NULL);
1563                         break;
1564                 }
1565         }
1566 }
1567
1568 /*
1569   trashcan
1570   CT 2k0130
1571   non-recursively destroy nested objects
1572
1573   CT 2k0223
1574   everything is now done in a macro.
1575
1576   CT 2k0305
1577   modified to use functions, after Tim Peter's suggestion.
1578
1579   CT 2k0309
1580   modified to restore a possible error.
1581
1582   CT 2k0325
1583   added better safe than sorry check for threadstate
1584
1585   CT 2k0422
1586   complete rewrite. We now build a chain via ob_type
1587   and save the limited number of types in ob_refcnt.
1588   This is perfect since we don't need any memory.
1589   A patch for free-threading would need just a lock.
1590 */
1591
1592 #define Py_TRASHCAN_TUPLE       1
1593 #define Py_TRASHCAN_LIST        2
1594 #define Py_TRASHCAN_DICT        3
1595 #define Py_TRASHCAN_FRAME       4
1596 #define Py_TRASHCAN_TRACEBACK   5
1597 /* extend here if other objects want protection */
1598
1599 int _PyTrash_delete_nesting = 0;
1600
1601 PyObject * _PyTrash_delete_later = NULL;
1602
1603 void
1604 _PyTrash_deposit_object(PyObject *op)
1605 {
1606         int typecode;
1607
1608         if (PyTuple_Check(op))
1609                 typecode = Py_TRASHCAN_TUPLE;
1610         else if (PyList_Check(op))
1611                 typecode = Py_TRASHCAN_LIST;
1612         else if (PyDict_Check(op))
1613                 typecode = Py_TRASHCAN_DICT;
1614         else if (PyFrame_Check(op))
1615                 typecode = Py_TRASHCAN_FRAME;
1616         else if (PyTraceBack_Check(op))
1617                 typecode = Py_TRASHCAN_TRACEBACK;
1618         else /* We have a bug here -- those are the only types in GC */ {
1619                 Py_FatalError("Type not supported in GC -- internal bug");
1620                 return; /* pacify compiler -- execution never here */
1621         }
1622         op->ob_refcnt = typecode;
1623
1624         op->ob_type = (PyTypeObject*)_PyTrash_delete_later;
1625         _PyTrash_delete_later = op;
1626 }
1627
1628 void
1629 _PyTrash_destroy_chain(void)
1630 {
1631         while (_PyTrash_delete_later) {
1632                 PyObject *shredder = _PyTrash_delete_later;
1633                 _PyTrash_delete_later = (PyObject*) shredder->ob_type;
1634
1635                 switch (shredder->ob_refcnt) {
1636                 case Py_TRASHCAN_TUPLE:
1637                         shredder->ob_type = &PyTuple_Type;
1638                         break;
1639                 case Py_TRASHCAN_LIST:
1640                         shredder->ob_type = &PyList_Type;
1641                         break;
1642                 case Py_TRASHCAN_DICT:
1643                         shredder->ob_type = &PyDict_Type;
1644                         break;
1645                 case Py_TRASHCAN_FRAME:
1646                         shredder->ob_type = &PyFrame_Type;
1647                         break;
1648                 case Py_TRASHCAN_TRACEBACK:
1649                         shredder->ob_type = &PyTraceBack_Type;
1650                         break;
1651                 }
1652                 _Py_NewReference(shredder);
1653
1654                 ++_PyTrash_delete_nesting;
1655                 Py_DECREF(shredder);
1656                 --_PyTrash_delete_nesting;
1657         }
1658 }
1659
1660 #ifdef WITH_PYMALLOC
1661 #include "obmalloc.c"
1662 #endif