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         /* If the types are equal, don't bother with coercions etc. */
 481         if (v->ob_type == w->ob_type) {
 482                 if ((f = v->ob_type->tp_compare) == NULL)
 483                         return 2;
 484                 c = (*f)(v, w);
 485                 if (PyErr_Occurred())
 486                         return -2;
 487                 return c < 0 ? -1 : c > 0 ? 1 : 0;
 488         }
 489
 490         /* Try coercion; if it fails, give up */
 491         c = PyNumber_CoerceEx(&v, &w);
 492         if (c < 0)
 493                 return -2;
 494         if (c > 0)
 495                 return 2;
 496
 497         /* Try v's comparison, if defined */
 498         if ((f = v->ob_type->tp_compare) != NULL) {
 499                 c = (*f)(v, w);
 500                 Py_DECREF(v);
 501                 Py_DECREF(w);
 502                 if (PyErr_Occurred())
 503                         return -2;
 504                 return c < 0 ? -1 : c > 0 ? 1 : 0;
 505         }
 506
 507         /* Try w's comparison, if defined */
 508         if ((f = w->ob_type->tp_compare) != NULL) {
 509                 c = (*f)(w, v); /* swapped! */
 510                 Py_DECREF(v);
 511                 Py_DECREF(w);
 512                 if (PyErr_Occurred())
 513                         return -2;
 514                 return c < 0 ? 1 : c > 0 ? -1 : 0; /* negated! */
 515         }
 516
 517         /* No comparison defined */
 518         Py_DECREF(v);
 519         Py_DECREF(w);
 520         return 2;
 521 }
 522
 523 /* Final fallback 3-way comparison, returning an int.  Return:
 524    -2 if an error occurred;
 525    -1 if v < w;
 526    0 if v == w;
 527    1 if v > w.
 528 */
 529 static int
 530 default_3way_compare(PyObject *v, PyObject *w)
 531 {
 532         int c;
 533         char *vname, *wname;
 534
 535         if (v->ob_type == w->ob_type) {
 536                 /* When comparing these pointers, they must be cast to
 537                  * integer types (i.e. Py_uintptr_t, our spelling of C9X's
 538                  * uintptr_t).  ANSI specifies that pointer compares other
 539                  * than == and != to non-related structures are undefined.
 540                  */
 541                 Py_uintptr_t vv = (Py_uintptr_t)v;
 542                 Py_uintptr_t ww = (Py_uintptr_t)w;
 543                 return (vv < ww) ? -1 : (vv > ww) ? 1 : 0;
 544         }
 545
 546         /* Special case for Unicode */
 547         if (PyUnicode_Check(v) || PyUnicode_Check(w)) {
 548                 c = PyUnicode_Compare(v, w);
 549                 if (!PyErr_Occurred())
 550                         return c;
 551                 /* TypeErrors are ignored: if Unicode coercion fails due
 552                    to one of the arguments not having the right type, we
 553                    continue as defined by the coercion protocol (see
 554                    above).  Luckily, decoding errors are reported as
 555                    ValueErrors and are not masked by this technique. */
 556                 if (!PyErr_ExceptionMatches(PyExc_TypeError))
 557                         return -2;
 558                 PyErr_Clear();
 559         }
 560
 561         /* None is smaller than anything */
 562         if (v == Py_None)
 563                 return -1;
 564         if (w == Py_None)
 565                 return 1;
 566
 567         /* different type: compare type names */
 568         if (v->ob_type->tp_as_number)
 569                 vname = "";
 570         else
 571                 vname = v->ob_type->tp_name;
 572         if (w->ob_type->tp_as_number)
 573                 wname = "";
 574         else
 575                 wname = w->ob_type->tp_name;
 576         c = strcmp(vname, wname);
 577         if (c < 0)
 578                 return -1;
 579         if (c > 0)
 580                 return 1;
 581         /* Same type name, or (more likely) incomparable numeric types */
 582         return ((Py_uintptr_t)(v->ob_type) < (
 583                 Py_uintptr_t)(w->ob_type)) ? -1 : 1;
 584 }
 585
 586 #define CHECK_TYPES(o) PyType_HasFeature((o)->ob_type, Py_TPFLAGS_CHECKTYPES)
 587
 588 /* Do a 3-way comparison, by hook or by crook.  Return:
 589    -2 for an exception;
 590    -1 if v < w;
 591     0 if v == w;
 592     1 if v > w;
 593 */
 594 static int
 595 do_cmp(PyObject *v, PyObject *w)
 596 {
 597         int c;
 598
 599         c = try_rich_to_3way_compare(v, w);
 600         if (c < 2)
 601                 return c;
 602         c = try_3way_compare(v, w);
 603         if (c < 2)
 604                 return c;
 605         return default_3way_compare(v, w);
 606 }
 607
 608 /* compare_nesting is incremented before calling compare (for
 609    some types) and decremented on exit.  If the count exceeds the
 610    nesting limit, enable code to detect circular data structures.
 611
 612    This is a tunable parameter that should only affect the performance
 613    of comparisons, nothing else.  Setting it high makes comparing deeply
 614    nested non-cyclical data structures faster, but makes comparing cyclical
 615    data structures slower.
 616 */
 617 #define NESTING_LIMIT 20
 618
 619 static int compare_nesting = 0;
 620
 621 static PyObject*
 622 get_inprogress_dict(void)
 623 {
 624         static PyObject *key;
 625         PyObject *tstate_dict, *inprogress;
 626
 627         if (key == NULL) {
 628                 key = PyString_InternFromString("cmp_state");
 629                 if (key == NULL)
 630                         return NULL;
 631         }
 632
 633         tstate_dict = PyThreadState_GetDict();
 634         if (tstate_dict == NULL) {
 635                 PyErr_BadInternalCall();
 636                 return NULL;
 637         }
 638
 639         inprogress = PyDict_GetItem(tstate_dict, key);
 640         if (inprogress == NULL) {
 641                 inprogress = PyDict_New();
 642                 if (inprogress == NULL)
 643                         return NULL;
 644                 if (PyDict_SetItem(tstate_dict, key, inprogress) == -1) {
 645                     Py_DECREF(inprogress);
 646                     return NULL;
 647                 }
 648                 Py_DECREF(inprogress);
 649         }
 650
 651         return inprogress;
 652 }
 653
 654 static PyObject *
 655 check_recursion(PyObject *v, PyObject *w, int op)
 656 {
 657         PyObject *inprogress;
 658         PyObject *token;
 659         Py_uintptr_t iv = (Py_uintptr_t)v;
 660         Py_uintptr_t iw = (Py_uintptr_t)w;
 661         PyObject *x, *y, *z;
 662
 663         inprogress = get_inprogress_dict();
 664         if (inprogress == NULL)
 665                 return NULL;
 666
 667         token = PyTuple_New(3);
 668         if (token == NULL)
 669                 return NULL;
 670
 671         if (iv <= iw) {
 672                 PyTuple_SET_ITEM(token, 0, x = PyLong_FromVoidPtr((void *)v));
 673                 PyTuple_SET_ITEM(token, 1, y = PyLong_FromVoidPtr((void *)w));
 674                 if (op >= 0)
 675                         op = swapped_op[op];
 676         } else {
 677                 PyTuple_SET_ITEM(token, 0, x = PyLong_FromVoidPtr((void *)w));
 678                 PyTuple_SET_ITEM(token, 1, y = PyLong_FromVoidPtr((void *)v));
 679         }
 680         PyTuple_SET_ITEM(token, 2, z = PyInt_FromLong((long)op));
 681         if (x == NULL || y == NULL || z == NULL) {
 682                 Py_DECREF(token);
 683                 return NULL;
 684         }
 685
 686         if (PyDict_GetItem(inprogress, token) != NULL) {
 687                 Py_DECREF(token);
 688                 return Py_None; /* Without INCREF! */
 689         }
 690
 691         if (PyDict_SetItem(inprogress, token, token) < 0) {
 692                 Py_DECREF(token);
 693                 return NULL;
 694         }
 695
 696         return token;
 697 }
 698
 699 static void
 700 delete_token(PyObject *token)
 701 {
 702         PyObject *inprogress;
 703
 704         if (token == NULL || token == Py_None)
 705                 return;
 706         inprogress = get_inprogress_dict();
 707         if (inprogress == NULL)
 708                 PyErr_Clear();
 709         else
 710                 PyDict_DelItem(inprogress, token);
 711         Py_DECREF(token);
 712 }
 713
 714 int
 715 PyObject_Compare(PyObject *v, PyObject *w)
 716 {
 717         PyTypeObject *vtp;
 718         int result;
 719
 720 #if defined(USE_STACKCHECK)
 721         if (PyOS_CheckStack()) {
 722                 PyErr_SetString(PyExc_MemoryError, "Stack overflow");
 723         return -1;
 724         }
 725 #endif
 726         if (v == NULL || w == NULL) {
 727                 PyErr_BadInternalCall();
 728                 return -1;
 729         }
 730         if (v == w)
 731                 return 0;
 732         vtp = v->ob_type;
 733         compare_nesting++;
 734         if (compare_nesting > NESTING_LIMIT &&
 735                 (vtp->tp_as_mapping
 736                  || (vtp->tp_as_sequence
 737                      && !PyString_Check(v)
 738                      && !PyTuple_Check(v)))) {
 739                 /* try to detect circular data structures */
 740                 PyObject *token = check_recursion(v, w, -1);
 741
 742                 if (token == NULL) {
 743                         result = -1;
 744                 }
 745                 else if (token == Py_None) {
 746                         /* already comparing these objects.  assume
 747                            they're equal until shown otherwise */
 748                         result = 0;
 749                 }
 750                 else {
 751                         result = do_cmp(v, w);
 752                         delete_token(token);
 753                 }
 754         }
 755         else {
 756                 result = do_cmp(v, w);
 757         }
 758         compare_nesting--;
 759         return result < 0 ? -1 : result;
 760 }
 761
 762 static PyObject *
 763 try_3way_to_rich_compare(PyObject *v, PyObject *w, int op)
 764 {
 765         int c;
 766         PyObject *result;
 767
 768         c = try_3way_compare(v, w);
 769         if (c >= 2)
 770                 c = default_3way_compare(v, w);
 771         if (c <= -2)
 772                 return NULL;
 773         switch (op) {
 774         case Py_LT: c = c <  0; break;
 775         case Py_LE: c = c <= 0; break;
 776         case Py_EQ: c = c == 0; break;
 777         case Py_NE: c = c != 0; break;
 778         case Py_GT: c = c >  0; break;
 779         case Py_GE: c = c >= 0; break;
 780         }
 781         result = c ? Py_True : Py_False;
 782         Py_INCREF(result);
 783         return result;
 784 }
 785
 786 static PyObject *
 787 do_richcmp(PyObject *v, PyObject *w, int op)
 788 {
 789         PyObject *res;
 790
 791         res = try_rich_compare(v, w, op);
 792         if (res != Py_NotImplemented)
 793                 return res;
 794         Py_DECREF(res);
 795
 796         return try_3way_to_rich_compare(v, w, op);
 797 }
 798
 799 PyObject *
 800 PyObject_RichCompare(PyObject *v, PyObject *w, int op)
 801 {
 802         PyObject *res;
 803
 804         assert(Py_LT <= op && op <= Py_GE);
 805
 806         compare_nesting++;
 807         if (compare_nesting > NESTING_LIMIT &&
 808                 (v->ob_type->tp_as_mapping
 809                  || (v->ob_type->tp_as_sequence
 810                      && !PyString_Check(v)
 811                      && !PyTuple_Check(v)))) {
 812                 /* try to detect circular data structures */
 813                 PyObject *token = check_recursion(v, w, op);
 814
 815                 if (token == NULL) {
 816                         res = NULL;
 817                 }
 818                 else if (token == Py_None) {
 819                         /* already comparing these objects with this operator.
 820                            assume they're equal until shown otherwise */
 821                         if (op == Py_EQ)
 822                                 res = Py_True;
 823                         else if (op == Py_NE)
 824                                 res = Py_False;
 825                         else {
 826                                 PyErr_SetString(PyExc_ValueError,
 827                                         "can't order recursive values");
 828                                 res = NULL;
 829                         }
 830                         Py_XINCREF(res);
 831                 }
 832                 else {
 833                         res = do_richcmp(v, w, op);
 834                         delete_token(token);
 835                 }
 836         }
 837         else {
 838                 res = do_richcmp(v, w, op);
 839         }
 840         compare_nesting--;
 841         return res;
 842 }
 843
 844 int
 845 PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
 846 {
 847         PyObject *res = PyObject_RichCompare(v, w, op);
 848         int ok;
 849
 850         if (res == NULL)
 851                 return -1;
 852         ok = PyObject_IsTrue(res);
 853         Py_DECREF(res);
 854         return ok;
 855 }
 856
 857 /* Set of hash utility functions to help maintaining the invariant that
 858         iff a==b then hash(a)==hash(b)
 859
 860    All the utility functions (_Py_Hash*()) return "-1" to signify an error.
 861 */
 862
 863 long
 864 _Py_HashDouble(double v)
 865 {
 866         double intpart, fractpart;
 867         int expo;
 868         long hipart;
 869         long x;         /* the final hash value */
 870         /* This is designed so that Python numbers of different types
 871          * that compare equal hash to the same value; otherwise comparisons
 872          * of mapping keys will turn out weird.
 873          */
 874
 875 #ifdef MPW /* MPW C modf expects pointer to extended as second argument */
 876 {
 877         extended e;
 878         fractpart = modf(v, &e);
 879         intpart = e;
 880 }
 881 #else
 882         fractpart = modf(v, &intpart);
 883 #endif
 884         if (fractpart == 0.0) {
 885                 /* This must return the same hash as an equal int or long. */
 886                 if (intpart > LONG_MAX || -intpart > LONG_MAX) {
 887                         /* Convert to long and use its hash. */
 888                         PyObject *plong;        /* converted to Python long */
 889                         if (Py_IS_INFINITY(intpart))
 890                                 /* can't convert to long int -- arbitrary */
 891                                 v = v < 0 ? -271828.0 : 314159.0;
 892                         plong = PyLong_FromDouble(v);
 893                         if (plong == NULL)
 894                                 return -1;
 895                         x = PyObject_Hash(plong);
 896                         Py_DECREF(plong);
 897                         return x;
 898                 }
 899                 /* Fits in a C long == a Python int, so is its own hash. */
 900                 x = (long)intpart;
 901                 if (x == -1)
 902                         x = -2;
 903                 return x;
 904         }
 905         /* The fractional part is non-zero, so we don't have to worry about
 906          * making this match the hash of some other type.
 907          * Use frexp to get at the bits in the double.
 908          * Since the VAX D double format has 56 mantissa bits, which is the
 909          * most of any double format in use, each of these parts may have as
 910          * many as (but no more than) 56 significant bits.
 911          * So, assuming sizeof(long) >= 4, each part can be broken into two
 912          * longs; frexp and multiplication are used to do that.
 913          * Also, since the Cray double format has 15 exponent bits, which is
 914          * the most of any double format in use, shifting the exponent field
 915          * left by 15 won't overflow a long (again assuming sizeof(long) >= 4).
 916          */
 917         v = frexp(v, &expo);
 918         v *= 2147483648.0;      /* 2**31 */
 919         hipart = (long)v;       /* take the top 32 bits */
 920         v = (v - (double)hipart) * 2147483648.0; /* get the next 32 bits */
 921         x = hipart + (long)v + (expo << 15);
 922         if (x == -1)
 923                 x = -2;
 924         return x;
 925 }
 926
 927 long
 928 _Py_HashPointer(void *p)
 929 {
 930 #if SIZEOF_LONG >= SIZEOF_VOID_P
 931         return (long)p;
 932 #else
 933         /* convert to a Python long and hash that */
 934         PyObject* longobj;
 935         long x;
 936
 937         if ((longobj = PyLong_FromVoidPtr(p)) == NULL) {
 938                 x = -1;
 939                 goto finally;
 940         }
 941         x = PyObject_Hash(longobj);
 942
 943 finally:
 944         Py_XDECREF(longobj);
 945         return x;
 946 #endif
 947 }
 948
 949
 950 long
 951 PyObject_Hash(PyObject *v)
 952 {
 953         PyTypeObject *tp = v->ob_type;
 954         if (tp->tp_hash != NULL)
 955                 return (*tp->tp_hash)(v);
 956         if (tp->tp_compare == NULL && RICHCOMPARE(tp) == NULL) {
 957                 return _Py_HashPointer(v); /* Use address as hash value */
 958         }
 959         /* If there's a cmp but no hash defined, the object can't be hashed */
 960         PyErr_SetString(PyExc_TypeError, "unhashable type");
 961         return -1;
 962 }
 963
 964 PyObject *
 965 PyObject_GetAttrString(PyObject *v, char *name)
 966 {
 967         if (v->ob_type->tp_getattro != NULL) {
 968                 PyObject *w, *res;
 969                 w = PyString_InternFromString(name);
 970                 if (w == NULL)
 971                         return NULL;
 972                 res = (*v->ob_type->tp_getattro)(v, w);
 973                 Py_XDECREF(w);
 974                 return res;
 975         }
 976
 977         if (v->ob_type->tp_getattr == NULL) {
 978                 PyErr_Format(PyExc_AttributeError,
 979                              "'%.50s' object has no attribute '%.400s'",
 980                              v->ob_type->tp_name,
 981                              name);
 982                 return NULL;
 983         }
 984         else {
 985                 return (*v->ob_type->tp_getattr)(v, name);
 986         }
 987 }
 988
 989 int
 990 PyObject_HasAttrString(PyObject *v, char *name)
 991 {
 992         PyObject *res = PyObject_GetAttrString(v, name);
 993         if (res != NULL) {
 994                 Py_DECREF(res);
 995                 return 1;
 996         }
 997         PyErr_Clear();
 998         return 0;
 999 }
