String annotations [PEP 563] (#4390)

* Document `from __future__ import annotations`
* Provide plumbing and tests for `from __future__ import annotations`
* Implement unparsing the AST back to string form

This is required for PEP 563 and as such only implements a part of the
unparsing process that covers expressions.
diff --git a/Lib/__future__.py b/Lib/__future__.py
index 63b2be3..ce8bed7 100644
--- a/Lib/__future__.py
+++ b/Lib/__future__.py
@@ -57,13 +57,14 @@
     "unicode_literals",
     "barry_as_FLUFL",
     "generator_stop",
+    "annotations",
 ]
 
 __all__ = ["all_feature_names"] + all_feature_names
 
-# The CO_xxx symbols are defined here under the same names used by
-# compile.h, so that an editor search will find them here.  However,
-# they're not exported in __all__, because they don't really belong to
+# The CO_xxx symbols are defined here under the same names defined in
+# code.h and used by compile.h, so that an editor search will find them here.
+# However, they're not exported in __all__, because they don't really belong to
 # this module.
 CO_NESTED            = 0x0010   # nested_scopes
 CO_GENERATOR_ALLOWED = 0        # generators (obsolete, was 0x1000)
@@ -74,6 +75,7 @@
 CO_FUTURE_UNICODE_LITERALS = 0x20000 # unicode string literals
 CO_FUTURE_BARRY_AS_BDFL = 0x40000
 CO_FUTURE_GENERATOR_STOP  = 0x80000 # StopIteration becomes RuntimeError in generators
+CO_FUTURE_ANNOTATIONS     = 0x100000  # annotations become strings at runtime
 
 class _Feature:
     def __init__(self, optionalRelease, mandatoryRelease, compiler_flag):
@@ -132,9 +134,13 @@
                             CO_FUTURE_UNICODE_LITERALS)
 
 barry_as_FLUFL = _Feature((3, 1, 0, "alpha", 2),
-                         (3, 9, 0, "alpha", 0),
-                         CO_FUTURE_BARRY_AS_BDFL)
+                          (3, 9, 0, "alpha", 0),
+                          CO_FUTURE_BARRY_AS_BDFL)
 
 generator_stop = _Feature((3, 5, 0, "beta", 1),
-                         (3, 7, 0, "alpha", 0),
-                         CO_FUTURE_GENERATOR_STOP)
+                          (3, 7, 0, "alpha", 0),
+                          CO_FUTURE_GENERATOR_STOP)
+
+annotations = _Feature((3, 7, 0, "beta", 1),
+                       (4, 0, 0, "alpha", 0),
+                       CO_FUTURE_ANNOTATIONS)
diff --git a/Lib/test/test_future.py b/Lib/test/test_future.py
index 2f1c410..29c4632 100644
--- a/Lib/test/test_future.py
+++ b/Lib/test/test_future.py
@@ -1,7 +1,9 @@
 # Test various flavors of legal and illegal future statements
 
+from functools import partial
 import unittest
 from test import support
+from textwrap import dedent
 import os
 import re
 
@@ -102,6 +104,167 @@
         exec("from __future__ import unicode_literals; x = ''", {}, scope)
         self.assertIsInstance(scope["x"], str)
 
