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/Lib/test/test_unicode.py b/Lib/test/test_unicode.py
index ef6a722..26a57cc 100644
--- a/Lib/test/test_unicode.py
+++ b/Lib/test/test_unicode.py
@@ -825,6 +825,268 @@
             return
         self.assertRaises(OverflowError, u't\tt\t'.expandtabs, sys.maxint)
 
+    def test__format__(self):
+        def test(value, format, expected):
+            # test both with and without the trailing 's'
+            self.assertEqual(value.__format__(format), expected)
+            self.assertEqual(value.__format__(format + u's'), expected)
+
+        test(u'', u'', u'')
+        test(u'abc', u'', u'abc')
+        test(u'abc', u'.3', u'abc')
+        test(u'ab', u'.3', u'ab')
+        test(u'abcdef', u'.3', u'abc')
+        test(u'abcdef', u'.0', u'')
+        test(u'abc', u'3.3', u'abc')
+        test(u'abc', u'2.3', u'abc')
+        test(u'abc', u'2.2', u'ab')
+        test(u'abc', u'3.2', u'ab ')
+        test(u'result', u'x<0', u'result')
+        test(u'result', u'x<5', u'result')
+        test(u'result', u'x<6', u'result')
+        test(u'result', u'x<7', u'resultx')
+        test(u'result', u'x<8', u'resultxx')
+        test(u'result', u' <7', u'result ')
+        test(u'result', u'<7', u'result ')
+        test(u'result', u'>7', u' result')
+        test(u'result', u'>8', u'  result')
+        test(u'result', u'^8', u' result ')
+        test(u'result', u'^9', u' result  ')
+        test(u'result', u'^10', u'  result  ')
+        test(u'a', u'10000', u'a' + u' ' * 9999)
+        test(u'', u'10000', u' ' * 10000)
+        test(u'', u'10000000', u' ' * 10000000)
+
+        # test mixing unicode and str
+        self.assertEqual(u'abc'.__format__('s'), u'abc')
+        self.assertEqual(u'abc'.__format__('->10s'), u'-------abc')
+
+    def test_format(self):
+        self.assertEqual(u''.format(), u'')
+        self.assertEqual(u'a'.format(), u'a')
+        self.assertEqual(u'ab'.format(), u'ab')
+        self.assertEqual(u'a{{'.format(), u'a{')
+        self.assertEqual(u'a}}'.format(), u'a}')
+        self.assertEqual(u'{{b'.format(), u'{b')
+        self.assertEqual(u'}}b'.format(), u'}b')
+        self.assertEqual(u'a{{b'.format(), u'a{b')
+
+        # examples from the PEP:
+        import datetime
+        self.assertEqual(u"My name is {0}".format(u'Fred'), u"My name is Fred")
+        self.assertEqual(u"My name is {0[name]}".format(dict(name=u'Fred')),
+                         u"My name is Fred")
+        self.assertEqual(u"My name is {0} :-{{}}".format(u'Fred'),
+                         u"My name is Fred :-{}")
+
+        # datetime.__format__ doesn't work with unicode
+        #d = datetime.date(2007, 8, 18)
+        #self.assertEqual("The year is {0.year}".format(d),
+        #                 "The year is 2007")
+
+        # classes we'll use for testing
+        class C:
+            def __init__(self, x=100):
+                self._x = x
+            def __format__(self, spec):
+                return spec
+
+        class D:
+            def __init__(self, x):
+                self.x = x
+            def __format__(self, spec):
+                return str(self.x)
+
+        # class with __str__, but no __format__
+        class E:
+            def __init__(self, x):
+                self.x = x
+            def __str__(self):
+                return u'E(' + self.x + u')'
+
+        # class with __repr__, but no __format__ or __str__
+        class F:
+            def __init__(self, x):
+                self.x = x
+            def __repr__(self):
+                return u'F(' + self.x + u')'
+
+        # class with __format__ that forwards to string, for some format_spec's
+        class G:
+            def __init__(self, x):
+                self.x = x
+            def __str__(self):
+                return u"string is " + self.x
+            def __format__(self, format_spec):
+                if format_spec == 'd':
+                    return u'G(' + self.x + u')'
+                return object.__format__(self, format_spec)
+
+        # class that returns a bad type from __format__
+        class H:
+            def __format__(self, format_spec):
+                return 1.0
+
+        class I(datetime.date):
+            def __format__(self, format_spec):
+                return self.strftime(format_spec)
+
+        class J(int):
+            def __format__(self, format_spec):
+                return int.__format__(self * 2, format_spec)
+
+
+        self.assertEqual(u''.format(), u'')
+        self.assertEqual(u'abc'.format(), u'abc')
+        self.assertEqual(u'{0}'.format(u'abc'), u'abc')
+        self.assertEqual(u'{0:}'.format(u'abc'), u'abc')
+        self.assertEqual(u'X{0}'.format(u'abc'), u'Xabc')
+        self.assertEqual(u'{0}X'.format(u'abc'), u'abcX')
+        self.assertEqual(u'X{0}Y'.format(u'abc'), u'XabcY')
+        self.assertEqual(u'{1}'.format(1, u'abc'), u'abc')
+        self.assertEqual(u'X{1}'.format(1, u'abc'), u'Xabc')
+        self.assertEqual(u'{1}X'.format(1, u'abc'), u'abcX')
+        self.assertEqual(u'X{1}Y'.format(1, u'abc'), u'XabcY')
+        self.assertEqual(u'{0}'.format(-15), u'-15')
+        self.assertEqual(u'{0}{1}'.format(-15, u'abc'), u'-15abc')
+        self.assertEqual(u'{0}X{1}'.format(-15, u'abc'), u'-15Xabc')
+        self.assertEqual(u'{{'.format(), u'{')
+        self.assertEqual(u'}}'.format(), u'}')
+        self.assertEqual(u'{{}}'.format(), u'{}')
+        self.assertEqual(u'{{x}}'.format(), u'{x}')
+        self.assertEqual(u'{{{0}}}'.format(123), u'{123}')
+        self.assertEqual(u'{{{{0}}}}'.format(), u'{{0}}')
+        self.assertEqual(u'}}{{'.format(), u'}{')
+        self.assertEqual(u'}}x{{'.format(), u'}x{')
+
+        # weird field names
+        self.assertEqual(u"{0[foo-bar]}".format({u'foo-bar':u'baz'}), u'baz')
+        self.assertEqual(u"{0[foo bar]}".format({u'foo bar':u'baz'}), u'baz')
+        self.assertEqual(u"{0[ ]}".format({u' ':3}), u'3')
+
+        self.assertEqual(u'{foo._x}'.format(foo=C(20)), u'20')
+        self.assertEqual(u'{1}{0}'.format(D(10), D(20)), u'2010')
+        self.assertEqual(u'{0._x.x}'.format(C(D(u'abc'))), u'abc')
+        self.assertEqual(u'{0[0]}'.format([u'abc', u'def']), u'abc')
+        self.assertEqual(u'{0[1]}'.format([u'abc', u'def']), u'def')
+        self.assertEqual(u'{0[1][0]}'.format([u'abc', [u'def']]), u'def')
+        self.assertEqual(u'{0[1][0].x}'.format(['abc', [D(u'def')]]), u'def')
+
+        # strings
+        self.assertEqual(u'{0:.3s}'.format(u'abc'), u'abc')
+        self.assertEqual(u'{0:.3s}'.format(u'ab'), u'ab')
+        self.assertEqual(u'{0:.3s}'.format(u'abcdef'), u'abc')
+        self.assertEqual(u'{0:.0s}'.format(u'abcdef'), u'')
+        self.assertEqual(u'{0:3.3s}'.format(u'abc'), u'abc')
+        self.assertEqual(u'{0:2.3s}'.format(u'abc'), u'abc')
+        self.assertEqual(u'{0:2.2s}'.format(u'abc'), u'ab')
+        self.assertEqual(u'{0:3.2s}'.format(u'abc'), u'ab ')
+        self.assertEqual(u'{0:x<0s}'.format(u'result'), u'result')
+        self.assertEqual(u'{0:x<5s}'.format(u'result'), u'result')
+        self.assertEqual(u'{0:x<6s}'.format(u'result'), u'result')
+        self.assertEqual(u'{0:x<7s}'.format(u'result'), u'resultx')
+        self.assertEqual(u'{0:x<8s}'.format(u'result'), u'resultxx')
+        self.assertEqual(u'{0: <7s}'.format(u'result'), u'result ')
+        self.assertEqual(u'{0:<7s}'.format(u'result'), u'result ')
+        self.assertEqual(u'{0:>7s}'.format(u'result'), u' result')
+        self.assertEqual(u'{0:>8s}'.format(u'result'), u'  result')
+        self.assertEqual(u'{0:^8s}'.format(u'result'), u' result ')
+        self.assertEqual(u'{0:^9s}'.format(u'result'), u' result  ')
+        self.assertEqual(u'{0:^10s}'.format(u'result'), u'  result  ')
+        self.assertEqual(u'{0:10000}'.format(u'a'), u'a' + u' ' * 9999)
+        self.assertEqual(u'{0:10000}'.format(u''), u' ' * 10000)
+        self.assertEqual(u'{0:10000000}'.format(u''), u' ' * 10000000)
+
+        # format specifiers for user defined type
+        self.assertEqual(u'{0:abc}'.format(C()), u'abc')
+
+        # !r and !s coersions
+        self.assertEqual(u'{0!s}'.format(u'Hello'), u'Hello')
+        self.assertEqual(u'{0!s:}'.format(u'Hello'), u'Hello')
+        self.assertEqual(u'{0!s:15}'.format(u'Hello'), u'Hello          ')
+        self.assertEqual(u'{0!s:15s}'.format(u'Hello'), u'Hello          ')
+        self.assertEqual(u'{0!r}'.format(u'Hello'), u"u'Hello'")
+        self.assertEqual(u'{0!r:}'.format(u'Hello'), u"u'Hello'")
+        self.assertEqual(u'{0!r}'.format(F(u'Hello')), u'F(Hello)')
+
+        # test fallback to object.__format__
+        self.assertEqual(u'{0}'.format({}), u'{}')
+        self.assertEqual(u'{0}'.format([]), u'[]')
+        self.assertEqual(u'{0}'.format([1]), u'[1]')
+        self.assertEqual(u'{0}'.format(E(u'data')), u'E(data)')
+        self.assertEqual(u'{0:^10}'.format(E(u'data')), u' E(data)  ')
+        self.assertEqual(u'{0:^10s}'.format(E(u'data')), u' E(data)  ')
+        self.assertEqual(u'{0:d}'.format(G(u'data')), u'G(data)')
+        self.assertEqual(u'{0:>15s}'.format(G(u'data')), u' string is data')
+        self.assertEqual(u'{0!s}'.format(G(u'data')), u'string is data')
+
+        self.assertEqual("{0:date: %Y-%m-%d}".format(I(year=2007,
+                                                       month=8,
+                                                       day=27)),
+                         "date: 2007-08-27")
+
+        # test deriving from a builtin type and overriding __format__
+        self.assertEqual("{0}".format(J(10)), "20")
+
+
+        # string format specifiers
+        self.assertEqual('{0:}'.format('a'), 'a')
+
+        # computed format specifiers
+        self.assertEqual("{0:.{1}}".format('hello world', 5), 'hello')
+        self.assertEqual("{0:.{1}s}".format('hello world', 5), 'hello')
+        self.assertEqual("{0:.{precision}s}".format('hello world', precision=5), 'hello')
+        self.assertEqual("{0:{width}.{precision}s}".format('hello world', width=10, precision=5), 'hello     ')
+        self.assertEqual("{0:{width}.{precision}s}".format('hello world', width='10', precision='5'), 'hello     ')
+
+        # test various errors
+        self.assertRaises(ValueError, '{'.format)
+        self.assertRaises(ValueError, '}'.format)
+        self.assertRaises(ValueError, 'a{'.format)
+        self.assertRaises(ValueError, 'a}'.format)
+        self.assertRaises(ValueError, '{a'.format)
+        self.assertRaises(ValueError, '}a'.format)
+        self.assertRaises(IndexError, '{0}'.format)
+        self.assertRaises(IndexError, '{1}'.format, 'abc')
+        self.assertRaises(KeyError,   '{x}'.format)
+        self.assertRaises(ValueError, "}{".format)
+        self.assertRaises(ValueError, "{".format)
+        self.assertRaises(ValueError, "}".format)
+        self.assertRaises(ValueError, "abc{0:{}".format)
+        self.assertRaises(ValueError, "{0".format)
+        self.assertRaises(IndexError, "{0.}".format)
+        self.assertRaises(ValueError, "{0.}".format, 0)
+        self.assertRaises(IndexError, "{0[}".format)
+        self.assertRaises(ValueError, "{0[}".format, [])
+        self.assertRaises(KeyError,   "{0]}".format)
+        self.assertRaises(ValueError, "{0.[]}".format, 0)
+        self.assertRaises(ValueError, "{0..foo}".format, 0)
+        self.assertRaises(ValueError, "{0[0}".format, 0)
+        self.assertRaises(ValueError, "{0[0:foo}".format, 0)
+        self.assertRaises(KeyError,   "{c]}".format)
+        self.assertRaises(ValueError, "{{ {{{0}}".format, 0)
+        self.assertRaises(ValueError, "{0}}".format, 0)
+        self.assertRaises(KeyError,   "{foo}".format, bar=3)
+        self.assertRaises(ValueError, "{0!x}".format, 3)
+        self.assertRaises(ValueError, "{0!}".format, 0)
+        self.assertRaises(ValueError, "{0!rs}".format, 0)
+        self.assertRaises(ValueError, "{!}".format)
+        self.assertRaises(ValueError, "{:}".format)
+        self.assertRaises(ValueError, "{:s}".format)
+        self.assertRaises(ValueError, "{}".format)
+
+        # can't have a replacement on the field name portion
+        self.assertRaises(TypeError, '{0[{1}]}'.format, 'abcdefg', 4)
+
+        # exceed maximum recursion depth
+        self.assertRaises(ValueError, "{0:{1:{2}}}".format, 'abc', 's', '')
+        self.assertRaises(ValueError, "{0:{1:{2:{3:{4:{5:{6}}}}}}}".format,
+                          0, 1, 2, 3, 4, 5, 6, 7)
+
+        # string format spec errors
+        self.assertRaises(ValueError, "{0:-s}".format, '')
+        self.assertRaises(ValueError, format, "", "-")
+        self.assertRaises(ValueError, "{0:=s}".format, '')
 
 def test_main():
     test_support.run_unittest(__name__)