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                         if (op->ob_type->tp_repr == NULL) {
 192                                 fprintf(fp, "<%s object at %p>",
 193                                         op->ob_type->tp_name, op);
 194                         }
 195                         else {
 196                                 PyObject *s;
 197                                 if (flags & Py_PRINT_RAW)
 198                                         s = PyObject_Str(op);
 199                                 else
 200                                         s = PyObject_Repr(op);
 201                                 if (s == NULL)
 202                                         ret = -1;
 203                                 else {
 204                                         ret = PyObject_Print(s, fp,
 205                                                              Py_PRINT_RAW);
 206                                 }
 207                                 Py_XDECREF(s);
 208                         }
 209                 }
 210                 else
 211                         ret = (*op->ob_type->tp_print)(op, fp, flags);
 212         }
 213         if (ret == 0) {
 214                 if (ferror(fp)) {
 215                         PyErr_SetFromErrno(PyExc_IOError);
 216                         clearerr(fp);
 217                         ret = -1;
 218                 }
 219         }
 220         return ret;
 221 }
 222
 223 PyObject *
 224 PyObject_Repr(PyObject *v)
 225 {
 226         if (PyErr_CheckSignals())
 227                 return NULL;
 228 #ifdef USE_STACKCHECK
 229         if (PyOS_CheckStack()) {
 230                 PyErr_SetString(PyExc_MemoryError, "Stack overflow");
 231                 return NULL;
 232         }
 233 #endif
 234         if (v == NULL)
 235                 return PyString_FromString("<NULL>");
 236         else if (v->ob_type->tp_repr == NULL) {
 237                 char buf[120];
 238                 sprintf(buf, "<%.80s object at %p>",
 239                         v->ob_type->tp_name, v);
 240                 return PyString_FromString(buf);
 241         }
 242         else {
 243                 PyObject *res;
 244                 res = (*v->ob_type->tp_repr)(v);
 245                 if (res == NULL)
 246                         return NULL;
 247                 if (PyUnicode_Check(res)) {
 248                         PyObject* str;
 249                         str = PyUnicode_AsUnicodeEscapeString(res);
 250                         Py_DECREF(res);
 251                         if (str)
 252                                 res = str;
 253                         else
 254                                 return NULL;
 255                 }
 256                 if (!PyString_Check(res)) {
 257                         PyErr_Format(PyExc_TypeError,
 258                                      "__repr__ returned non-string (type %.200s)",
 259                                      res->ob_type->tp_name);
 260                         Py_DECREF(res);
 261                         return NULL;
 262                 }
 263                 return res;
 264         }
 265 }
 266
 267 PyObject *
 268 PyObject_Str(PyObject *v)
 269 {
 270         PyObject *res;
 271
 272         if (v == NULL)
 273                 return PyString_FromString("<NULL>");
 274         else if (PyString_Check(v)) {
 275                 Py_INCREF(v);
 276                 return v;
 277         }
 278         else if (v->ob_type->tp_str != NULL)
 279                 res = (*v->ob_type->tp_str)(v);
 280         else {
 281                 PyObject *func;
 282                 if (!PyInstance_Check(v) ||
 283                     (func = PyObject_GetAttrString(v, "__str__")) == NULL) {
 284                         PyErr_Clear();
 285                         return PyObject_Repr(v);
 286                 }
 287                 res = PyEval_CallObject(func, (PyObject *)NULL);
 288                 Py_DECREF(func);
 289         }
 290         if (res == NULL)
 291                 return NULL;
 292         if (PyUnicode_Check(res)) {
 293                 PyObject* str;
 294                 str = PyUnicode_AsEncodedString(res, NULL, NULL);
 295                 Py_DECREF(res);
 296                 if (str)
 297                         res = str;
 298                 else
 299                         return NULL;
 300         }
 301         if (!PyString_Check(res)) {
 302                 PyErr_Format(PyExc_TypeError,
 303                              "__str__ returned non-string (type %.200s)",
 304                              res->ob_type->tp_name);
 305                 Py_DECREF(res);
 306                 return NULL;
 307         }
 308         return res;
 309 }
 310
 311 static PyObject *
 312 do_cmp(PyObject *v, PyObject *w)
 313 {
 314         long c;
 315         /* __rcmp__ actually won't be called unless __cmp__ isn't defined,
 316            because the check in cmpobject() reverses the objects first.
 317            This is intentional -- it makes no sense to define cmp(x,y)
 318            different than -cmp(y,x). */
 319         if (PyInstance_Check(v) || PyInstance_Check(w))
 320                 return PyInstance_DoBinOp(v, w, "__cmp__", "__rcmp__", do_cmp);
 321         c = PyObject_Compare(v, w);
 322         if (c && PyErr_Occurred())
 323                 return NULL;
 324         return PyInt_FromLong(c);
 325 }
 326
 327 PyObject *_PyCompareState_Key;
 328
 329 /* _PyCompareState_nesting is incremented before calling compare (for
 330    some types) and decremented on exit.  If the count exceeds the
 331    nesting limit, enable code to detect circular data structures.
 332 */
 333 #ifdef macintosh
 334 #define NESTING_LIMIT 60
 335 #else
 336 #define NESTING_LIMIT 500
 337 #endif
 338 int _PyCompareState_nesting = 0;
 339
 340 static PyObject*
 341 get_inprogress_dict(void)
 342 {
 343         PyObject *tstate_dict, *inprogress;
 344
 345         tstate_dict = PyThreadState_GetDict();
 346         if (tstate_dict == NULL) {
 347                 PyErr_BadInternalCall();
 348                 return NULL;
 349         }
 350         inprogress = PyDict_GetItem(tstate_dict, _PyCompareState_Key);
 351         if (inprogress == NULL) {
 352                 inprogress = PyDict_New();
 353                 if (inprogress == NULL)
 354                         return NULL;
 355                 if (PyDict_SetItem(tstate_dict, _PyCompareState_Key,
 356                                    inprogress) == -1) {
 357                     Py_DECREF(inprogress);
 358                     return NULL;
 359                 }
 360                 Py_DECREF(inprogress);
 361         }
 362         return inprogress;
 363 }
 364
 365 static PyObject *
 366 make_pair(PyObject *v, PyObject *w)
 367 {
 368         PyObject *pair;
 369         Py_uintptr_t iv = (Py_uintptr_t)v;
 370         Py_uintptr_t iw = (Py_uintptr_t)w;
 371
 372         pair = PyTuple_New(2);
 373         if (pair == NULL) {
 374                 return NULL;
 375         }
 376         if (iv <= iw) {
 377                 PyTuple_SET_ITEM(pair, 0, PyLong_FromVoidPtr((void *)v));
 378                 PyTuple_SET_ITEM(pair, 1, PyLong_FromVoidPtr((void *)w));
 379         } else {
 380                 PyTuple_SET_ITEM(pair, 0, PyLong_FromVoidPtr((void *)w));
 381                 PyTuple_SET_ITEM(pair, 1, PyLong_FromVoidPtr((void *)v));
 382         }
 383         return pair;
 384 }
 385
 386 int
 387 PyObject_Compare(PyObject *v, PyObject *w)
 388 {
 389         PyTypeObject *vtp, *wtp;
 390         int result;
 391
 392 #if defined(USE_STACKCHECK)
 393         if (PyOS_CheckStack()) {
 394                 PyErr_SetString(PyExc_MemoryError, "Stack overflow");
 395         return -1;
 396         }
 397 #endif
 398         if (v == NULL || w == NULL) {
 399                 PyErr_BadInternalCall();
 400                 return -1;
 401         }
 402         if (v == w)
 403                 return 0;
 404         if (PyInstance_Check(v) || PyInstance_Check(w)) {
 405                 PyObject *res;
 406                 int c;
 407                 if (!PyInstance_Check(v))
 408                         return -PyObject_Compare(w, v);
 409                 _PyCompareState_nesting++;
 410                 if (_PyCompareState_nesting > NESTING_LIMIT) {
 411                         PyObject *inprogress, *pair;
 412
 413                         inprogress = get_inprogress_dict();
 414                         if (inprogress == NULL) {
 415                                 _PyCompareState_nesting--;
 416                                 return -1;
 417                         }
 418                         pair = make_pair(v, w);
 419                         if (PyDict_GetItem(inprogress, pair)) {
 420                                 /* already comparing these objects.  assume
 421                                    they're equal until shown otherwise */
 422                                 Py_DECREF(pair);
 423                                 _PyCompareState_nesting--;
 424                                 return 0;
 425                         }
 426                         if (PyDict_SetItem(inprogress, pair, pair) == -1) {
 427                                 _PyCompareState_nesting--;
 428                                 return -1;
 429                         }
 430                         res = do_cmp(v, w);
 431                         /* XXX DelItem shouldn't fail */
 432                         PyDict_DelItem(inprogress, pair);
 433                         Py_DECREF(pair);
 434                 } else {
 435                         res = do_cmp(v, w);
 436                 }
 437                 _PyCompareState_nesting--;
 438                 if (res == NULL)
 439                         return -1;
 440                 if (!PyInt_Check(res)) {
 441                         Py_DECREF(res);
 442                         PyErr_SetString(PyExc_TypeError,
 443                                         "comparison did not return an int");
 444                         return -1;
 445                 }
 446                 c = PyInt_AsLong(res);
 447                 Py_DECREF(res);
 448                 return (c < 0) ? -1 : (c > 0) ? 1 : 0;
 449         }
 450         if ((vtp = v->ob_type) != (wtp = w->ob_type)) {
 451                 char *vname = vtp->tp_name;
 452                 char *wname = wtp->tp_name;
 453                 if (vtp->tp_as_number != NULL && wtp->tp_as_number != NULL) {
 454                         int err;
 455                         err = PyNumber_CoerceEx(&v, &w);
 456                         if (err < 0)
 457                                 return -1;
 458                         else if (err == 0) {
 459                                 int cmp;
 460                                 vtp = v->ob_type;
 461                                 if (vtp->tp_compare == NULL)
 462                                         cmp = (v < w) ? -1 : 1;
 463                                 else
 464                                         cmp = (*vtp->tp_compare)(v, w);
 465                                 Py_DECREF(v);
 466                                 Py_DECREF(w);
 467                                 return cmp;
 468                         }
 469                 }
 470                 else if (PyUnicode_Check(v) || PyUnicode_Check(w)) {
 471                         int result = PyUnicode_Compare(v, w);
 472                         if (result == -1 && PyErr_Occurred() &&
 473                             PyErr_ExceptionMatches(PyExc_TypeError))
 474                                 /* TypeErrors are ignored: if Unicode coercion
 475                                 fails due to one of the arguments not
 476                                 having the right type, we continue as
 477                                 defined by the coercion protocol (see
 478                                 above). Luckily, decoding errors are
 479                                 reported as ValueErrors and are not masked
 480                                 by this technique. */
 481                                 PyErr_Clear();
 482                         else
 483                                 return result;
 484                 }
 485                 else if (vtp->tp_as_number != NULL)
 486                         vname = "";
 487                 else if (wtp->tp_as_number != NULL)
 488                         wname = "";
 489                 /* Numerical types compare smaller than all other types */
 490                 return strcmp(vname, wname);
 491         }
 492         if (vtp->tp_compare == NULL) {
 493                 Py_uintptr_t iv = (Py_uintptr_t)v;
 494                 Py_uintptr_t iw = (Py_uintptr_t)w;
 495                 return (iv < iw) ? -1 : 1;
 496         }
 497         _PyCompareState_nesting++;
 498         if (_PyCompareState_nesting > NESTING_LIMIT
 499             && (vtp->tp_as_mapping
 500                 || (vtp->tp_as_sequence && !PyString_Check(v)))) {
 501                 PyObject *inprogress, *pair;
 502
 503                 inprogress = get_inprogress_dict();
 504                 if (inprogress == NULL) {
 505                         _PyCompareState_nesting--;
 506                         return -1;
 507                 }
 508                 pair = make_pair(v, w);
 509                 if (PyDict_GetItem(inprogress, pair)) {
 510                         /* already comparing these objects.  assume
 511                            they're equal until shown otherwise */
 512                         Py_DECREF(pair);
 513                         _PyCompareState_nesting--;
 514                         return 0;
 515                 }
 516                 if (PyDict_SetItem(inprogress, pair, pair) == -1) {
 517                         _PyCompareState_nesting--;
 518                         return -1;
 519                 }
 520                 result = (*vtp->tp_compare)(v, w);
 521                 PyDict_DelItem(inprogress, pair); /* XXX shouldn't fail */
 522                 Py_DECREF(pair);
 523         } else {
 524                 result = (*vtp->tp_compare)(v, w);
 525         }
 526         _PyCompareState_nesting--;
 527         return result;
 528 }
 529
 530
 531 /* Set of hash utility functions to help maintaining the invariant that
 532         iff a==b then hash(a)==hash(b)
 533
 534    All the utility functions (_Py_Hash*()) return "-1" to signify an error.
 535 */
 536
 537 long
 538 _Py_HashDouble(double v)
 539 {
 540         double intpart, fractpart;
 541         int expo;
 542         long hipart;
 543         long x;         /* the final hash value */
 544         /* This is designed so that Python numbers of different types
 545          * that compare equal hash to the same value; otherwise comparisons
 546          * of mapping keys will turn out weird.
 547          */
 548
 549 #ifdef MPW /* MPW C modf expects pointer to extended as second argument */
 550 {
 551         extended e;
 552         fractpart = modf(v, &e);
 553         intpart = e;
 554 }
 555 #else
 556         fractpart = modf(v, &intpart);
 557 #endif
 558         if (fractpart == 0.0) {
 559                 /* This must return the same hash as an equal int or long. */
 560                 if (intpart > LONG_MAX || -intpart > LONG_MAX) {
 561                         /* Convert to long and use its hash. */
 562                         PyObject *plong;        /* converted to Python long */
 563                         if (Py_IS_INFINITY(intpart))
 564                                 /* can't convert to long int -- arbitrary */
 565                                 v = v < 0 ? -271828.0 : 314159.0;
 566                         plong = PyLong_FromDouble(v);
 567                         if (plong == NULL)
 568                                 return -1;
 569                         x = PyObject_Hash(plong);
 570                         Py_DECREF(plong);
 571                         return x;
 572                 }
 573                 /* Fits in a C long == a Python int, so is its own hash. */
 574                 x = (long)intpart;
 575                 if (x == -1)
 576                         x = -2;
 577                 return x;
 578         }
 579         /* The fractional part is non-zero, so we don't have to worry about
 580          * making this match the hash of some other type.
 581          * Use frexp to get at the bits in the double.
 582          * Since the VAX D double format has 56 mantissa bits, which is the
 583          * most of any double format in use, each of these parts may have as
 584          * many as (but no more than) 56 significant bits.
 585          * So, assuming sizeof(long) >= 4, each part can be broken into two
 586          * longs; frexp and multiplication are used to do that.
 587          * Also, since the Cray double format has 15 exponent bits, which is
 588          * the most of any double format in use, shifting the exponent field
 589          * left by 15 won't overflow a long (again assuming sizeof(long) >= 4).
 590          */
 591         v = frexp(v, &expo);
 592         v *= 2147483648.0;      /* 2**31 */
 593         hipart = (long)v;       /* take the top 32 bits */
 594         v = (v - (double)hipart) * 2147483648.0; /* get the next 32 bits */
 595         x = hipart + (long)v + (expo << 15);
 596         if (x == -1)
 597                 x = -2;
 598         return x;
 599 }
 600
 601 long
 602 _Py_HashPointer(void *p)
 603 {
 604 #if SIZEOF_LONG >= SIZEOF_VOID_P
 605         return (long)p;
 606 #else
 607         /* convert to a Python long and hash that */
 608         PyObject* longobj;
 609         long x;
 610
 611         if ((longobj = PyLong_FromVoidPtr(p)) == NULL) {
 612                 x = -1;
 613                 goto finally;
 614         }
 615         x = PyObject_Hash(longobj);
 616
 617 finally:
 618         Py_XDECREF(longobj);
 619         return x;
 620 #endif
 621 }
 622
 623
 624 long
 625 PyObject_Hash(PyObject *v)
 626 {
 627         PyTypeObject *tp = v->ob_type;
 628         if (tp->tp_hash != NULL)
 629                 return (*tp->tp_hash)(v);
 630         if (tp->tp_compare == NULL) {
 631                 return _Py_HashPointer(v); /* Use address as hash value */
 632         }
 633         /* If there's a cmp but no hash defined, the object can't be hashed */
 634         PyErr_SetString(PyExc_TypeError, "unhashable type");
 635         return -1;
 636 }
 637
 638 PyObject *
 639 PyObject_GetAttrString(PyObject *v, char *name)
 640 {
 641         if (v->ob_type->tp_getattro != NULL) {
 642                 PyObject *w, *res;
 643                 w = PyString_InternFromString(name);
 644                 if (w == NULL)
 645                         return NULL;
 646                 res = (*v->ob_type->tp_getattro)(v, w);
 647                 Py_XDECREF(w);
 648                 return res;
 649         }
 650
 651         if (v->ob_type->tp_getattr == NULL) {
 652                 PyErr_Format(PyExc_AttributeError,
 653                              "'%.50s' object has no attribute '%.400s'",
 654                              v->ob_type->tp_name,
 655                              name);
 656                 return NULL;
 657         }
 658         else {
 659                 return (*v->ob_type->tp_getattr)(v, name);
 660         }
 661 }
 662
 663 int
 664 PyObject_HasAttrString(PyObject *v, char *name)
 665 {
 666         PyObject *res = PyObject_GetAttrString(v, name);
 667         if (res != NULL) {
 668                 Py_DECREF(res);
 669                 return 1;
 670         }
 671         PyErr_Clear();
 672         return 0;
 673 }
 674
 675 int
 676 PyObject_SetAttrString(PyObject *v, char *name, PyObject *w)
 677 {
 678         if (v->ob_type->tp_setattro != NULL) {
 679                 PyObject *s;
 680                 int res;
 681                 s = PyString_InternFromString(name);
 682                 if (s == NULL)
 683                         return -1;
 684                 res = (*v->ob_type->tp_setattro)(v, s, w);
 685                 Py_XDECREF(s);
 686                 return res;
 687         }
 688
 689         if (v->ob_type->tp_setattr == NULL) {
 690                 if (v->ob_type->tp_getattr == NULL)
 691                         PyErr_SetString(PyExc_TypeError,
 692                                    "attribute-less object (assign or del)");
 693                 else
 694                         PyErr_SetString(PyExc_TypeError,
 695                                    "object has read-only attributes");
 696                 return -1;
 697         }
 698         else {
 699                 return (*v->ob_type->tp_setattr)(v, name, w);
 700         }
 701 }
 702
 703 /* Internal API needed by PyObject_GetAttr(): */
 704 extern
 705 PyObject *_PyUnicode_AsDefaultEncodedString(PyObject *unicode,
 706                                   const char *errors);
 707
 708 PyObject *
 709 PyObject_GetAttr(PyObject *v, PyObject *name)
 710 {
 711         /* The Unicode to string conversion is done here because the
 712            existing tp_getattro slots expect a string object as name
 713            and we wouldn't want to break those. */
 714         if (PyUnicode_Check(name)) {
 715                 name = _PyUnicode_AsDefaultEncodedString(name, NULL);
 716                 if (name == NULL)
 717                         return NULL;
 718         }
 719
 720         if (!PyString_Check(name)) {
 721                 PyErr_SetString(PyExc_TypeError,
 722                                 "attribute name must be string");
 723                 return NULL;
 724         }
 725         if (v->ob_type->tp_getattro != NULL)
 726                 return (*v->ob_type->tp_getattro)(v, name);
 727         else
 728         return PyObject_GetAttrString(v, PyString_AS_STRING(name));
 729 }
 730
 731 int
 732 PyObject_HasAttr(PyObject *v, PyObject *name)
 733 {
 734         PyObject *res = PyObject_GetAttr(v, name);
 735         if (res != NULL) {
 736                 Py_DECREF(res);
 737                 return 1;
 738         }
 739         PyErr_Clear();
 740         return 0;
 741 }
 742
 743 int
 744 PyObject_SetAttr(PyObject *v, PyObject *name, PyObject *value)
 745 {
 746         int err;
 747
 748         /* The Unicode to string conversion is done here because the
 749            existing tp_setattro slots expect a string object as name
 750            and we wouldn't want to break those. */
 751         if (PyUnicode_Check(name)) {
 752                 name = PyUnicode_AsEncodedString(name, NULL, NULL);
 753                 if (name == NULL)
 754                         return -1;
 755         }
 756         else
 757                 Py_INCREF(name);
 758
 759         if (!PyString_Check(name)){
 760                 PyErr_SetString(PyExc_TypeError,
 761                                 "attribute name must be string");
 762                 err = -1;
 763         }
 764         else {
 765                 PyString_InternInPlace(&name);
 766                 if (v->ob_type->tp_setattro != NULL)
 767                         err = (*v->ob_type->tp_setattro)(v, name, value);
 768                 else
 769                         err = PyObject_SetAttrString(v,
 770                                         PyString_AS_STRING(name), value);
 771         }
 772
 773         Py_DECREF(name);
 774         return err;
 775 }
 776
 777 /* Test a value used as condition, e.g., in a for or if statement.
 778    Return -1 if an error occurred */
 779
 780 int
 781 PyObject_IsTrue(PyObject *v)
 782 {
 783         int res;
 784         if (v == Py_None)
 785                 res = 0;
 786         else if (v->ob_type->tp_as_number != NULL &&
 787                  v->ob_type->tp_as_number->nb_nonzero != NULL)
 788                 res = (*v->ob_type->tp_as_number->nb_nonzero)(v);
 789         else if (v->ob_type->tp_as_mapping != NULL &&
 790                  v->ob_type->tp_as_mapping->mp_length != NULL)
 791                 res = (*v->ob_type->tp_as_mapping->mp_length)(v);
 792         else if (v->ob_type->tp_as_sequence != NULL &&
 793                  v->ob_type->tp_as_sequence->sq_length != NULL)
 794                 res = (*v->ob_type->tp_as_sequence->sq_length)(v);
 795         else
 796                 res = 1;
 797         if (res > 0)
 798                 res = 1;
 799         return res;
 800 }
 801
 802 /* equivalent of 'not v'
 803    Return -1 if an error occurred */
 804
 805 int
 806 PyObject_Not(PyObject *v)
 807 {
 808         int res;
 809         res = PyObject_IsTrue(v);
 810         if (res < 0)
 811                 return res;
 812         return res == 0;
 813 }
 814
 815 /* Coerce two numeric types to the "larger" one.
 816    Increment the reference count on each argument.
 817    Return -1 and raise an exception if no coercion is possible
 818    (and then no reference count is incremented).
 819 */
 820
 821 int
 822 PyNumber_CoerceEx(PyObject **pv, PyObject **pw)
 823 {
 824         register PyObject *v = *pv;
 825         register PyObject *w = *pw;
 826         int res;
 827
 828         if (v->ob_type == w->ob_type && !PyInstance_Check(v)) {
 829                 Py_INCREF(v);
 830                 Py_INCREF(w);
 831                 return 0;
 832         }
 833         if (v->ob_type->tp_as_number && v->ob_type->tp_as_number->nb_coerce) {
 834                 res = (*v->ob_type->tp_as_number->nb_coerce)(pv, pw);
 835                 if (res <= 0)
 836                         return res;
 837         }
 838         if (w->ob_type->tp_as_number && w->ob_type->tp_as_number->nb_coerce) {
 839                 res = (*w->ob_type->tp_as_number->nb_coerce)(pw, pv);
 840                 if (res <= 0)
 841                         return res;
 842         }
 843         return 1;
 844 }
 845
 846 int
 847 PyNumber_Coerce(PyObject **pv, PyObject **pw)
 848 {
 849         int err = PyNumber_CoerceEx(pv, pw);
 850         if (err <= 0)
 851                 return err;
 852         PyErr_SetString(PyExc_TypeError, "number coercion failed");
 853         return -1;
 854 }
 855
 856
 857 /* Test whether an object can be called */
 858
 859 int
 860 PyCallable_Check(PyObject *x)
 861 {
 862         if (x == NULL)
 863                 return 0;
 864         if (x->ob_type->tp_call != NULL ||
 865             PyFunction_Check(x) ||
 866             PyMethod_Check(x) ||
 867             PyCFunction_Check(x) ||
 868             PyClass_Check(x))
 869                 return 1;
 870         if (PyInstance_Check(x)) {
 871                 PyObject *call = PyObject_GetAttrString(x, "__call__");
 872                 if (call == NULL) {
 873                         PyErr_Clear();
 874                         return 0;
 875                 }
 876                 /* Could test recursively but don't, for fear of endless
 877                    recursion if some joker sets self.__call__ = self */
 878                 Py_DECREF(call);
 879                 return 1;
 880         }
 881         return 0;
 882 }
 883
 884
 885 /*
 886 NoObject is usable as a non-NULL undefined value, used by the macro None.
 887 There is (and should be!) no way to create other objects of this type,
 888 so there is exactly one (which is indestructible, by the way).
 889 */
 890
 891 /* ARGSUSED */
 892 static PyObject *
 893 none_repr(PyObject *op)
 894 {
 895         return PyString_FromString("None");
 896 }
 897
 898 static PyTypeObject PyNothing_Type = {
 899         PyObject_HEAD_INIT(&PyType_Type)
 900         0,
 901         "None",
 902         0,
 903         0,
 904         0,              /*tp_dealloc*/ /*never called*/
 905         0,              /*tp_print*/
 906         0,              /*tp_getattr*/
 907         0,              /*tp_setattr*/
 908         0,              /*tp_compare*/
 909         (reprfunc)none_repr, /*tp_repr*/
 910         0,              /*tp_as_number*/
 911         0,              /*tp_as_sequence*/
 912         0,              /*tp_as_mapping*/
 913         0,              /*tp_hash */
 914 };
 915
 916 PyObject _Py_NoneStruct = {
 917         PyObject_HEAD_INIT(&PyNothing_Type)
 918 };
 919
 920
 921 #ifdef Py_TRACE_REFS
 922
 923 static PyObject refchain = {&refchain, &refchain};
 924
 925 void
 926 _Py_ResetReferences(void)
 927 {
 928         refchain._ob_prev = refchain._ob_next = &refchain;
 929         _Py_RefTotal = 0;
 930 }
 931
 932 void
 933 _Py_NewReference(PyObject *op)
 934 {
 935         _Py_RefTotal++;
 936         op->ob_refcnt = 1;
 937         op->_ob_next = refchain._ob_next;
 938         op->_ob_prev = &refchain;
 939         refchain._ob_next->_ob_prev = op;
 940         refchain._ob_next = op;
 941 #ifdef COUNT_ALLOCS
 942         inc_count(op->ob_type);
 943 #endif
 944 }
 945
 946 void
 947 _Py_ForgetReference(register PyObject *op)
 948 {
 949 #ifdef SLOW_UNREF_CHECK
 950         register PyObject *p;
 951 #endif
 952         if (op->ob_refcnt < 0)
 953                 Py_FatalError("UNREF negative refcnt");
 954         if (op == &refchain ||
 955             op->_ob_prev->_ob_next != op || op->_ob_next->_ob_prev != op)
 956                 Py_FatalError("UNREF invalid object");
 957 #ifdef SLOW_UNREF_CHECK
 958         for (p = refchain._ob_next; p != &refchain; p = p->_ob_next) {
 959                 if (p == op)
 960                         break;
 961         }
 962         if (p == &refchain) /* Not found */
 963                 Py_FatalError("UNREF unknown object");
 964 #endif
 965         op->_ob_next->_ob_prev = op->_ob_prev;
 966         op->_ob_prev->_ob_next = op->_ob_next;
 967         op->_ob_next = op->_ob_prev = NULL;
 968 #ifdef COUNT_ALLOCS
 969         op->ob_type->tp_free++;
 970 #endif
 971 }
 972
 973 void
 974 _Py_Dealloc(PyObject *op)
 975 {
 976         destructor dealloc = op->ob_type->tp_dealloc;
 977         _Py_ForgetReference(op);
 978         (*dealloc)(op);
 979 }
 980
 981 void
 982 _Py_PrintReferences(FILE *fp)
 983 {
 984         PyObject *op;
 985         fprintf(fp, "Remaining objects:\n");
 986         for (op = refchain._ob_next; op != &refchain; op = op->_ob_next) {
 987                 fprintf(fp, "[%d] ", op->ob_refcnt);
 988                 if (PyObject_Print(op, fp, 0) != 0)
 989                         PyErr_Clear();
 990                 putc('\n', fp);
 991         }
 992 }
 993
 994 PyObject *
 995 _Py_GetObjects(PyObject *self, PyObject *args)
 996 {
 997         int i, n;
 998         PyObject *t = NULL;
 999         PyObject *res, *op;
1000
1001         if (!PyArg_ParseTuple(args, "i|O", &n, &t))
1002                 return NULL;
1003         op = refchain._ob_next;
1004         res = PyList_New(0);
1005         if (res == NULL)
1006                 return NULL;
1007         for (i = 0; (n == 0 || i < n) && op != &refchain; i++) {
1008                 while (op == self || op == args || op == res || op == t ||
1009                        t != NULL && op->ob_type != (PyTypeObject *) t) {
1010                         op = op->_ob_next;
1011                         if (op == &refchain)
1012                                 return res;
1013                 }
1014                 if (PyList_Append(res, op) < 0) {
1015                         Py_DECREF(res);
1016                         return NULL;
1017                 }
1018                 op = op->_ob_next;
1019         }
1020         return res;
1021 }
1022
1023 #endif
1024
1025
1026 /* Hack to force loading of cobject.o */
1027 PyTypeObject *_Py_cobject_hack = &PyCObject_Type;
1028
1029
1030 /* Hack to force loading of abstract.o */
1031 int (*_Py_abstract_hack)(PyObject *) = &PyObject_Size;
1032
1033
1034 /* Python's malloc wrappers (see pymem.h) */
1035
1036 void *
1037 PyMem_Malloc(size_t nbytes)
1038 {
1039 #if _PyMem_EXTRA > 0
1040         if (nbytes == 0)
1041                 nbytes = _PyMem_EXTRA;
1042 #endif
1043         return PyMem_MALLOC(nbytes);
1044 }
1045
1046 void *
1047 PyMem_Realloc(void *p, size_t nbytes)
1048 {
1049 #if _PyMem_EXTRA > 0
1050         if (nbytes == 0)
1051                 nbytes = _PyMem_EXTRA;
1052 #endif
1053         return PyMem_REALLOC(p, nbytes);
1054 }
1055
1056 void
1057 PyMem_Free(void *p)
1058 {
1059         PyMem_FREE(p);
1060 }
1061
1062
1063 /* Python's object malloc wrappers (see objimpl.h) */
1064
1065 void *
1066 PyObject_Malloc(size_t nbytes)
1067 {
1068         return PyObject_MALLOC(nbytes);
1069 }
1070
1071 void *
1072 PyObject_Realloc(void *p, size_t nbytes)
1073 {
1074         return PyObject_REALLOC(p, nbytes);
1075 }
1076
1077 void
1078 PyObject_Free(void *p)
1079 {
1080         PyObject_FREE(p);
1081 }
1082
1083
1084 /* These methods are used to control infinite recursion in repr, str, print,
1085    etc.  Container objects that may recursively contain themselves,
1086    e.g. builtin dictionaries and lists, should used Py_ReprEnter() and
1087    Py_ReprLeave() to avoid infinite recursion.
1088
1089    Py_ReprEnter() returns 0 the first time it is called for a particular
1090    object and 1 every time thereafter.  It returns -1 if an exception
1091    occurred.  Py_ReprLeave() has no return value.
1092
1093    See dictobject.c and listobject.c for examples of use.
1094 */
1095
1096 #define KEY "Py_Repr"
1097
1098 int
1099 Py_ReprEnter(PyObject *obj)
1100 {
1101         PyObject *dict;
1102         PyObject *list;
1103         int i;
1104
1105         dict = PyThreadState_GetDict();
1106         if (dict == NULL)
1107                 return -1;
1108         list = PyDict_GetItemString(dict, KEY);
1109         if (list == NULL) {
1110                 list = PyList_New(0);
1111                 if (list == NULL)
1112                         return -1;
1113                 if (PyDict_SetItemString(dict, KEY, list) < 0)
1114                         return -1;
1115                 Py_DECREF(list);
1116         }
1117         i = PyList_GET_SIZE(list);
1118         while (--i >= 0) {
1119                 if (PyList_GET_ITEM(list, i) == obj)
1120                         return 1;
1121         }
1122         PyList_Append(list, obj);
1123         return 0;
1124 }
1125
1126 void
1127 Py_ReprLeave(PyObject *obj)
1128 {
1129         PyObject *dict;
1130         PyObject *list;
1131         int i;
1132
1133         dict = PyThreadState_GetDict();
1134         if (dict == NULL)
1135                 return;
1136         list = PyDict_GetItemString(dict, KEY);
1137         if (list == NULL || !PyList_Check(list))
1138                 return;
1139         i = PyList_GET_SIZE(list);
1140         /* Count backwards because we always expect obj to be list[-1] */
1141         while (--i >= 0) {
1142                 if (PyList_GET_ITEM(list, i) == obj) {
1143                         PyList_SetSlice(list, i, i + 1, NULL);
1144                         break;
1145                 }
1146         }
1147 }
1148
1149 /*
1150   trashcan
1151   CT 2k0130
1152   non-recursively destroy nested objects
1153
1154   CT 2k0223
1155   everything is now done in a macro.
1156
1157   CT 2k0305
1158   modified to use functions, after Tim Peter's suggestion.
1159
1160   CT 2k0309
1161   modified to restore a possible error.
1162
1163   CT 2k0325
1164   added better safe than sorry check for threadstate
1165
1166   CT 2k0422
1167   complete rewrite. We now build a chain via ob_type
1168   and save the limited number of types in ob_refcnt.
1169   This is perfect since we don't need any memory.
1170   A patch for free-threading would need just a lock.
1171 */
1172
1173 #define Py_TRASHCAN_TUPLE       1
1174 #define Py_TRASHCAN_LIST        2
1175 #define Py_TRASHCAN_DICT        3
1176 #define Py_TRASHCAN_FRAME       4
1177 #define Py_TRASHCAN_TRACEBACK   5
1178 /* extend here if other objects want protection */
1179
1180 int _PyTrash_delete_nesting = 0;
1181
1182 PyObject * _PyTrash_delete_later = NULL;
1183
1184 void
1185 _PyTrash_deposit_object(PyObject *op)
1186 {
1187         int typecode;
1188
1189         if (PyTuple_Check(op))
1190                 typecode = Py_TRASHCAN_TUPLE;
1191         else if (PyList_Check(op))
1192                 typecode = Py_TRASHCAN_LIST;
1193         else if (PyDict_Check(op))
1194                 typecode = Py_TRASHCAN_DICT;
1195         else if (PyFrame_Check(op))
1196                 typecode = Py_TRASHCAN_FRAME;
1197         else if (PyTraceBack_Check(op))
1198                 typecode = Py_TRASHCAN_TRACEBACK;
1199         else /* We have a bug here -- those are the only types in GC */ {
1200                 Py_FatalError("Type not supported in GC -- internal bug");
1201                 return; /* pacify compiler -- execution never here */
1202         }
1203         op->ob_refcnt = typecode;
1204
1205         op->ob_type = (PyTypeObject*)_PyTrash_delete_later;
1206         _PyTrash_delete_later = op;
1207 }
1208
1209 void
1210 _PyTrash_destroy_chain(void)
1211 {
1212         while (_PyTrash_delete_later) {
1213                 PyObject *shredder = _PyTrash_delete_later;
1214                 _PyTrash_delete_later = (PyObject*) shredder->ob_type;
1215
1216                 switch (shredder->ob_refcnt) {
1217                 case Py_TRASHCAN_TUPLE:
1218                         shredder->ob_type = &PyTuple_Type;
1219                         break;
1220                 case Py_TRASHCAN_LIST:
1221                         shredder->ob_type = &PyList_Type;
1222                         break;
1223                 case Py_TRASHCAN_DICT:
1224                         shredder->ob_type = &PyDict_Type;
1225                         break;
1226                 case Py_TRASHCAN_FRAME:
1227                         shredder->ob_type = &PyFrame_Type;
1228                         break;
1229                 case Py_TRASHCAN_TRACEBACK:
1230                         shredder->ob_type = &PyTraceBack_Type;
1231                         break;
1232                 }
1233                 _Py_NewReference(shredder);
1234
1235                 ++_PyTrash_delete_nesting;
1236                 Py_DECREF(shredder);
1237                 --_PyTrash_delete_nesting;
1238         }
1239 }