+class AnnotationsFutureTestCase(unittest.TestCase):
+    template = dedent(
+        """
+        from __future__ import annotations
+        def f() -> {ann}:
+            ...
+        def g(arg: {ann}) -> None:
+            ...
+        var: {ann}
+        var2: {ann} = None
+        """
+    )
+
+    def getActual(self, annotation):
+        scope = {}
+        exec(self.template.format(ann=annotation), {}, scope)
+        func_ret_ann = scope['f'].__annotations__['return']
+        func_arg_ann = scope['g'].__annotations__['arg']
+        var_ann1 = scope['__annotations__']['var']
+        var_ann2 = scope['__annotations__']['var2']
+        self.assertEqual(func_ret_ann, func_arg_ann)
+        self.assertEqual(func_ret_ann, var_ann1)
+        self.assertEqual(func_ret_ann, var_ann2)
+        return func_ret_ann
+
+    def assertAnnotationEqual(
+        self, annotation, expected=None, drop_parens=False, is_tuple=False,
+    ):
+        actual = self.getActual(annotation)
+        if expected is None:
+            expected = annotation if not is_tuple else annotation[1:-1]
+        if drop_parens:
+            self.assertNotEqual(actual, expected)
+            actual = actual.replace("(", "").replace(")", "")
+
+        self.assertEqual(actual, expected)
+
+    def test_annotations(self):
+        eq = self.assertAnnotationEqual
+        eq('...')
+        eq("'some_string'")
+        eq("b'\\xa3'")
+        eq('Name')
+        eq('None')
+        eq('True')
+        eq('False')
+        eq('1')
+        eq('1.0')
+        eq('1j')
+        eq('True or False')
+        eq('True or False or None')
+        eq('True and False')
+        eq('True and False and None')
+        eq('(Name1 and Name2) or Name3')
+        eq('Name1 or (Name2 and Name3)')
+        eq('(Name1 and Name2) or (Name3 and Name4)')
+        eq('Name1 or (Name2 and Name3) or Name4')
+        eq('v1 << 2')
+        eq('1 >> v2')
+        eq(r'1 % finished')
+        eq('((1 + v2) - (v3 * 4)) ^ (((5 ** v6) / 7) // 8)')
+        eq('not great')
+        eq('~great')
+        eq('+value')
+        eq('-1')
+        eq('(~int) and (not ((v1 ^ (123 + v2)) | True))')
+        eq('lambda arg: None')
+        eq('lambda a=True: a')
+        eq('lambda a, b, c=True: a')
+        eq("lambda a, b, c=True, *, d=(1 << v2), e='str': a")
+        eq("lambda a, b, c=True, *vararg, d=(v1 << 2), e='str', **kwargs: a + b")
+        eq('1 if True else 2')
+        eq('(str or None) if True else (str or bytes or None)')
+        eq('(str or None) if (1 if True else 2) else (str or bytes or None)')
+        eq("{'2.7': dead, '3.7': (long_live or die_hard)}")
+        eq("{'2.7': dead, '3.7': (long_live or die_hard), **{'3.6': verygood}}")
+        eq("{**a, **b, **c}")
+        eq("{'2.7', '3.6', '3.7', '3.8', '3.9', ('4.0' if gilectomy else '3.10')}")
+        eq("({'a': 'b'}, (True or False), (+value), 'string', b'bytes') or None")
+        eq("()")
+        eq("(1,)")
+        eq("(1, 2)")
+        eq("(1, 2, 3)")
+        eq("[]")
+        eq("[1, 2, 3, 4, 5, 6, 7, 8, 9, (10 or A), (11 or B), (12 or C)]")
+        eq("{i for i in (1, 2, 3)}")
+        eq("{(i ** 2) for i in (1, 2, 3)}")
+        eq("{(i ** 2) for i, _ in ((1, 'a'), (2, 'b'), (3, 'c'))}")
+        eq("{((i ** 2) + j) for i in (1, 2, 3) for j in (1, 2, 3)}")
+        eq("[i for i in (1, 2, 3)]")
+        eq("[(i ** 2) for i in (1, 2, 3)]")
+        eq("[(i ** 2) for i, _ in ((1, 'a'), (2, 'b'), (3, 'c'))]")
+        eq("[((i ** 2) + j) for i in (1, 2, 3) for j in (1, 2, 3)]")
+        eq(r"{i: 0 for i in (1, 2, 3)}")
+        eq("{i: j for i, j in ((1, 'a'), (2, 'b'), (3, 'c'))}")
+        eq("Python3 > Python2 > COBOL")
+        eq("Life is Life")
+        eq("call()")
+        eq("call(arg)")
+        eq("call(kwarg='hey')")
+        eq("call(arg, kwarg='hey')")
+        eq("call(arg, another, kwarg='hey', **kwargs)")
+        eq("lukasz.langa.pl")
+        eq("call.me(maybe)")
+        eq("1 .real")
+        eq("1.0 .real")
+        eq("....__class__")
+        eq("list[str]")
+        eq("dict[str, int]")
+        eq("tuple[str, ...]")
+        eq("tuple[str, int, float, dict[str, int]]")
+        eq("slice[0]")
+        eq("slice[0:1]")
+        eq("slice[0:1:2]")
+        eq("slice[:]")
+        eq("slice[:-1]")
+        eq("slice[1:]")
+        eq("slice[::-1]")
+        eq('(str or None) if (sys.version_info[0] > (3,)) else (str or bytes or None)')
+        eq("f'f-string without formatted values is just a string'")
+        eq("f'{{NOT a formatted value}}'")
+        eq("f'some f-string with {a} {few():.2f} {formatted.values!r}'")
+        eq('''f"{f'{nested} inner'} outer"''')
+        eq("f'space between opening braces: { {a for a in (1, 2, 3)}}'")
+
+    def test_annotations_inexact(self):
+        """Source formatting is not always preserved
+
+        This is due to reconstruction from AST.  We *need to* put the parens
+        in nested expressions because we don't know if the source code
+        had them in the first place or not.
+        """
+        eq = partial(self.assertAnnotationEqual, drop_parens=True)
+        eq('Name1 and Name2 or Name3')
+        eq('Name1 or Name2 and Name3')
+        eq('Name1 and Name2 or Name3 and Name4')
+        eq('Name1 or Name2 and Name3 or Name4')
+        eq('1 + v2 - v3 * 4 ^ v5 ** 6 / 7 // 8')
+        eq('~int and not v1 ^ 123 + v2 | True')
+        eq('str or None if True else str or bytes or None')
+        eq("{'2.7': dead, '3.7': long_live or die_hard}")
+        eq("{'2.7', '3.6', '3.7', '3.8', '3.9', '4.0' if gilectomy else '3.10'}")
+        eq("[1, 2, 3, 4, 5, 6, 7, 8, 9, 10 or A, 11 or B, 12 or C]")
+        # Consequently, we always drop unnecessary parens if they were given in
+        # the outer scope:
+        some_name = self.getActual("(SomeName)")
+        self.assertEqual(some_name, 'SomeName')
+        # Interestingly, in the case of tuples (and generator expressions) the
+        # parens are *required* by the Python syntax in the annotation context.
+        # But there's no point storing that detail in __annotations__ so we're
+        # fine with the parens-less form.
+        eq = partial(self.assertAnnotationEqual, is_tuple=True)
+        eq("(Good, Bad, Ugly)")
+        eq("(i for i in (1, 2, 3))")
+        eq("((i ** 2) for i in (1, 2, 3))")
+        eq("((i ** 2) for i, _ in ((1, 'a'), (2, 'b'), (3, 'c')))")
+        eq("(((i ** 2) + j) for i in (1, 2, 3) for j in (1, 2, 3))")
+        eq("(*starred)")
+        eq('(yield from outside_of_generator)')
+        eq('(yield)')
+        eq('(await some.complicated[0].call(with_args=(True or (1 is not 1))))')
 
 
 if __name__ == "__main__":