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_string.py b/Lib/test/test_string.py
index 9b22333..5c20a2b 100644
--- a/Lib/test/test_string.py
+++ b/Lib/test/test_string.py
@@ -106,6 +106,92 @@
         self.assertEqual(string.capwords('ABC-DEF-GHI', '-'), 'Abc-Def-Ghi')
         self.assertEqual(string.capwords('ABC-def DEF-ghi GHI'), 'Abc-def Def-ghi Ghi')
 
+    def test_formatter(self):
+        fmt = string.Formatter()
+        self.assertEqual(fmt.format("foo"), "foo")
+
+        self.assertEqual(fmt.format("foo{0}", "bar"), "foobar")
+        self.assertEqual(fmt.format("foo{1}{0}-{1}", "bar", 6), "foo6bar-6")
+        self.assertEqual(fmt.format("-{arg!r}-", arg='test'), "-'test'-")
+
+        # override get_value ############################################
+        class NamespaceFormatter(string.Formatter):
+            def __init__(self, namespace={}):
+                string.Formatter.__init__(self)
+                self.namespace = namespace
+
+            def get_value(self, key, args, kwds):
+                if isinstance(key, str):
+                    try:
+                        # Check explicitly passed arguments first
+                        return kwds[key]
+                    except KeyError:
+                        return self.namespace[key]
+                else:
+                    string.Formatter.get_value(key, args, kwds)
+
+        fmt = NamespaceFormatter({'greeting':'hello'})
+        self.assertEqual(fmt.format("{greeting}, world!"), 'hello, world!')
+
+
+        # override format_field #########################################
+        class CallFormatter(string.Formatter):
+            def format_field(self, value, format_spec):
+                return format(value(), format_spec)
+
+        fmt = CallFormatter()
+        self.assertEqual(fmt.format('*{0}*', lambda : 'result'), '*result*')
+
+
+        # override convert_field ########################################
+        class XFormatter(string.Formatter):
+            def convert_field(self, value, conversion):
+                if conversion == 'x':
+                    return None
+                return super(XFormatter, self).convert_field(value, conversion)
+
+        fmt = XFormatter()
+        self.assertEqual(fmt.format("{0!r}:{0!x}", 'foo', 'foo'), "'foo':None")
+
+
+        # override parse ################################################
+        class BarFormatter(string.Formatter):
+            # returns an iterable that contains tuples of the form:
+            # (literal_text, field_name, format_spec, conversion)
+            def parse(self, format_string):
+                for field in format_string.split('|'):
+                    if field[0] == '+':
+                        # it's markup
+                        field_name, _, format_spec = field[1:].partition(':')
+                        yield '', field_name, format_spec, None
+                    else:
+                        yield field, None, None, None
+
+        fmt = BarFormatter()
+        self.assertEqual(fmt.format('*|+0:^10s|*', 'foo'), '*   foo    *')
+
+        # test all parameters used
+        class CheckAllUsedFormatter(string.Formatter):
+            def check_unused_args(self, used_args, args, kwargs):
+                # Track which arguments actuallly got used
+                unused_args = set(kwargs.keys())
+                unused_args.update(range(0, len(args)))
+
+                for arg in used_args:
+                    unused_args.remove(arg)
+
+                if unused_args:
+                    raise ValueError("unused arguments")
+
+        fmt = CheckAllUsedFormatter()
+        self.assertEqual(fmt.format("{0}", 10), "10")
+        self.assertEqual(fmt.format("{0}{i}", 10, i=100), "10100")
+        self.assertEqual(fmt.format("{0}{i}{1}", 10, 20, i=100), "1010020")
+        self.assertRaises(ValueError, fmt.format, "{0}{i}{1}", 10, 20, i=100, j=0)
+        self.assertRaises(ValueError, fmt.format, "{0}", 10, 20)
+        self.assertRaises(ValueError, fmt.format, "{0}", 10, 20, i=100)
+        self.assertRaises(ValueError, fmt.format, "{i}", 10, 20, i=100)
+
 class BytesAliasTest(unittest.TestCase):
 
     def test_builtin(self):