Backport of PEP 3101, Advanced String Formatting, from py3k.

Highlights:
 - Adding PyObject_Format.
 - Adding string.Format class.
 - Adding __format__ for str, unicode, int, long, float, datetime.
 - Adding builtin format.
 - Adding ''.format and u''.format.
 - str/unicode fixups for formatters.

The files in Objects/stringlib that implement PEP 3101 (stringdefs.h,
unicodedefs.h, formatter.h, string_format.h) are identical in trunk
and py3k.  Any changes from here on should be made to trunk, and
changes will propogate to py3k).
diff --git a/Objects/abstract.c b/Objects/abstract.c
index a377e76..071cbdc 100644
--- a/Objects/abstract.c
+++ b/Objects/abstract.c
@@ -348,6 +348,138 @@
 	return 0;
 }
 
+PyObject *
+PyObject_Format(PyObject* obj, PyObject *format_spec)
+{
+	static PyObject * str__format__ = NULL;
+	PyObject *empty = NULL;
+	PyObject *result = NULL;
+	int spec_is_unicode;
+	int result_is_unicode;
+
+	/* Initialize cached value */
+	if (str__format__ == NULL) {
+		/* Initialize static variable needed by _PyType_Lookup */
+		str__format__ = PyString_InternFromString("__format__");
+		if (str__format__ == NULL)
+			goto done;
+	}
+
+	/* If no format_spec is provided, use an empty string */
+	if (format_spec == NULL) {
+		empty = PyString_FromStringAndSize(NULL, 0);
+		format_spec = empty;
+	}
+
+	/* Check the format_spec type, and make sure it's str or unicode */
+	if (PyUnicode_Check(format_spec))
+		spec_is_unicode = 1;
+	else if (PyString_Check(format_spec))
+		spec_is_unicode = 0;
+	else {
+		PyErr_Format(PyExc_TypeError,
+			     "format expects arg 2 to be string "
+			     "or unicode, not %.100s", Py_TYPE(format_spec)->tp_name);
+		goto done;
+	}
+
+	/* Make sure the type is initialized.  float gets initialized late */
+	if (Py_TYPE(obj)->tp_dict == NULL)
+		if (PyType_Ready(Py_TYPE(obj)) < 0)
+			goto done;
+
+	/* Check for a __format__ method and call it. */
+	if (PyInstance_Check(obj)) {
+		/* We're an instance of a classic class */
+		PyObject *bound_method = PyObject_GetAttr(obj,
+							  str__format__);
+		if (bound_method != NULL) {
+			result = PyObject_CallFunctionObjArgs(bound_method,
+							      format_spec,
+							      NULL);
+			Py_DECREF(bound_method);
+		} else {
+			PyObject *self_as_str;
+			PyObject *format_method;
+
+			PyErr_Clear();
+			/* Per the PEP, convert to str (or unicode,
+			   depending on the type of the format
+			   specifier).  For new-style classes, this
+			   logic is done by object.__format__(). */
+			if (spec_is_unicode)
+				self_as_str = PyObject_Unicode(obj);
+			else
+				self_as_str = PyObject_Str(obj);
+			if (self_as_str == NULL)
+				goto done;
+
+			/* Then call str.__format__ on that result */
+			format_method = PyObject_GetAttr(self_as_str,
+							 str__format__);
+			if (format_method == NULL) {
+				Py_DECREF(self_as_str);
+				goto done;
+			}
+                        result = PyObject_CallFunctionObjArgs(format_method,
+							      format_spec,
+							      NULL);
+			Py_DECREF(self_as_str);
+			Py_DECREF(format_method);
+			if (result == NULL)
+				goto done;
+                }
+	} else {
+		/* Not an instance of a classic class, use the code
+		   from py3k */
+
+		/* Find the (unbound!) __format__ method (a borrowed
+		   reference) */
+		PyObject *method = _PyType_Lookup(Py_TYPE(obj),
+						  str__format__);
+		if (method == NULL) {
+			PyErr_Format(PyExc_TypeError,
+				     "Type %.100s doesn't define __format__",
+				     Py_TYPE(obj)->tp_name);
+			goto done;
+		}
+		/* And call it, binding it to the value */
+		result = PyObject_CallFunctionObjArgs(method, obj,
+						      format_spec, NULL);
+	}
+
+	if (result == NULL)
+		goto done;
+
+	/* Check the result type, and make sure it's str or unicode */
+	if (PyUnicode_Check(result))
+		result_is_unicode = 1;
+	else if (PyString_Check(result))
+		result_is_unicode = 0;
+	else {
+		PyErr_Format(PyExc_TypeError,
+			     "%.100s.__format__ must return string or "
+			     "unicode, not %.100s", Py_TYPE(obj)->tp_name,
+			     Py_TYPE(result)->tp_name);
+		Py_DECREF(result);
+		result = NULL;
+		goto done;
+	}
+
+	/* Convert to unicode, if needed.  Required if spec is unicode
+	   and result is str */
+	if (spec_is_unicode && !result_is_unicode) {
+		PyObject *tmp = PyObject_Unicode(result);
+		/* This logic works whether or not tmp is NULL */
+		Py_DECREF(result);
+		result = tmp;
+	}
+
+done:
+	Py_XDECREF(empty);
+	return result;
+}
+
 /* Operations on numbers */
 
 int