1000
1001 int
1002 PyObject_SetAttrString(PyObject *v, char *name, PyObject *w)
1003 {
1004         if (v->ob_type->tp_setattro != NULL) {
1005                 PyObject *s;
1006                 int res;
1007                 s = PyString_InternFromString(name);
1008                 if (s == NULL)
1009                         return -1;
1010                 res = (*v->ob_type->tp_setattro)(v, s, w);
1011                 Py_XDECREF(s);
1012                 return res;
1013         }
1014
1015         if (v->ob_type->tp_setattr == NULL) {
1016                 if (v->ob_type->tp_getattr == NULL)
1017                         PyErr_SetString(PyExc_TypeError,
1018                                    "attribute-less object (assign or del)");
1019                 else
1020                         PyErr_SetString(PyExc_TypeError,
1021                                    "object has read-only attributes");
1022                 return -1;
1023         }
1024         else {
1025                 return (*v->ob_type->tp_setattr)(v, name, w);
1026         }
1027 }
1028
1029 /* Internal API needed by PyObject_GetAttr(): */
1030 extern
1031 PyObject *_PyUnicode_AsDefaultEncodedString(PyObject *unicode,
1032                                   const char *errors);
1033
1034 PyObject *
1035 PyObject_GetAttr(PyObject *v, PyObject *name)
1036 {
1037         /* The Unicode to string conversion is done here because the
1038            existing tp_getattro slots expect a string object as name
1039            and we wouldn't want to break those. */
1040         if (PyUnicode_Check(name)) {
1041                 name = _PyUnicode_AsDefaultEncodedString(name, NULL);
1042                 if (name == NULL)
1043                         return NULL;
1044         }
1045
1046         if (!PyString_Check(name)) {
1047                 PyErr_SetString(PyExc_TypeError,
1048                                 "attribute name must be string");
1049                 return NULL;
1050         }
1051         if (v->ob_type->tp_getattro != NULL)
1052                 return (*v->ob_type->tp_getattro)(v, name);
1053         else
1054         return PyObject_GetAttrString(v, PyString_AS_STRING(name));
1055 }
1056
1057 int
1058 PyObject_HasAttr(PyObject *v, PyObject *name)
1059 {
1060         PyObject *res = PyObject_GetAttr(v, name);
1061         if (res != NULL) {
1062                 Py_DECREF(res);
1063                 return 1;
1064         }
1065         PyErr_Clear();
1066         return 0;
1067 }
1068
1069 int
1070 PyObject_SetAttr(PyObject *v, PyObject *name, PyObject *value)
1071 {
1072         int err;
1073
1074         /* The Unicode to string conversion is done here because the
1075            existing tp_setattro slots expect a string object as name
1076            and we wouldn't want to break those. */
1077         if (PyUnicode_Check(name)) {
1078                 name = PyUnicode_AsEncodedString(name, NULL, NULL);
1079                 if (name == NULL)
1080                         return -1;
1081         }
1082         else
1083                 Py_INCREF(name);
1084
1085         if (!PyString_Check(name)){
1086                 PyErr_SetString(PyExc_TypeError,
1087                                 "attribute name must be string");
1088                 err = -1;
1089         }
1090         else {
1091                 PyString_InternInPlace(&name);
1092                 if (v->ob_type->tp_setattro != NULL)
1093                         err = (*v->ob_type->tp_setattro)(v, name, value);
1094                 else
1095                         err = PyObject_SetAttrString(v,
1096                                         PyString_AS_STRING(name), value);
1097         }
1098
1099         Py_DECREF(name);
1100         return err;
1101 }
1102
1103 /* Test a value used as condition, e.g., in a for or if statement.
1104    Return -1 if an error occurred */
1105
1106 int
1107 PyObject_IsTrue(PyObject *v)
1108 {
1109         int res;
1110         if (v == Py_None)
1111                 res = 0;
1112         else if (v->ob_type->tp_as_number != NULL &&
1113                  v->ob_type->tp_as_number->nb_nonzero != NULL)
1114                 res = (*v->ob_type->tp_as_number->nb_nonzero)(v);
1115         else if (v->ob_type->tp_as_mapping != NULL &&
1116                  v->ob_type->tp_as_mapping->mp_length != NULL)
1117                 res = (*v->ob_type->tp_as_mapping->mp_length)(v);
1118         else if (v->ob_type->tp_as_sequence != NULL &&
1119                  v->ob_type->tp_as_sequence->sq_length != NULL)
1120                 res = (*v->ob_type->tp_as_sequence->sq_length)(v);
1121         else
1122                 res = 1;
1123         if (res > 0)
1124                 res = 1;
1125         return res;
1126 }
1127
1128 /* equivalent of 'not v'
1129    Return -1 if an error occurred */
1130
1131 int
1132 PyObject_Not(PyObject *v)
1133 {
1134         int res;
1135         res = PyObject_IsTrue(v);
1136         if (res < 0)
1137                 return res;
1138         return res == 0;
1139 }
1140
1141 /* Coerce two numeric types to the "larger" one.
1142    Increment the reference count on each argument.
1143    Return value:
1144    -1 if an error occurred;
1145    0 if the coercion succeeded (and then the reference counts are increased);
1146    1 if no coercion is possible (and no error is raised).
1147 */
1148 int
1149 PyNumber_CoerceEx(PyObject **pv, PyObject **pw)
1150 {
1151         register PyObject *v = *pv;
1152         register PyObject *w = *pw;
1153         int res;
1154
1155         if (v->ob_type == w->ob_type && !PyInstance_Check(v)) {
1156                 Py_INCREF(v);
1157                 Py_INCREF(w);
1158                 return 0;
1159         }
1160         if (v->ob_type->tp_as_number && v->ob_type->tp_as_number->nb_coerce) {
1161                 res = (*v->ob_type->tp_as_number->nb_coerce)(pv, pw);
1162                 if (res <= 0)
1163                         return res;
1164         }
1165         if (w->ob_type->tp_as_number && w->ob_type->tp_as_number->nb_coerce) {
1166                 res = (*w->ob_type->tp_as_number->nb_coerce)(pw, pv);
1167                 if (res <= 0)
1168                         return res;
1169         }
1170         return 1;
1171 }
1172
1173 /* Coerce two numeric types to the "larger" one.
1174    Increment the reference count on each argument.
1175    Return -1 and raise an exception if no coercion is possible
1176    (and then no reference count is incremented).
1177 */
1178 int
1179 PyNumber_Coerce(PyObject **pv, PyObject **pw)
1180 {
1181         int err = PyNumber_CoerceEx(pv, pw);
1182         if (err <= 0)
1183                 return err;
1184         PyErr_SetString(PyExc_TypeError, "number coercion failed");
1185         return -1;
1186 }
1187
1188
1189 /* Test whether an object can be called */
1190
1191 int
1192 PyCallable_Check(PyObject *x)
1193 {
1194         if (x == NULL)
1195                 return 0;
1196         if (x->ob_type->tp_call != NULL ||
1197             PyFunction_Check(x) ||
1198             PyMethod_Check(x) ||
1199             PyCFunction_Check(x) ||
1200             PyClass_Check(x))
1201                 return 1;
1202         if (PyInstance_Check(x)) {
1203                 PyObject *call = PyObject_GetAttrString(x, "__call__");
1204                 if (call == NULL) {
1205                         PyErr_Clear();
1206                         return 0;
1207                 }
1208                 /* Could test recursively but don't, for fear of endless
1209                    recursion if some joker sets self.__call__ = self */
1210                 Py_DECREF(call);
1211                 return 1;
1212         }
1213         return 0;
1214 }
1215
1216
1217 /*
1218 NoObject is usable as a non-NULL undefined value, used by the macro None.
1219 There is (and should be!) no way to create other objects of this type,
1220 so there is exactly one (which is indestructible, by the way).
1221 */
1222
1223 /* ARGSUSED */
1224 static PyObject *
1225 none_repr(PyObject *op)
1226 {
1227         return PyString_FromString("None");
1228 }
1229
1230 /* ARGUSED */
1231 static void
1232 none_dealloc(PyObject* ignore)
1233 {
1234         /* This should never get called, but we also don't want to SEGV if
1235          * we accidently decref None out of existance.
1236          */
1237         abort();
1238 }
1239
1240
1241 static PyTypeObject PyNothing_Type = {
1242         PyObject_HEAD_INIT(&PyType_Type)
1243         0,
1244         "None",
1245         0,
1246         0,
1247         (destructor)none_dealloc,            /*tp_dealloc*/ /*never called*/
1248         0,              /*tp_print*/
1249         0,              /*tp_getattr*/
1250         0,              /*tp_setattr*/
1251         0,              /*tp_compare*/
1252         (reprfunc)none_repr, /*tp_repr*/
1253         0,              /*tp_as_number*/
1254         0,              /*tp_as_sequence*/
1255         0,              /*tp_as_mapping*/
1256         0,              /*tp_hash */
1257 };
1258
1259 PyObject _Py_NoneStruct = {
1260         PyObject_HEAD_INIT(&PyNothing_Type)
1261 };
1262
1263 /* NotImplemented is an object that can be used to signal that an
1264    operation is not implemented for the given type combination. */
1265
1266 static PyObject *
1267 NotImplemented_repr(PyObject *op)
1268 {
1269         return PyString_FromString("NotImplemented");
1270 }
1271
1272 static PyTypeObject PyNotImplemented_Type = {
1273         PyObject_HEAD_INIT(&PyType_Type)
1274         0,
1275         "NotImplemented",
1276         0,
1277         0,
1278         (destructor)none_dealloc,            /*tp_dealloc*/ /*never called*/
1279         0,              /*tp_print*/
1280         0,              /*tp_getattr*/
1281         0,              /*tp_setattr*/
1282         0,              /*tp_compare*/
1283         (reprfunc)NotImplemented_repr, /*tp_repr*/
1284         0,              /*tp_as_number*/
1285         0,              /*tp_as_sequence*/
1286         0,              /*tp_as_mapping*/
1287         0,              /*tp_hash */
1288 };
1289
1290 PyObject _Py_NotImplementedStruct = {
1291         PyObject_HEAD_INIT(&PyNotImplemented_Type)
1292 };
1293
1294
1295 #ifdef Py_TRACE_REFS
1296
1297 static PyObject refchain = {&refchain, &refchain};
1298
1299 void
1300 _Py_ResetReferences(void)
1301 {
1302         refchain._ob_prev = refchain._ob_next = &refchain;
1303         _Py_RefTotal = 0;
1304 }
1305
1306 void
1307 _Py_NewReference(PyObject *op)
1308 {
1309         _Py_RefTotal++;
1310         op->ob_refcnt = 1;
1311         op->_ob_next = refchain._ob_next;
1312         op->_ob_prev = &refchain;
1313         refchain._ob_next->_ob_prev = op;
1314         refchain._ob_next = op;
1315 #ifdef COUNT_ALLOCS
1316         inc_count(op->ob_type);
1317 #endif
1318 }
1319
1320 void
1321 _Py_ForgetReference(register PyObject *op)
1322 {
1323 #ifdef SLOW_UNREF_CHECK
1324         register PyObject *p;
1325 #endif
1326         if (op->ob_refcnt < 0)
1327                 Py_FatalError("UNREF negative refcnt");
1328         if (op == &refchain ||
1329             op->_ob_prev->_ob_next != op || op->_ob_next->_ob_prev != op)
1330                 Py_FatalError("UNREF invalid object");
1331 #ifdef SLOW_UNREF_CHECK
1332         for (p = refchain._ob_next; p != &refchain; p = p->_ob_next) {
1333                 if (p == op)
1334                         break;
1335         }
1336         if (p == &refchain) /* Not found */
1337                 Py_FatalError("UNREF unknown object");
1338 #endif
1339         op->_ob_next->_ob_prev = op->_ob_prev;
1340         op->_ob_prev->_ob_next = op->_ob_next;
1341         op->_ob_next = op->_ob_prev = NULL;
1342 #ifdef COUNT_ALLOCS
1343         op->ob_type->tp_free++;
1344 #endif
1345 }
1346
1347 void
1348 _Py_Dealloc(PyObject *op)
1349 {
1350         destructor dealloc = op->ob_type->tp_dealloc;
1351         _Py_ForgetReference(op);
1352         (*dealloc)(op);
1353 }
1354
1355 void
1356 _Py_PrintReferences(FILE *fp)
1357 {
1358         PyObject *op;
1359         fprintf(fp, "Remaining objects:\n");
1360         for (op = refchain._ob_next; op != &refchain; op = op->_ob_next) {
1361                 fprintf(fp, "[%d] ", op->ob_refcnt);
1362                 if (PyObject_Print(op, fp, 0) != 0)
1363                         PyErr_Clear();
1364                 putc('\n', fp);
1365         }
1366 }
1367
1368 PyObject *
1369 _Py_GetObjects(PyObject *self, PyObject *args)
1370 {
1371         int i, n;
1372         PyObject *t = NULL;
1373         PyObject *res, *op;
1374
1375         if (!PyArg_ParseTuple(args, "i|O", &n, &t))
1376                 return NULL;
1377         op = refchain._ob_next;
1378         res = PyList_New(0);
1379         if (res == NULL)
1380                 return NULL;
1381         for (i = 0; (n == 0 || i < n) && op != &refchain; i++) {
1382                 while (op == self || op == args || op == res || op == t ||
1383                        t != NULL && op->ob_type != (PyTypeObject *) t) {
1384                         op = op->_ob_next;
1385                         if (op == &refchain)
1386                                 return res;
1387                 }
1388                 if (PyList_Append(res, op) < 0) {
1389                         Py_DECREF(res);
1390                         return NULL;
1391                 }
1392                 op = op->_ob_next;
1393         }
1394         return res;
1395 }
1396
1397 #endif
1398
1399
1400 /* Hack to force loading of cobject.o */
1401 PyTypeObject *_Py_cobject_hack = &PyCObject_Type;
1402
1403
1404 /* Hack to force loading of abstract.o */
1405 int (*_Py_abstract_hack)(PyObject *) = &PyObject_Size;
1406
1407
1408 /* Python's malloc wrappers (see pymem.h) */
1409
1410 void *
1411 PyMem_Malloc(size_t nbytes)
1412 {
1413 #if _PyMem_EXTRA > 0
1414         if (nbytes == 0)
1415                 nbytes = _PyMem_EXTRA;
1416 #endif
1417         return PyMem_MALLOC(nbytes);
1418 }
1419
1420 void *
1421 PyMem_Realloc(void *p, size_t nbytes)
1422 {
1423 #if _PyMem_EXTRA > 0
1424         if (nbytes == 0)
1425                 nbytes = _PyMem_EXTRA;
1426 #endif
1427         return PyMem_REALLOC(p, nbytes);
1428 }
1429
1430 void
1431 PyMem_Free(void *p)
1432 {
1433         PyMem_FREE(p);
1434 }
1435
1436
1437 /* Python's object malloc wrappers (see objimpl.h) */
1438
1439 void *
1440 PyObject_Malloc(size_t nbytes)
1441 {
1442         return PyObject_MALLOC(nbytes);
1443 }
1444
1445 void *
1446 PyObject_Realloc(void *p, size_t nbytes)
1447 {
1448         return PyObject_REALLOC(p, nbytes);
1449 }
1450
1451 void
1452 PyObject_Free(void *p)
1453 {
1454         PyObject_FREE(p);
1455 }
1456
1457
1458 /* Hook to clear up weak references only once the _weakref module is
1459    imported.  We use a dummy implementation to simplify the code at each
1460    call site instead of requiring a test for NULL.
1461 */
1462
1463 static void
1464 empty_clear_weak_refs(PyObject *o)
1465 {
1466     return;
1467 }
1468
1469 void (*PyObject_ClearWeakRefs)(PyObject *) = empty_clear_weak_refs;
1470
1471
1472
1473 /* These methods are used to control infinite recursion in repr, str, print,
1474    etc.  Container objects that may recursively contain themselves,
1475    e.g. builtin dictionaries and lists, should used Py_ReprEnter() and
1476    Py_ReprLeave() to avoid infinite recursion.
1477
1478    Py_ReprEnter() returns 0 the first time it is called for a particular
1479    object and 1 every time thereafter.  It returns -1 if an exception
1480    occurred.  Py_ReprLeave() has no return value.
1481
1482    See dictobject.c and listobject.c for examples of use.
1483 */
1484
1485 #define KEY "Py_Repr"
1486
1487 int
1488 Py_ReprEnter(PyObject *obj)
1489 {
1490         PyObject *dict;
1491         PyObject *list;
1492         int i;
1493
1494         dict = PyThreadState_GetDict();
1495         if (dict == NULL)
1496                 return -1;
1497         list = PyDict_GetItemString(dict, KEY);
1498         if (list == NULL) {
1499                 list = PyList_New(0);
1500                 if (list == NULL)
1501                         return -1;
1502                 if (PyDict_SetItemString(dict, KEY, list) < 0)
1503                         return -1;
1504                 Py_DECREF(list);
1505         }
1506         i = PyList_GET_SIZE(list);
1507         while (--i >= 0) {
1508                 if (PyList_GET_ITEM(list, i) == obj)
1509                         return 1;
1510         }
1511         PyList_Append(list, obj);
1512         return 0;
1513 }
1514
1515 void
1516 Py_ReprLeave(PyObject *obj)
1517 {
1518         PyObject *dict;
1519         PyObject *list;
1520         int i;
1521
1522         dict = PyThreadState_GetDict();
1523         if (dict == NULL)
1524                 return;
1525         list = PyDict_GetItemString(dict, KEY);
1526         if (list == NULL || !PyList_Check(list))
1527                 return;
1528         i = PyList_GET_SIZE(list);
1529         /* Count backwards because we always expect obj to be list[-1] */
1530         while (--i >= 0) {
1531                 if (PyList_GET_ITEM(list, i) == obj) {
1532                         PyList_SetSlice(list, i, i + 1, NULL);
1533                         break;
1534                 }
1535         }
1536 }
1537
1538 /*
1539   trashcan
1540   CT 2k0130
1541   non-recursively destroy nested objects
1542
1543   CT 2k0223
1544   everything is now done in a macro.
1545
1546   CT 2k0305
1547   modified to use functions, after Tim Peter's suggestion.
1548
1549   CT 2k0309
1550   modified to restore a possible error.
1551
1552   CT 2k0325
1553   added better safe than sorry check for threadstate
1554
1555   CT 2k0422
1556   complete rewrite. We now build a chain via ob_type
1557   and save the limited number of types in ob_refcnt.
1558   This is perfect since we don't need any memory.
1559   A patch for free-threading would need just a lock.
1560 */
1561
1562 #define Py_TRASHCAN_TUPLE       1
1563 #define Py_TRASHCAN_LIST        2
1564 #define Py_TRASHCAN_DICT        3
1565 #define Py_TRASHCAN_FRAME       4
1566 #define Py_TRASHCAN_TRACEBACK   5
1567 /* extend here if other objects want protection */
1568
1569 int _PyTrash_delete_nesting = 0;
1570
1571 PyObject * _PyTrash_delete_later = NULL;
1572
1573 void
1574 _PyTrash_deposit_object(PyObject *op)
1575 {
1576         int typecode;
1577
1578         if (PyTuple_Check(op))
1579                 typecode = Py_TRASHCAN_TUPLE;
1580         else if (PyList_Check(op))
1581                 typecode = Py_TRASHCAN_LIST;
1582         else if (PyDict_Check(op))
1583                 typecode = Py_TRASHCAN_DICT;
1584         else if (PyFrame_Check(op))
1585                 typecode = Py_TRASHCAN_FRAME;
1586         else if (PyTraceBack_Check(op))
1587                 typecode = Py_TRASHCAN_TRACEBACK;
1588         else /* We have a bug here -- those are the only types in GC */ {
1589                 Py_FatalError("Type not supported in GC -- internal bug");
1590                 return; /* pacify compiler -- execution never here */
1591         }
1592         op->ob_refcnt = typecode;
1593
1594         op->ob_type = (PyTypeObject*)_PyTrash_delete_later;
1595         _PyTrash_delete_later = op;
1596 }
1597
1598 void
1599 _PyTrash_destroy_chain(void)
1600 {
1601         while (_PyTrash_delete_later) {
1602                 PyObject *shredder = _PyTrash_delete_later;
1603                 _PyTrash_delete_later = (PyObject*) shredder->ob_type;
1604
1605                 switch (shredder->ob_refcnt) {
1606                 case Py_TRASHCAN_TUPLE:
1607                         shredder->ob_type = &PyTuple_Type;
1608                         break;
1609                 case Py_TRASHCAN_LIST:
1610                         shredder->ob_type = &PyList_Type;
1611                         break;
1612                 case Py_TRASHCAN_DICT:
1613                         shredder->ob_type = &PyDict_Type;
1614                         break;
1615                 case Py_TRASHCAN_FRAME:
1616                         shredder->ob_type = &PyFrame_Type;
1617                         break;
1618                 case Py_TRASHCAN_TRACEBACK:
1619                         shredder->ob_type = &PyTraceBack_Type;
1620                         break;
1621                 }
1622                 _Py_NewReference(shredder);
1623
1624                 ++_PyTrash_delete_nesting;
1625                 Py_DECREF(shredder);
1626                 --_PyTrash_delete_nesting;
1627         }
1628 }
1629
1630 #ifdef WITH_PYMALLOC
1631 #include "obmalloc.c"
1632 #endif