Objects/object.c

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