1 

     2 /* Generic object operations; and implementation of None (NoObject) */

     3 

     4 #include "Python.h"

     5 

     6 #ifdef __cplusplus

     7 extern "C" {

     8 #endif

     9 

    10 #ifdef Py_REF_DEBUG

    11 Py_ssize_t _Py_RefTotal;

    12 

    13 Py_ssize_t

    14 _Py_GetRefTotal(void)

    15 {

    16 	PyObject *o;

    17 	Py_ssize_t total = _Py_RefTotal;

    18         /* ignore the references to the dummy object of the dicts and sets

    19            because they are not reliable and not useful (now that the

    20            hash table code is well-tested) */

    21 	o = _PyDict_Dummy();

    22 	if (o != NULL)

    23 		total -= o->ob_refcnt;

    24 	o = _PySet_Dummy();

    25 	if (o != NULL)

    26 		total -= o->ob_refcnt;

    27 	return total;

    28 }

    29 #endif /* Py_REF_DEBUG */

    30 

    31 int Py_DivisionWarningFlag;

    32 int Py_Py3kWarningFlag;

    33 

    34 /* Object allocation routines used by NEWOBJ and NEWVAROBJ macros.

    35    These are used by the individual routines for object creation.

    36    Do not call them otherwise, they do not initialize the object! */

    37 

    38 #ifdef Py_TRACE_REFS

    39 /* Head of circular doubly-linked list of all objects.  These are linked

    40  * together via the _ob_prev and _ob_next members of a PyObject, which

    41  * exist only in a Py_TRACE_REFS build.

    42  */

    43 static PyObject refchain = {&refchain, &refchain};

    44 

    45 /* Insert op at the front of the list of all objects.  If force is true,

    46  * op is added even if _ob_prev and _ob_next are non-NULL already.  If

    47  * force is false amd _ob_prev or _ob_next are non-NULL, do nothing.

    48  * force should be true if and only if op points to freshly allocated,

    49  * uninitialized memory, or you've unlinked op from the list and are

    50  * relinking it into the front.

    51  * Note that objects are normally added to the list via _Py_NewReference,

    52  * which is called by PyObject_Init.  Not all objects are initialized that

    53  * way, though; exceptions include statically allocated type objects, and

    54  * statically allocated singletons (like Py_True and Py_None).

    55  */

    56 void

    57 _Py_AddToAllObjects(PyObject *op, int force)

    58 {

    59 #ifdef  Py_DEBUG

    60 	if (!force) {

    61 		/* If it's initialized memory, op must be in or out of

    62 		 * the list unambiguously.

    63 		 */

    64 		assert((op->_ob_prev == NULL) == (op->_ob_next == NULL));

    65 	}

    66 #endif

    67 	if (force || op->_ob_prev == NULL) {

    68 		op->_ob_next = refchain._ob_next;

    69 		op->_ob_prev = &refchain;

    70 		refchain._ob_next->_ob_prev = op;

    71 		refchain._ob_next = op;

    72 	}

    73 }

    74 #endif	/* Py_TRACE_REFS */

    75 

    76 #ifdef COUNT_ALLOCS

    77 static PyTypeObject *type_list;

    78 /* All types are added to type_list, at least when

    79    they get one object created. That makes them

    80    immortal, which unfortunately contributes to

    81    garbage itself. If unlist_types_without_objects

    82    is set, they will be removed from the type_list

    83    once the last object is deallocated. */

    84 int unlist_types_without_objects;

    85 extern int tuple_zero_allocs, fast_tuple_allocs;

    86 extern int quick_int_allocs, quick_neg_int_allocs;

    87 extern int null_strings, one_strings;

    88 void

    89 dump_counts(FILE* f)

    90 {

    91 	PyTypeObject *tp;

    92 

    93 	for (tp = type_list; tp; tp = tp->tp_next)

    94 		fprintf(f, "%s alloc'd: %d, freed: %d, max in use: %d\n",

    95 			tp->tp_name, tp->tp_allocs, tp->tp_frees,

    96 			tp->tp_maxalloc);

    97 	fprintf(f, "fast tuple allocs: %d, empty: %d\n",

    98 		fast_tuple_allocs, tuple_zero_allocs);

    99 	fprintf(f, "fast int allocs: pos: %d, neg: %d\n",

   100 		quick_int_allocs, quick_neg_int_allocs);

   101 	fprintf(f, "null strings: %d, 1-strings: %d\n",

   102 		null_strings, one_strings);

   103 }

   104 

   105 PyObject *

   106 get_counts(void)

   107 {

   108 	PyTypeObject *tp;

   109 	PyObject *result;

   110 	PyObject *v;

   111 

   112 	result = PyList_New(0);

   113 	if (result == NULL)

   114 		return NULL;

   115 	for (tp = type_list; tp; tp = tp->tp_next) {

   116 		v = Py_BuildValue("(snnn)", tp->tp_name, tp->tp_allocs,

   117 				  tp->tp_frees, tp->tp_maxalloc);

   118 		if (v == NULL) {

   119 			Py_DECREF(result);

   120 			return NULL;

   121 		}

   122 		if (PyList_Append(result, v) < 0) {

   123 			Py_DECREF(v);

   124 			Py_DECREF(result);

   125 			return NULL;

   126 		}

   127 		Py_DECREF(v);

   128 	}

   129 	return result;

   130 }

   131 

   132 void

   133 inc_count(PyTypeObject *tp)

   134 {

   135 	if (tp->tp_next == NULL && tp->tp_prev == NULL) {

   136 		/* first time; insert in linked list */

   137 		if (tp->tp_next != NULL) /* sanity check */

   138 			Py_FatalError("XXX inc_count sanity check");

   139 		if (type_list)

   140 			type_list->tp_prev = tp;

   141 		tp->tp_next = type_list;

   142 		/* Note that as of Python 2.2, heap-allocated type objects

   143 		 * can go away, but this code requires that they stay alive

   144 		 * until program exit.  That's why we're careful with

   145 		 * refcounts here.  type_list gets a new reference to tp,

   146 		 * while ownership of the reference type_list used to hold

   147 		 * (if any) was transferred to tp->tp_next in the line above.

   148 		 * tp is thus effectively immortal after this.

   149 		 */

   150 		Py_INCREF(tp);

   151 		type_list = tp;

   152 #ifdef Py_TRACE_REFS

   153 		/* Also insert in the doubly-linked list of all objects,

   154 		 * if not already there.

   155 		 */

   156 		_Py_AddToAllObjects((PyObject *)tp, 0);

   157 #endif

   158 	}

   159 	tp->tp_allocs++;

   160 	if (tp->tp_allocs - tp->tp_frees > tp->tp_maxalloc)

   161 		tp->tp_maxalloc = tp->tp_allocs - tp->tp_frees;

   162 }

   163 

   164 void dec_count(PyTypeObject *tp)

   165 {

   166 	tp->tp_frees++;

   167 	if (unlist_types_without_objects &&

   168 	    tp->tp_allocs == tp->tp_frees) {

   169 		/* unlink the type from type_list */

   170 		if (tp->tp_prev)

   171 			tp->tp_prev->tp_next = tp->tp_next;

   172 		else

   173 			type_list = tp->tp_next;

   174 		if (tp->tp_next)

   175 			tp->tp_next->tp_prev = tp->tp_prev;

   176 		tp->tp_next = tp->tp_prev = NULL;

   177 		Py_DECREF(tp);

   178 	}

   179 }

   180 

   181 #endif

   182 

   183 #ifdef Py_REF_DEBUG

   184 /* Log a fatal error; doesn't return. */

   185 void

   186 _Py_NegativeRefcount(const char *fname, int lineno, PyObject *op)

   187 {

   188 	char buf[300];

   189 

   190 	PyOS_snprintf(buf, sizeof(buf),

   191 		      "%s:%i object at %p has negative ref count "

   192 		      "%" PY_FORMAT_SIZE_T "d",

   193 		      fname, lineno, op, op->ob_refcnt);

   194 	Py_FatalError(buf);

   195 }

   196 

   197 #endif /* Py_REF_DEBUG */

   198 

   199 void

   200 Py_IncRef(PyObject *o)

   201 {

   202     Py_XINCREF(o);

   203 }

   204 

   205 void

   206 Py_DecRef(PyObject *o)

   207 {

   208     Py_XDECREF(o);

   209 }

   210 

   211 PyObject *

   212 PyObject_Init(PyObject *op, PyTypeObject *tp)

   213 {

   214 	if (op == NULL)

   215 		return PyErr_NoMemory();

   216 	/* Any changes should be reflected in PyObject_INIT (objimpl.h) */

   217 	Py_TYPE(op) = tp;

   218 	_Py_NewReference(op);

   219 	return op;

   220 }

   221 

   222 PyVarObject *

   223 PyObject_InitVar(PyVarObject *op, PyTypeObject *tp, Py_ssize_t size)

   224 {

   225 	if (op == NULL)

   226 		return (PyVarObject *) PyErr_NoMemory();

   227 	/* Any changes should be reflected in PyObject_INIT_VAR */

   228 	op->ob_size = size;

   229 	Py_TYPE(op) = tp;

   230 	_Py_NewReference((PyObject *)op);

   231 	return op;

   232 }

   233 

   234 PyObject *

   235 _PyObject_New(PyTypeObject *tp)

   236 {

   237 	PyObject *op;

   238 	op = (PyObject *) PyObject_MALLOC(_PyObject_SIZE(tp));

   239 	if (op == NULL)

   240 		return PyErr_NoMemory();

   241 	return PyObject_INIT(op, tp);

   242 }

   243 

   244 PyVarObject *

   245 _PyObject_NewVar(PyTypeObject *tp, Py_ssize_t nitems)

   246 {

   247 	PyVarObject *op;

   248 	const size_t size = _PyObject_VAR_SIZE(tp, nitems);

   249 	op = (PyVarObject *) PyObject_MALLOC(size);

   250 	if (op == NULL)

   251 		return (PyVarObject *)PyErr_NoMemory();

   252 	return PyObject_INIT_VAR(op, tp, nitems);

   253 }

   254 

   255 /* for binary compatibility with 2.2 */

   256 #undef _PyObject_Del

   257 void

   258 _PyObject_Del(PyObject *op)

   259 {

   260 	PyObject_FREE(op);

   261 }

   262 

   263 /* Implementation of PyObject_Print with recursion checking */

   264 static int

   265 internal_print(PyObject *op, FILE *fp, int flags, int nesting)

   266 {

   267 	int ret = 0;

   268 	if (nesting > 10) {

   269 		PyErr_SetString(PyExc_RuntimeError, "print recursion");

   270 		return -1;

   271 	}

   272 	if (PyErr_CheckSignals())

   273 		return -1;

   274 #ifdef USE_STACKCHECK

   275 	if (PyOS_CheckStack()) {

   276 		PyErr_SetString(PyExc_MemoryError, "stack overflow");

   277 		return -1;

   278 	}

   279 #endif

   280 	clearerr(fp); /* Clear any previous error condition */

   281 	if (op == NULL) {

   282 		Py_BEGIN_ALLOW_THREADS

   283 		fprintf(fp, "<nil>");

   284 		Py_END_ALLOW_THREADS

   285 	}

   286 	else {

   287 		if (op->ob_refcnt <= 0)

   288 			/* XXX(twouters) cast refcount to long until %zd is

   289 			   universally available */

   290 			Py_BEGIN_ALLOW_THREADS

   291 			fprintf(fp, "<refcnt %ld at %p>",

   292 				(long)op->ob_refcnt, op);

   293 			Py_END_ALLOW_THREADS

   294 		else if (Py_TYPE(op)->tp_print == NULL) {

   295 			PyObject *s;

   296 			if (flags & Py_PRINT_RAW)

   297 				s = PyObject_Str(op);

   298 			else

   299 				s = PyObject_Repr(op);

   300 			if (s == NULL)

   301 				ret = -1;

   302 			else {

   303 				ret = internal_print(s, fp, Py_PRINT_RAW,

   304 						     nesting+1);

   305 			}

   306 			Py_XDECREF(s);

   307 		}

   308 		else

   309 			ret = (*Py_TYPE(op)->tp_print)(op, fp, flags);

   310 	}

   311 	if (ret == 0) {

   312 		if (ferror(fp)) {

   313 			PyErr_SetFromErrno(PyExc_IOError);

   314 			clearerr(fp);

   315 			ret = -1;

   316 		}

   317 	}

   318 	return ret;

   319 }

   320 

   321 int

   322 PyObject_Print(PyObject *op, FILE *fp, int flags)

   323 {

   324 	return internal_print(op, fp, flags, 0);

   325 }

   326 

   327 

   328 /* For debugging convenience.  See Misc/gdbinit for some useful gdb hooks */

   329 void _PyObject_Dump(PyObject* op)

   330 {

   331 	if (op == NULL)

   332 		fprintf(stderr, "NULL\n");

   333 	else {

   334 		fprintf(stderr, "object  : ");

   335 		(void)PyObject_Print(op, stderr, 0);

   336 		/* XXX(twouters) cast refcount to long until %zd is

   337 		   universally available */

   338 		fprintf(stderr, "\n"

   339 			"type    : %s\n"

   340 			"refcount: %ld\n"

   341 			"address : %p\n",

   342 			Py_TYPE(op)==NULL ? "NULL" : Py_TYPE(op)->tp_name,

   343 			(long)op->ob_refcnt,

   344 			op);

   345 	}

   346 }

   347 

   348 PyObject *

   349 PyObject_Repr(PyObject *v)

   350 {

   351 	if (PyErr_CheckSignals())

   352 		return NULL;

   353 #ifdef USE_STACKCHECK

   354 	if (PyOS_CheckStack()) {

   355 		PyErr_SetString(PyExc_MemoryError, "stack overflow");

   356 		return NULL;

   357 	}

   358 #endif

   359 	if (v == NULL)

   360 		return PyString_FromString("<NULL>");

   361 	else if (Py_TYPE(v)->tp_repr == NULL)

   362 		return PyString_FromFormat("<%s object at %p>",

   363 					   Py_TYPE(v)->tp_name, v);

   364 	else {

   365 		PyObject *res;

   366 		res = (*Py_TYPE(v)->tp_repr)(v);

   367 		if (res == NULL)

   368 			return NULL;

   369 #ifdef Py_USING_UNICODE

   370 		if (PyUnicode_Check(res)) {

   371 			PyObject* str;

   372 			str = PyUnicode_AsEncodedString(res, NULL, NULL);

   373 			Py_DECREF(res);

   374 			if (str)

   375 				res = str;

   376 			else

   377 				return NULL;

   378 		}

   379 #endif

   380 		if (!PyString_Check(res)) {

   381 			PyErr_Format(PyExc_TypeError,

   382 				     "__repr__ returned non-string (type %.200s)",

   383 				     Py_TYPE(res)->tp_name);

   384 			Py_DECREF(res);

   385 			return NULL;

   386 		}

   387 		return res;

   388 	}

   389 }

   390 

   391 PyObject *

   392 _PyObject_Str(PyObject *v)

   393 {

   394 	PyObject *res;

   395 	int type_ok;

   396 	if (v == NULL)

   397 		return PyString_FromString("<NULL>");

   398 	if (PyString_CheckExact(v)) {

   399 		Py_INCREF(v);

   400 		return v;

   401 	}

   402 #ifdef Py_USING_UNICODE

   403 	if (PyUnicode_CheckExact(v)) {

   404 		Py_INCREF(v);

   405 		return v;

   406 	}

   407 #endif

   408 	if (Py_TYPE(v)->tp_str == NULL)

   409 		return PyObject_Repr(v);

   410 

   411 	/* It is possible for a type to have a tp_str representation that loops

   412 	   infinitely. */

   413 	if (Py_EnterRecursiveCall(" while getting the str of an object"))

   414 		return NULL;

   415 	res = (*Py_TYPE(v)->tp_str)(v);

   416 	Py_LeaveRecursiveCall();

   417 	if (res == NULL)

   418 		return NULL;

   419 	type_ok = PyString_Check(res);

   420 #ifdef Py_USING_UNICODE

   421 	type_ok = type_ok || PyUnicode_Check(res);

   422 #endif

   423 	if (!type_ok) {

   424 		PyErr_Format(PyExc_TypeError,

   425 			     "__str__ returned non-string (type %.200s)",

   426 			     Py_TYPE(res)->tp_name);

   427 		Py_DECREF(res);

   428 		return NULL;

   429 	}

   430 	return res;

   431 }

   432 

   433 PyObject *

   434 PyObject_Str(PyObject *v)

   435 {

   436 	PyObject *res = _PyObject_Str(v);

   437 	if (res == NULL)

   438 		return NULL;

   439 #ifdef Py_USING_UNICODE

   440 	if (PyUnicode_Check(res)) {

   441 		PyObject* str;

   442 		str = PyUnicode_AsEncodedString(res, NULL, NULL);

   443 		Py_DECREF(res);

   444 		if (str)

   445 			res = str;

   446 		else

   447 		    	return NULL;

   448 	}

   449 #endif

   450 	assert(PyString_Check(res));

   451 	return res;

   452 }

   453 

   454 #ifdef Py_USING_UNICODE

   455 PyObject *

   456 PyObject_Unicode(PyObject *v)

   457 {

   458 	PyObject *res;

   459 	PyObject *func;

   460 	PyObject *str;

   461 	int unicode_method_found = 0;

   462 	static PyObject *unicodestr;

   463 

   464 	if (v == NULL) {

   465 		res = PyString_FromString("<NULL>");

   466 		if (res == NULL)

   467 			return NULL;

   468 		str = PyUnicode_FromEncodedObject(res, NULL, "strict");

   469 		Py_DECREF(res);

   470 		return str;

   471 	} else if (PyUnicode_CheckExact(v)) {

   472 		Py_INCREF(v);

   473 		return v;

   474 	}

   475 

   476 	/* Try the __unicode__ method */

   477 	if (unicodestr == NULL) {

   478 		unicodestr= PyString_InternFromString("__unicode__");

   479 		if (unicodestr == NULL)

   480 			return NULL;

   481 	}

   482 	if (PyInstance_Check(v)) {

   483 		/* We're an instance of a classic class */

   484 		/* Try __unicode__ from the instance -- alas we have no type */

   485 		func = PyObject_GetAttr(v, unicodestr);

   486 		if (func != NULL) {

   487 			unicode_method_found = 1;

   488 			res = PyObject_CallFunctionObjArgs(func, NULL);

   489 			Py_DECREF(func);

   490 		}

   491 		else {

   492 			PyErr_Clear(); 

   493 		}

   494 	}

   495 	else {

   496 		/* Not a classic class instance, try __unicode__ from type */

   497 		/* _PyType_Lookup doesn't create a reference */

   498 		func = _PyType_Lookup(Py_TYPE(v), unicodestr);

   499 		if (func != NULL) {

   500 			unicode_method_found = 1;

   501 			res = PyObject_CallFunctionObjArgs(func, v, NULL);

   502 		}

   503 		else {

   504 			PyErr_Clear();

   505 		}

   506 	}

   507 

   508 	/* Didn't find __unicode__ */

   509 	if (!unicode_method_found) {

   510 		if (PyUnicode_Check(v)) {

   511 			/* For a Unicode subtype that's didn't overwrite __unicode__,

   512 			   return a true Unicode object with the same data. */

   513 			return PyUnicode_FromUnicode(PyUnicode_AS_UNICODE(v),

   514 						     PyUnicode_GET_SIZE(v));

   515 		}

   516 		if (PyString_CheckExact(v)) {

   517 			Py_INCREF(v);

   518 			res = v;

   519 		}

   520 		else {

   521 			if (Py_TYPE(v)->tp_str != NULL)

   522 				res = (*Py_TYPE(v)->tp_str)(v);

   523 			else

   524 				res = PyObject_Repr(v);

   525 		}

   526 	}

   527 

   528 	if (res == NULL)

   529 		return NULL;

   530 	if (!PyUnicode_Check(res)) {

   531 		str = PyUnicode_FromEncodedObject(res, NULL, "strict");

   532 		Py_DECREF(res);

   533 		res = str;

   534 	}

   535 	return res;

   536 }

   537 #endif

   538 

   539 

   540 /* Helper to warn about deprecated tp_compare return values.  Return:

   541    -2 for an exception;

   542    -1 if v <  w;

   543     0 if v == w;

   544     1 if v  > w.

   545    (This function cannot return 2.)

   546 */

   547 static int

   548 adjust_tp_compare(int c)

   549 {

   550 	if (PyErr_Occurred()) {

   551 		if (c != -1 && c != -2) {

   552 			PyObject *t, *v, *tb;

   553 			PyErr_Fetch(&t, &v, &tb);

   554 			if (PyErr_Warn(PyExc_RuntimeWarning,

   555 				       "tp_compare didn't return -1 or -2 "

   556 				       "for exception") < 0) {

   557 				Py_XDECREF(t);

   558 				Py_XDECREF(v);

   559 				Py_XDECREF(tb);

   560 			}

   561 			else

   562 				PyErr_Restore(t, v, tb);

   563 		}

   564 		return -2;

   565 	}

   566 	else if (c < -1 || c > 1) {

   567 		if (PyErr_Warn(PyExc_RuntimeWarning,

   568 			       "tp_compare didn't return -1, 0 or 1") < 0)

   569 			return -2;

   570 		else

   571 			return c < -1 ? -1 : 1;

   572 	}

   573 	else {

   574 		assert(c >= -1 && c <= 1);

   575 		return c;

   576 	}

   577 }

   578 

   579 

   580 /* Macro to get the tp_richcompare field of a type if defined */

   581 #define RICHCOMPARE(t) (PyType_HasFeature((t), Py_TPFLAGS_HAVE_RICHCOMPARE) \

   582                          ? (t)->tp_richcompare : NULL)

   583 

   584 /* Map rich comparison operators to their swapped version, e.g. LT --> GT */

   585 int _Py_SwappedOp[] = {Py_GT, Py_GE, Py_EQ, Py_NE, Py_LT, Py_LE};

   586 

   587 /* Try a genuine rich comparison, returning an object.  Return:

   588    NULL for exception;

   589    NotImplemented if this particular rich comparison is not implemented or

   590      undefined;

   591    some object not equal to NotImplemented if it is implemented

   592      (this latter object may not be a Boolean).

   593 */

   594 static PyObject *

   595 try_rich_compare(PyObject *v, PyObject *w, int op)

   596 {

   597 	richcmpfunc f;

   598 	PyObject *res;

   599 

   600 	if (v->ob_type != w->ob_type &&

   601 	    PyType_IsSubtype(w->ob_type, v->ob_type) &&

   602 	    (f = RICHCOMPARE(w->ob_type)) != NULL) {

   603 		res = (*f)(w, v, _Py_SwappedOp[op]);

   604 		if (res != Py_NotImplemented)

   605 			return res;

   606 		Py_DECREF(res);

   607 	}

   608 	if ((f = RICHCOMPARE(v->ob_type)) != NULL) {

   609 		res = (*f)(v, w, op);

   610 		if (res != Py_NotImplemented)

   611 			return res;

   612 		Py_DECREF(res);

   613 	}

   614 	if ((f = RICHCOMPARE(w->ob_type)) != NULL) {

   615 		return (*f)(w, v, _Py_SwappedOp[op]);

   616 	}

   617 	res = Py_NotImplemented;

   618 	Py_INCREF(res);

   619 	return res;

   620 }

   621 

   622 /* Try a genuine rich comparison, returning an int.  Return:

   623    -1 for exception (including the case where try_rich_compare() returns an

   624       object that's not a Boolean);

   625     0 if the outcome is false;

   626     1 if the outcome is true;

   627     2 if this particular rich comparison is not implemented or undefined.

   628 */

   629 static int

   630 try_rich_compare_bool(PyObject *v, PyObject *w, int op)

   631 {

   632 	PyObject *res;

   633 	int ok;

   634 

   635 	if (RICHCOMPARE(v->ob_type) == NULL && RICHCOMPARE(w->ob_type) == NULL)

   636 		return 2; /* Shortcut, avoid INCREF+DECREF */

   637 	res = try_rich_compare(v, w, op);

   638 	if (res == NULL)

   639 		return -1;

   640 	if (res == Py_NotImplemented) {

   641 		Py_DECREF(res);

   642 		return 2;

   643 	}

   644 	ok = PyObject_IsTrue(res);

   645 	Py_DECREF(res);

   646 	return ok;

   647 }

   648 

   649 /* Try rich comparisons to determine a 3-way comparison.  Return:

   650    -2 for an exception;

   651    -1 if v  < w;

   652     0 if v == w;

   653     1 if v  > w;

   654     2 if this particular rich comparison is not implemented or undefined.

   655 */

   656 static int

   657 try_rich_to_3way_compare(PyObject *v, PyObject *w)

   658 {

   659 	static struct { int op; int outcome; } tries[3] = {

   660 		/* Try this operator, and if it is true, use this outcome: */

   661 		{Py_EQ, 0},

   662 		{Py_LT, -1},

   663 		{Py_GT, 1},

   664 	};

   665 	int i;

   666 

   667 	if (RICHCOMPARE(v->ob_type) == NULL && RICHCOMPARE(w->ob_type) == NULL)

   668 		return 2; /* Shortcut */

   669 

   670 	for (i = 0; i < 3; i++) {

   671 		switch (try_rich_compare_bool(v, w, tries[i].op)) {

   672 		case -1:

   673 			return -2;

   674 		case 1:

   675 			return tries[i].outcome;

   676 		}

   677 	}

   678 

   679 	return 2;

   680 }

   681 

   682 /* Try a 3-way comparison, returning an int.  Return:

   683    -2 for an exception;

   684    -1 if v <  w;

   685     0 if v == w;

   686     1 if v  > w;

   687     2 if this particular 3-way comparison is not implemented or undefined.

   688 */

   689 static int

   690 try_3way_compare(PyObject *v, PyObject *w)

   691 {

   692 	int c;

   693 	cmpfunc f;

   694 

   695 	/* Comparisons involving instances are given to instance_compare,

   696 	   which has the same return conventions as this function. */

   697 

   698 	f = v->ob_type->tp_compare;

   699 	if (PyInstance_Check(v))

   700 		return (*f)(v, w);

   701 	if (PyInstance_Check(w))

   702 		return (*w->ob_type->tp_compare)(v, w);

   703 

   704 	/* If both have the same (non-NULL) tp_compare, use it. */

   705 	if (f != NULL && f == w->ob_type->tp_compare) {

   706 		c = (*f)(v, w);

   707 		return adjust_tp_compare(c);

   708 	}

   709 

   710 	/* If either tp_compare is _PyObject_SlotCompare, that's safe. */

   711 	if (f == _PyObject_SlotCompare ||

   712 	    w->ob_type->tp_compare == _PyObject_SlotCompare)

   713 		return _PyObject_SlotCompare(v, w);

   714 

   715 	/* If we're here, v and w,

   716 	    a) are not instances;

   717 	    b) have different types or a type without tp_compare; and

   718 	    c) don't have a user-defined tp_compare.

   719 	   tp_compare implementations in C assume that both arguments

   720 	   have their type, so we give up if the coercion fails or if

   721 	   it yields types which are still incompatible (which can

   722 	   happen with a user-defined nb_coerce).

   723 	*/

   724 	c = PyNumber_CoerceEx(&v, &w);

   725 	if (c < 0)

   726 		return -2;

   727 	if (c > 0)

   728 		return 2;

   729 	f = v->ob_type->tp_compare;

   730 	if (f != NULL && f == w->ob_type->tp_compare) {

   731 		c = (*f)(v, w);

   732 		Py_DECREF(v);

   733 		Py_DECREF(w);

   734 		return adjust_tp_compare(c);

   735 	}

   736 

   737 	/* No comparison defined */

   738 	Py_DECREF(v);

   739 	Py_DECREF(w);

   740 	return 2;

   741 }

   742 

   743 /* Final fallback 3-way comparison, returning an int.  Return:

   744    -2 if an error occurred;

   745    -1 if v <  w;

   746     0 if v == w;

   747     1 if v >  w.

   748 */

   749 static int

   750 default_3way_compare(PyObject *v, PyObject *w)

   751 {

   752 	int c;

   753 	const char *vname, *wname;

   754 

   755 	if (v->ob_type == w->ob_type) {

   756 		/* When comparing these pointers, they must be cast to

   757 		 * integer types (i.e. Py_uintptr_t, our spelling of C9X's

   758 		 * uintptr_t).  ANSI specifies that pointer compares other

   759 		 * than == and != to non-related structures are undefined.

   760 		 */

   761 		Py_uintptr_t vv = (Py_uintptr_t)v;

   762 		Py_uintptr_t ww = (Py_uintptr_t)w;

   763 		return (vv < ww) ? -1 : (vv > ww) ? 1 : 0;

   764 	}

   765 

   766 	/* None is smaller than anything */

   767 	if (v == Py_None)

   768 		return -1;

   769 	if (w == Py_None)

   770 		return 1;

   771 

   772 	/* different type: compare type names; numbers are smaller */

   773 	if (PyNumber_Check(v))

   774 		vname = "";

   775 	else

   776 		vname = v->ob_type->tp_name;

   777 	if (PyNumber_Check(w))

   778 		wname = "";

   779 	else

   780 		wname = w->ob_type->tp_name;

   781 	c = strcmp(vname, wname);

   782 	if (c < 0)

   783 		return -1;

   784 	if (c > 0)

   785 		return 1;

   786 	/* Same type name, or (more likely) incomparable numeric types */

   787 	return ((Py_uintptr_t)(v->ob_type) < (

   788 		Py_uintptr_t)(w->ob_type)) ? -1 : 1;

   789 }

   790 

   791 /* Do a 3-way comparison, by hook or by crook.  Return:

   792    -2 for an exception (but see below);

   793    -1 if v <  w;

   794     0 if v == w;

   795     1 if v >  w;

   796    BUT: if the object implements a tp_compare function, it returns

   797    whatever this function returns (whether with an exception or not).

   798 */

   799 static int

   800 do_cmp(PyObject *v, PyObject *w)

   801 {

   802 	int c;

   803 	cmpfunc f;

   804 

   805 	if (v->ob_type == w->ob_type

   806 	    && (f = v->ob_type->tp_compare) != NULL) {

   807 		c = (*f)(v, w);

   808 		if (PyInstance_Check(v)) {

   809 			/* Instance tp_compare has a different signature.

   810 			   But if it returns undefined we fall through. */

   811 			if (c != 2)

   812 				return c;

   813 			/* Else fall through to try_rich_to_3way_compare() */

   814 		}

   815 		else

   816 			return adjust_tp_compare(c);

   817 	}

   818 	/* We only get here if one of the following is true:

   819 	   a) v and w have different types

   820 	   b) v and w have the same type, which doesn't have tp_compare

   821 	   c) v and w are instances, and either __cmp__ is not defined or

   822 	      __cmp__ returns NotImplemented

   823 	*/

   824 	c = try_rich_to_3way_compare(v, w);

   825 	if (c < 2)

   826 		return c;

   827 	c = try_3way_compare(v, w);

   828 	if (c < 2)

   829 		return c;

   830 	return default_3way_compare(v, w);

   831 }

   832 

   833 /* Compare v to w.  Return

   834    -1 if v <  w or exception (PyErr_Occurred() true in latter case).

   835     0 if v == w.

   836     1 if v > w.

   837    XXX The docs (C API manual) say the return value is undefined in case

   838    XXX of error.

   839 */

   840 int

   841 PyObject_Compare(PyObject *v, PyObject *w)

   842 {

   843 	int result;

   844 

   845 	if (v == NULL || w == NULL) {

   846 		PyErr_BadInternalCall();

   847 		return -1;

   848 	}

   849 	if (v == w)

   850 		return 0;

   851 	if (Py_EnterRecursiveCall(" in cmp"))

   852 		return -1;

   853 	result = do_cmp(v, w);

   854 	Py_LeaveRecursiveCall();

   855 	return result < 0 ? -1 : result;

   856 }

   857 

   858 /* Return (new reference to) Py_True or Py_False. */

   859 static PyObject *

   860 convert_3way_to_object(int op, int c)

   861 {

   862 	PyObject *result;

   863 	switch (op) {

   864 	case Py_LT: c = c <  0; break;

   865 	case Py_LE: c = c <= 0; break;

   866 	case Py_EQ: c = c == 0; break;

   867 	case Py_NE: c = c != 0; break;

   868 	case Py_GT: c = c >  0; break;

   869 	case Py_GE: c = c >= 0; break;

   870 	}

   871 	result = c ? Py_True : Py_False;

   872 	Py_INCREF(result);

   873 	return result;

   874 }

   875 

   876 /* We want a rich comparison but don't have one.  Try a 3-way cmp instead.

   877    Return

   878    NULL      if error

   879    Py_True   if v op w

   880    Py_False  if not (v op w)

   881 */

   882 static PyObject *

   883 try_3way_to_rich_compare(PyObject *v, PyObject *w, int op)

   884 {

   885 	int c;

   886 

   887 	c = try_3way_compare(v, w);

   888 	if (c >= 2) {

   889 

   890 		/* Py3K warning if types are not equal and comparison isn't == or !=  */

   891 		if (Py_Py3kWarningFlag &&

   892 		    v->ob_type != w->ob_type && op != Py_EQ && op != Py_NE &&

   893 		    PyErr_WarnEx(PyExc_DeprecationWarning,

   894 			       "comparing unequal types not supported "

   895 			       "in 3.x", 1) < 0) {

   896 			return NULL;

   897 		}

   898 

   899 		c = default_3way_compare(v, w);

   900 	}

   901 	if (c <= -2)

   902 		return NULL;

   903 	return convert_3way_to_object(op, c);

   904 }

   905 

   906 /* Do rich comparison on v and w.  Return

   907    NULL      if error

   908    Else a new reference to an object other than Py_NotImplemented, usually(?):

   909    Py_True   if v op w

   910    Py_False  if not (v op w)

   911 */

   912 static PyObject *

   913 do_richcmp(PyObject *v, PyObject *w, int op)

   914 {

   915 	PyObject *res;

   916 

   917 	res = try_rich_compare(v, w, op);

   918 	if (res != Py_NotImplemented)

   919 		return res;

   920 	Py_DECREF(res);

   921 

   922 	return try_3way_to_rich_compare(v, w, op);

   923 }

   924 

   925 /* Return:

   926    NULL for exception;

   927    some object not equal to NotImplemented if it is implemented

   928      (this latter object may not be a Boolean).

   929 */

   930 PyObject *

   931 PyObject_RichCompare(PyObject *v, PyObject *w, int op)

   932 {

   933 	PyObject *res;

   934 

   935 	assert(Py_LT <= op && op <= Py_GE);

   936 	if (Py_EnterRecursiveCall(" in cmp"))

   937 		return NULL;

   938 

   939 	/* If the types are equal, and not old-style instances, try to

   940 	   get out cheap (don't bother with coercions etc.). */

   941 	if (v->ob_type == w->ob_type && !PyInstance_Check(v)) {

   942 		cmpfunc fcmp;

   943 		richcmpfunc frich = RICHCOMPARE(v->ob_type);

   944 		/* If the type has richcmp, try it first.  try_rich_compare

   945 		   tries it two-sided, which is not needed since we've a

   946 		   single type only. */

   947 		if (frich != NULL) {

   948 			res = (*frich)(v, w, op);

   949 			if (res != Py_NotImplemented)

   950 				goto Done;

   951 			Py_DECREF(res);

   952 		}

   953 		/* No richcmp, or this particular richmp not implemented.

   954 		   Try 3-way cmp. */

   955 		fcmp = v->ob_type->tp_compare;

   956 		if (fcmp != NULL) {

   957 			int c = (*fcmp)(v, w);

   958 			c = adjust_tp_compare(c);

   959 			if (c == -2) {

   960 				res = NULL;

   961 				goto Done;

   962 			}

   963 			res = convert_3way_to_object(op, c);

   964 			goto Done;

   965 		}

   966 	}

   967 

   968 	/* Fast path not taken, or couldn't deliver a useful result. */

   969 	res = do_richcmp(v, w, op);

   970 Done:

   971 	Py_LeaveRecursiveCall();

   972 	return res;

   973 }

   974 

   975 /* Return -1 if error; 1 if v op w; 0 if not (v op w). */

   976 int

   977 PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)

   978 {

   979 	PyObject *res;

   980 	int ok;

   981 

   982 	/* Quick result when objects are the same.

   983 	   Guarantees that identity implies equality. */

   984 	if (v == w) {

   985 		if (op == Py_EQ)

   986 			return 1;

   987 		else if (op == Py_NE)

   988 			return 0;

   989 	}

   990 

   991 	res = PyObject_RichCompare(v, w, op);

   992 	if (res == NULL)

   993 		return -1;

   994 	if (PyBool_Check(res))

   995 		ok = (res == Py_True);

   996 	else

   997 		ok = PyObject_IsTrue(res);

   998 	Py_DECREF(res);

   999 	return ok;

  1000 }

  1001 

  1002 /* Set of hash utility functions to help maintaining the invariant that

  1003 	if a==b then hash(a)==hash(b)

  1004 

  1005    All the utility functions (_Py_Hash*()) return "-1" to signify an error.

  1006 */

  1007 

  1008 long

  1009 _Py_HashDouble(double v)

  1010 {

  1011 	double intpart, fractpart;

  1012 	int expo;

  1013 	long hipart;

  1014 	long x;		/* the final hash value */

  1015 	/* This is designed so that Python numbers of different types

  1016 	 * that compare equal hash to the same value; otherwise comparisons

  1017 	 * of mapping keys will turn out weird.

  1018 	 */

  1019 

  1020 	fractpart = modf(v, &intpart);

  1021 	if (fractpart == 0.0) {

  1022 		/* This must return the same hash as an equal int or long. */

  1023 		if (intpart > LONG_MAX || -intpart > LONG_MAX) {

  1024 			/* Convert to long and use its hash. */

  1025 			PyObject *plong;	/* converted to Python long */

  1026 			if (Py_IS_INFINITY(intpart))

  1027 				/* can't convert to long int -- arbitrary */

  1028 				v = v < 0 ? -271828.0 : 314159.0;

  1029 			plong = PyLong_FromDouble(v);

  1030 			if (plong == NULL)

  1031 				return -1;

  1032 			x = PyObject_Hash(plong);

  1033 			Py_DECREF(plong);

  1034 			return x;

  1035 		}

  1036 		/* Fits in a C long == a Python int, so is its own hash. */

  1037 		x = (long)intpart;

  1038 		if (x == -1)

  1039 			x = -2;

  1040 		return x;

  1041 	}

  1042 	/* The fractional part is non-zero, so we don't have to worry about

  1043 	 * making this match the hash of some other type.

  1044 	 * Use frexp to get at the bits in the double.

  1045 	 * Since the VAX D double format has 56 mantissa bits, which is the

  1046 	 * most of any double format in use, each of these parts may have as

  1047 	 * many as (but no more than) 56 significant bits.

  1048 	 * So, assuming sizeof(long) >= 4, each part can be broken into two

  1049 	 * longs; frexp and multiplication are used to do that.

  1050 	 * Also, since the Cray double format has 15 exponent bits, which is

  1051 	 * the most of any double format in use, shifting the exponent field

  1052 	 * left by 15 won't overflow a long (again assuming sizeof(long) >= 4).

  1053 	 */

  1054 	v = frexp(v, &expo);

  1055 	v *= 2147483648.0;	/* 2**31 */

  1056 	hipart = (long)v;	/* take the top 32 bits */

  1057 	v = (v - (double)hipart) * 2147483648.0; /* get the next 32 bits */

  1058 	x = hipart + (long)v + (expo << 15);

  1059 	if (x == -1)

  1060 		x = -2;

  1061 	return x;

  1062 }

  1063 

  1064 long

  1065 _Py_HashPointer(void *p)

  1066 {

  1067 #if SIZEOF_LONG >= SIZEOF_VOID_P

  1068 	return (long)p;

  1069 #else

  1070 	/* convert to a Python long and hash that */

  1071 	PyObject* longobj;

  1072 	long x;

  1073 

  1074 	if ((longobj = PyLong_FromVoidPtr(p)) == NULL) {

  1075 		x = -1;

  1076 		goto finally;

  1077 	}

  1078 	x = PyObject_Hash(longobj);

  1079 

  1080 finally:

  1081 	Py_XDECREF(longobj);

  1082 	return x;

  1083 #endif

  1084 }

  1085 

  1086 long

  1087 PyObject_HashNotImplemented(PyObject *self)

  1088 {

  1089 	PyErr_Format(PyExc_TypeError, "unhashable type: '%.200s'",

  1090 		     self->ob_type->tp_name);

  1091 	return -1;

  1092 }

  1093 

  1094 long

  1095 PyObject_Hash(PyObject *v)

  1096 {

  1097 	PyTypeObject *tp = v->ob_type;

  1098 	if (tp->tp_hash != NULL)

  1099 		return (*tp->tp_hash)(v);

  1100 	if (tp->tp_compare == NULL && RICHCOMPARE(tp) == NULL) {

  1101 		return _Py_HashPointer(v); /* Use address as hash value */

  1102 	}

  1103 	/* If there's a cmp but no hash defined, the object can't be hashed */

  1104 	return PyObject_HashNotImplemented(v);

  1105 }

  1106 

  1107 PyObject *

  1108 PyObject_GetAttrString(PyObject *v, const char *name)

  1109 {

  1110 	PyObject *w, *res;

  1111 

  1112 	if (Py_TYPE(v)->tp_getattr != NULL)

  1113 		return (*Py_TYPE(v)->tp_getattr)(v, (char*)name);

  1114 	w = PyString_InternFromString(name);

  1115 	if (w == NULL)

  1116 		return NULL;

  1117 	res = PyObject_GetAttr(v, w);

  1118 	Py_XDECREF(w);

  1119 	return res;

  1120 }

  1121 

  1122 int

  1123 PyObject_HasAttrString(PyObject *v, const char *name)

  1124 {

  1125 	PyObject *res = PyObject_GetAttrString(v, name);

  1126 	if (res != NULL) {

  1127 		Py_DECREF(res);

  1128 		return 1;

  1129 	}

  1130 	PyErr_Clear();

  1131 	return 0;

  1132 }

  1133 

  1134 int

  1135 PyObject_SetAttrString(PyObject *v, const char *name, PyObject *w)