Closes issue #24773: Implement PEP 495 (Local Time Disambiguation).
diff --git a/Lib/test/datetimetester.py b/Lib/test/datetimetester.py
index 8fc0139..e0d23da 100644
--- a/Lib/test/datetimetester.py
+++ b/Lib/test/datetimetester.py
@@ -2,14 +2,22 @@
 
 See http://www.zope.org/Members/fdrake/DateTimeWiki/TestCases
 """
+from test.support import requires
+
+import itertools
+import bisect
 
 import copy
 import decimal
 import sys
+import os
 import pickle
 import random
+import struct
 import unittest
 
+from array import array
+
 from operator import lt, le, gt, ge, eq, ne, truediv, floordiv, mod
 
 from test import support
@@ -1592,6 +1600,10 @@
         self.assertEqual(t.isoformat(' '), "0002-03-02 00:00:00")
         # str is ISO format with the separator forced to a blank.
         self.assertEqual(str(t), "0002-03-02 00:00:00")
+        # ISO format with timezone
+        tz = FixedOffset(timedelta(seconds=16), 'XXX')
+        t = self.theclass(2, 3, 2, tzinfo=tz)
+        self.assertEqual(t.isoformat(), "0002-03-02T00:00:00+00:00:16")
 
     def test_format(self):
         dt = self.theclass(2007, 9, 10, 4, 5, 1, 123)
@@ -1711,6 +1723,9 @@
         self.assertRaises(ValueError, self.theclass,
                           2000, 1, 31, 23, 59, 59,
                           1000000)
+        # Positional fold:
+        self.assertRaises(TypeError, self.theclass,
+                          2000, 1, 31, 23, 59, 59, 0, None, 1)
 
     def test_hash_equality(self):
         d = self.theclass(2000, 12, 31, 23, 30, 17)
@@ -1894,16 +1909,20 @@
         t = self.theclass(1970, 1, 1, 1, 2, 3, 4)
         self.assertEqual(t.timestamp(),
                          18000.0 + 3600 + 2*60 + 3 + 4*1e-6)
-        # Missing hour may produce platform-dependent result
-        t = self.theclass(2012, 3, 11, 2, 30)
-        self.assertIn(self.theclass.fromtimestamp(t.timestamp()),
-                      [t - timedelta(hours=1), t + timedelta(hours=1)])
+        # Missing hour
+        t0 = self.theclass(2012, 3, 11, 2, 30)
+        t1 = t0.replace(fold=1)
+        self.assertEqual(self.theclass.fromtimestamp(t1.timestamp()),
+                         t0 - timedelta(hours=1))
+        self.assertEqual(self.theclass.fromtimestamp(t0.timestamp()),
+                         t1 + timedelta(hours=1))
         # Ambiguous hour defaults to DST
         t = self.theclass(2012, 11, 4, 1, 30)
         self.assertEqual(self.theclass.fromtimestamp(t.timestamp()), t)
 
         # Timestamp may raise an overflow error on some platforms
-        for t in [self.theclass(1,1,1), self.theclass(9999,12,12)]:
+        # XXX: Do we care to support the first and last year?
+        for t in [self.theclass(2,1,1), self.theclass(9998,12,12)]:
             try:
                 s = t.timestamp()
             except OverflowError:
@@ -1922,6 +1941,7 @@
         self.assertEqual(t.timestamp(),
                          18000 + 3600 + 2*60 + 3 + 4*1e-6)
 
+    @support.run_with_tz('MSK-03')  # Something east of Greenwich
     def test_microsecond_rounding(self):
         for fts in [self.theclass.fromtimestamp,
                     self.theclass.utcfromtimestamp]:
@@ -2127,6 +2147,7 @@
         self.assertRaises(ValueError, base.replace, year=2001)
 
     def test_astimezone(self):
+        return  # The rest is no longer applicable
         # Pretty boring!  The TZ test is more interesting here.  astimezone()
         # simply can't be applied to a naive object.
         dt = self.theclass.now()
@@ -2619,9 +2640,9 @@
         self.assertRaises(ValueError, t.utcoffset)
         self.assertRaises(ValueError, t.dst)
 
-        # Not a whole number of minutes.
+        # Not a whole number of seconds.
         class C7(tzinfo):
-            def utcoffset(self, dt): return timedelta(seconds=61)
+            def utcoffset(self, dt): return timedelta(microseconds=61)
             def dst(self, dt): return timedelta(microseconds=-81)
         t = cls(1, 1, 1, tzinfo=C7())
         self.assertRaises(ValueError, t.utcoffset)
@@ -3994,5 +4015,777 @@
         with self.assertRaises(TypeError):
             datetime(10, 10, 10, 10, 10, 10, 10.)
 
+#############################################################################
+# Local Time Disambiguation
+
+# An experimental reimplementation of fromutc that respects the "fold" flag.
+
+class tzinfo2(tzinfo):
+
+    def fromutc(self, dt):
+        "datetime in UTC -> datetime in local time."
+
+        if not isinstance(dt, datetime):
+            raise TypeError("fromutc() requires a datetime argument")
+        if dt.tzinfo is not self:
+            raise ValueError("dt.tzinfo is not self")
+        # Returned value satisfies
+        #          dt + ldt.utcoffset() = ldt
+        off0 = dt.replace(fold=0).utcoffset()
+        off1 = dt.replace(fold=1).utcoffset()
+        if off0 is None or off1 is None or dt.dst() is None:
+            raise ValueError
+        if off0 == off1:
+            ldt = dt + off0
+            off1 = ldt.utcoffset()
+            if off0 == off1:
+                return ldt
+        # Now, we discovered both possible offsets, so
+        # we can just try four possible solutions:
+        for off in [off0, off1]:
+            ldt = dt + off
+            if ldt.utcoffset() == off:
+                return ldt
+            ldt = ldt.replace(fold=1)
+            if ldt.utcoffset() == off:
+                return ldt
+
+        raise ValueError("No suitable local time found")
+
+# Reimplementing simplified US timezones to respect the "fold" flag:
+
+class USTimeZone2(tzinfo2):
+
+    def __init__(self, hours, reprname, stdname, dstname):
+        self.stdoffset = timedelta(hours=hours)
+        self.reprname = reprname
+        self.stdname = stdname
+        self.dstname = dstname
+
+    def __repr__(self):
+        return self.reprname
+
+    def tzname(self, dt):
+        if self.dst(dt):
+            return self.dstname
+        else:
+            return self.stdname
+
+    def utcoffset(self, dt):
+        return self.stdoffset + self.dst(dt)
+
+    def dst(self, dt):
+        if dt is None or dt.tzinfo is None:
+            # An exception instead may be sensible here, in one or more of
+            # the cases.
+            return ZERO
+        assert dt.tzinfo is self
+
+        # Find first Sunday in April.
+        start = first_sunday_on_or_after(DSTSTART.replace(year=dt.year))
+        assert start.weekday() == 6 and start.month == 4 and start.day <= 7
+
+        # Find last Sunday in October.
+        end = first_sunday_on_or_after(DSTEND.replace(year=dt.year))
+        assert end.weekday() == 6 and end.month == 10 and end.day >= 25
+
+        # Can't compare naive to aware objects, so strip the timezone from
+        # dt first.
+        dt = dt.replace(tzinfo=None)
+        if start + HOUR <= dt < end:
+            # DST is in effect.
+            return HOUR
+        elif end <= dt < end + HOUR:
+            # Fold (an ambiguous hour): use dt.fold to disambiguate.
+            return ZERO if dt.fold else HOUR
+        elif start <= dt < start + HOUR:
+            # Gap (a non-existent hour): reverse the fold rule.
+            return HOUR if dt.fold else ZERO
+        else:
+            # DST is off.
+            return ZERO
+
+Eastern2  = USTimeZone2(-5, "Eastern2",  "EST", "EDT")
+Central2  = USTimeZone2(-6, "Central2",  "CST", "CDT")
+Mountain2 = USTimeZone2(-7, "Mountain2", "MST", "MDT")
+Pacific2  = USTimeZone2(-8, "Pacific2",  "PST", "PDT")
+
+# Europe_Vilnius_1941 tzinfo implementation reproduces the following
+# 1941 transition from Olson's tzdist:
+#
+# Zone NAME           GMTOFF RULES  FORMAT [UNTIL]
+# ZoneEurope/Vilnius  1:00   -      CET    1940 Aug  3
+#                     3:00   -      MSK    1941 Jun 24
+#                     1:00   C-Eur  CE%sT  1944 Aug
+#
+# $ zdump -v Europe/Vilnius | grep 1941
+# Europe/Vilnius  Mon Jun 23 20:59:59 1941 UTC = Mon Jun 23 23:59:59 1941 MSK isdst=0 gmtoff=10800
+# Europe/Vilnius  Mon Jun 23 21:00:00 1941 UTC = Mon Jun 23 23:00:00 1941 CEST isdst=1 gmtoff=7200
+
+class Europe_Vilnius_1941(tzinfo):
+    def _utc_fold(self):
+        return [datetime(1941, 6, 23, 21, tzinfo=self),  # Mon Jun 23 21:00:00 1941 UTC
+                datetime(1941, 6, 23, 22, tzinfo=self)]  # Mon Jun 23 22:00:00 1941 UTC
+
+    def _loc_fold(self):
+        return [datetime(1941, 6, 23, 23, tzinfo=self),  # Mon Jun 23 23:00:00 1941 MSK / CEST
+                datetime(1941, 6, 24, 0, tzinfo=self)]   # Mon Jun 24 00:00:00 1941 CEST
+
+    def utcoffset(self, dt):
+        fold_start, fold_stop = self._loc_fold()
+        if dt < fold_start:
+            return 3 * HOUR
+        if dt < fold_stop:
+            return (2 if dt.fold else 3) * HOUR
+        # if dt >= fold_stop
+        return 2 * HOUR
+
+    def dst(self, dt):
+        fold_start, fold_stop = self._loc_fold()
+        if dt < fold_start:
+            return 0 * HOUR
+        if dt < fold_stop:
+            return (1 if dt.fold else 0) * HOUR
+        # if dt >= fold_stop
+        return 1 * HOUR
+
+    def tzname(self, dt):
+        fold_start, fold_stop = self._loc_fold()
+        if dt < fold_start:
+            return 'MSK'
+        if dt < fold_stop:
+            return ('MSK', 'CEST')[dt.fold]
+        # if dt >= fold_stop
+        return 'CEST'
+
+    def fromutc(self, dt):
+        assert dt.fold == 0
+        assert dt.tzinfo is self
+        if dt.year != 1941:
+            raise NotImplementedError
+        fold_start, fold_stop = self._utc_fold()
+        if dt < fold_start:
+            return dt + 3 * HOUR
+        if dt < fold_stop:
+            return (dt + 2 * HOUR).replace(fold=1)
+        # if dt >= fold_stop
+        return dt + 2 * HOUR
+
+
+class TestLocalTimeDisambiguation(unittest.TestCase):
+
+    def test_vilnius_1941_fromutc(self):
+        Vilnius = Europe_Vilnius_1941()
+
+        gdt = datetime(1941, 6, 23, 20, 59, 59, tzinfo=timezone.utc)
+        ldt = gdt.astimezone(Vilnius)
+        self.assertEqual(ldt.strftime("%c %Z%z"),
+                         'Mon Jun 23 23:59:59 1941 MSK+0300')
+        self.assertEqual(ldt.fold, 0)
+        self.assertFalse(ldt.dst())
+
+        gdt = datetime(1941, 6, 23, 21, tzinfo=timezone.utc)
+        ldt = gdt.astimezone(Vilnius)
+        self.assertEqual(ldt.strftime("%c %Z%z"),
+                         'Mon Jun 23 23:00:00 1941 CEST+0200')
+        self.assertEqual(ldt.fold, 1)
+        self.assertTrue(ldt.dst())
+
+        gdt = datetime(1941, 6, 23, 22, tzinfo=timezone.utc)
+        ldt = gdt.astimezone(Vilnius)
+        self.assertEqual(ldt.strftime("%c %Z%z"),
+                         'Tue Jun 24 00:00:00 1941 CEST+0200')
+        self.assertEqual(ldt.fold, 0)
+        self.assertTrue(ldt.dst())
+
+    def test_vilnius_1941_toutc(self):
+        Vilnius = Europe_Vilnius_1941()
+
+        ldt = datetime(1941, 6, 23, 22, 59, 59, tzinfo=Vilnius)
+        gdt = ldt.astimezone(timezone.utc)
+        self.assertEqual(gdt.strftime("%c %Z"),
+                         'Mon Jun 23 19:59:59 1941 UTC')
+
+        ldt = datetime(1941, 6, 23, 23, 59, 59, tzinfo=Vilnius)
+        gdt = ldt.astimezone(timezone.utc)
+        self.assertEqual(gdt.strftime("%c %Z"),
+                         'Mon Jun 23 20:59:59 1941 UTC')
+
+        ldt = datetime(1941, 6, 23, 23, 59, 59, tzinfo=Vilnius, fold=1)
+        gdt = ldt.astimezone(timezone.utc)
+        self.assertEqual(gdt.strftime("%c %Z"),
+                         'Mon Jun 23 21:59:59 1941 UTC')
+
+        ldt = datetime(1941, 6, 24, 0, tzinfo=Vilnius)
+        gdt = ldt.astimezone(timezone.utc)
+        self.assertEqual(gdt.strftime("%c %Z"),
+                         'Mon Jun 23 22:00:00 1941 UTC')
+
+
+    def test_constructors(self):
+        t = time(0, fold=1)
+        dt = datetime(1, 1, 1, fold=1)
+        self.assertEqual(t.fold, 1)
+        self.assertEqual(dt.fold, 1)
+        with self.assertRaises(TypeError):
+            time(0, 0, 0, 0, None, 0)
+
+    def test_member(self):
+        dt = datetime(1, 1, 1, fold=1)
+        t = dt.time()
+        self.assertEqual(t.fold, 1)
+        t = dt.timetz()
+        self.assertEqual(t.fold, 1)
+
+    def test_replace(self):
+        t = time(0)
+        dt = datetime(1, 1, 1)
+        self.assertEqual(t.replace(fold=1).fold, 1)
+        self.assertEqual(dt.replace(fold=1).fold, 1)
+        self.assertEqual(t.replace(fold=0).fold, 0)
+        self.assertEqual(dt.replace(fold=0).fold, 0)
+        # Check that replacement of other fields does not change "fold".
+        t = t.replace(fold=1, tzinfo=Eastern)
+        dt = dt.replace(fold=1, tzinfo=Eastern)
+        self.assertEqual(t.replace(tzinfo=None).fold, 1)
+        self.assertEqual(dt.replace(tzinfo=None).fold, 1)
+        # Check that fold is a keyword-only argument
+        with self.assertRaises(TypeError):
+            t.replace(1, 1, 1, None, 1)
+        with self.assertRaises(TypeError):
+            dt.replace(1, 1, 1, 1, 1, 1, 1, None, 1)
+
+    def test_comparison(self):
+        t = time(0)
+        dt = datetime(1, 1, 1)
+        self.assertEqual(t, t.replace(fold=1))
+        self.assertEqual(dt, dt.replace(fold=1))
+
+    def test_hash(self):
+        t = time(0)
+        dt = datetime(1, 1, 1)
+        self.assertEqual(hash(t), hash(t.replace(fold=1)))
+        self.assertEqual(hash(dt), hash(dt.replace(fold=1)))
+
+    @support.run_with_tz('EST+05EDT,M3.2.0,M11.1.0')
+    def test_fromtimestamp(self):
+        s = 1414906200
+        dt0 = datetime.fromtimestamp(s)
+        dt1 = datetime.fromtimestamp(s + 3600)
+        self.assertEqual(dt0.fold, 0)
+        self.assertEqual(dt1.fold, 1)
+
+    @support.run_with_tz('Australia/Lord_Howe')
+    def test_fromtimestamp_lord_howe(self):
+        tm = _time.localtime(1.4e9)
+        if _time.strftime('%Z%z', tm) != 'LHST+1030':
+            self.skipTest('Australia/Lord_Howe timezone is not supported on this platform')
+        # $ TZ=Australia/Lord_Howe date -r 1428158700
+        # Sun Apr  5 01:45:00 LHDT 2015
+        # $ TZ=Australia/Lord_Howe date -r 1428160500
+        # Sun Apr  5 01:45:00 LHST 2015
+        s = 1428158700
+        t0 = datetime.fromtimestamp(s)
+        t1 = datetime.fromtimestamp(s + 1800)
+        self.assertEqual(t0, t1)
+        self.assertEqual(t0.fold, 0)
+        self.assertEqual(t1.fold, 1)
+
+
+    @support.run_with_tz('EST+05EDT,M3.2.0,M11.1.0')
+    def test_timestamp(self):
+        dt0 = datetime(2014, 11, 2, 1, 30)
+        dt1 = dt0.replace(fold=1)
+        self.assertEqual(dt0.timestamp() + 3600,
+                         dt1.timestamp())
+
+    @support.run_with_tz('Australia/Lord_Howe')
+    def test_timestamp_lord_howe(self):
+        tm = _time.localtime(1.4e9)
+        if _time.strftime('%Z%z', tm) != 'LHST+1030':
+            self.skipTest('Australia/Lord_Howe timezone is not supported on this platform')
+        t = datetime(2015, 4, 5, 1, 45)
+        s0 = t.replace(fold=0).timestamp()
+        s1 = t.replace(fold=1).timestamp()
+        self.assertEqual(s0 + 1800, s1)
+
+
+    @support.run_with_tz('EST+05EDT,M3.2.0,M11.1.0')
+    def test_astimezone(self):
+        dt0 = datetime(2014, 11, 2, 1, 30)
+        dt1 = dt0.replace(fold=1)
+        # Convert both naive instances to aware.
+        adt0 = dt0.astimezone()
+        adt1 = dt1.astimezone()
+        # Check that the first instance in DST zone and the second in STD
+        self.assertEqual(adt0.tzname(), 'EDT')
+        self.assertEqual(adt1.tzname(), 'EST')
+        self.assertEqual(adt0 + HOUR, adt1)
+        # Aware instances with fixed offset tzinfo's always have fold=0
+        self.assertEqual(adt0.fold, 0)
+        self.assertEqual(adt1.fold, 0)
+
+
+    def test_pickle_fold(self):
+        t = time(fold=1)
+        dt = datetime(1, 1, 1, fold=1)
+        for pickler, unpickler, proto in pickle_choices:
+            for x in [t, dt]:
+                s = pickler.dumps(x, proto)
+                y = unpickler.loads(s)
+                self.assertEqual(x, y)
+                self.assertEqual((0 if proto < 4 else x.fold), y.fold)
+
+    def test_repr(self):
+        t = time(fold=1)
+        dt = datetime(1, 1, 1, fold=1)
+        self.assertEqual(repr(t), 'datetime.time(0, 0, fold=1)')
+        self.assertEqual(repr(dt),
+                         'datetime.datetime(1, 1, 1, 0, 0, fold=1)')
+
+    def test_dst(self):
+        # Let's first establish that things work in regular times.
+        dt_summer = datetime(2002, 10, 27, 1, tzinfo=Eastern2) - timedelta.resolution
+        dt_winter = datetime(2002, 10, 27, 2, tzinfo=Eastern2)
+        self.assertEqual(dt_summer.dst(), HOUR)
+        self.assertEqual(dt_winter.dst(), ZERO)
+        # The disambiguation flag is ignored
+        self.assertEqual(dt_summer.replace(fold=1).dst(), HOUR)
+        self.assertEqual(dt_winter.replace(fold=1).dst(), ZERO)
+
+        # Pick local time in the fold.
+        for minute in [0, 30, 59]:
+            dt = datetime(2002, 10, 27, 1, minute, tzinfo=Eastern2)
+            # With fold=0 (the default) it is in DST.
+            self.assertEqual(dt.dst(), HOUR)
+            # With fold=1 it is in STD.
+            self.assertEqual(dt.replace(fold=1).dst(), ZERO)
+
+        # Pick local time in the gap.
+        for minute in [0, 30, 59]:
+            dt = datetime(2002, 4, 7, 2, minute, tzinfo=Eastern2)
+            # With fold=0 (the default) it is in STD.
+            self.assertEqual(dt.dst(), ZERO)
+            # With fold=1 it is in DST.
+            self.assertEqual(dt.replace(fold=1).dst(), HOUR)
+
+
+    def test_utcoffset(self):
+        # Let's first establish that things work in regular times.
+        dt_summer = datetime(2002, 10, 27, 1, tzinfo=Eastern2) - timedelta.resolution
+        dt_winter = datetime(2002, 10, 27, 2, tzinfo=Eastern2)
+        self.assertEqual(dt_summer.utcoffset(), -4 * HOUR)
+        self.assertEqual(dt_winter.utcoffset(), -5 * HOUR)
+        # The disambiguation flag is ignored
+        self.assertEqual(dt_summer.replace(fold=1).utcoffset(), -4 * HOUR)
+        self.assertEqual(dt_winter.replace(fold=1).utcoffset(), -5 * HOUR)
+
+    def test_fromutc(self):
+        # Let's first establish that things work in regular times.
+        u_summer = datetime(2002, 10, 27, 6, tzinfo=Eastern2) - timedelta.resolution
+        u_winter = datetime(2002, 10, 27, 7, tzinfo=Eastern2)
+        t_summer = Eastern2.fromutc(u_summer)
+        t_winter = Eastern2.fromutc(u_winter)
+        self.assertEqual(t_summer, u_summer - 4 * HOUR)
+        self.assertEqual(t_winter, u_winter - 5 * HOUR)
+        self.assertEqual(t_summer.fold, 0)
+        self.assertEqual(t_winter.fold, 0)
+
+        # What happens in the fall-back fold?
+        u = datetime(2002, 10, 27, 5, 30, tzinfo=Eastern2)
+        t0 = Eastern2.fromutc(u)
+        u += HOUR
+        t1 = Eastern2.fromutc(u)
+        self.assertEqual(t0, t1)
+        self.assertEqual(t0.fold, 0)
+        self.assertEqual(t1.fold, 1)
+        # The tricky part is when u is in the local fold:
+        u = datetime(2002, 10, 27, 1, 30, tzinfo=Eastern2)
+        t = Eastern2.fromutc(u)
+        self.assertEqual((t.day, t.hour), (26, 21))
+        # .. or gets into the local fold after a standard time adjustment
+        u = datetime(2002, 10, 27, 6, 30, tzinfo=Eastern2)
+        t = Eastern2.fromutc(u)
+        self.assertEqual((t.day, t.hour), (27, 1))
+
+        # What happens in the spring-forward gap?
+        u = datetime(2002, 4, 7, 2, 0, tzinfo=Eastern2)
+        t = Eastern2.fromutc(u)
+        self.assertEqual((t.day, t.hour), (6, 21))
+
+    def test_mixed_compare_regular(self):
+        t = datetime(2000, 1, 1, tzinfo=Eastern2)
+        self.assertEqual(t, t.astimezone(timezone.utc))
+        t = datetime(2000, 6, 1, tzinfo=Eastern2)
+        self.assertEqual(t, t.astimezone(timezone.utc))
+
+    def test_mixed_compare_fold(self):
+        t_fold = datetime(2002, 10, 27, 1, 45, tzinfo=Eastern2)
+        t_fold_utc = t_fold.astimezone(timezone.utc)
+        self.assertNotEqual(t_fold, t_fold_utc)
+
+    def test_mixed_compare_gap(self):
+        t_gap = datetime(2002, 4, 7, 2, 45, tzinfo=Eastern2)
+        t_gap_utc = t_gap.astimezone(timezone.utc)
+        self.assertNotEqual(t_gap, t_gap_utc)
+
+    def test_hash_aware(self):
+        t = datetime(2000, 1, 1, tzinfo=Eastern2)
+        self.assertEqual(hash(t), hash(t.replace(fold=1)))
+        t_fold = datetime(2002, 10, 27, 1, 45, tzinfo=Eastern2)
+        t_gap = datetime(2002, 4, 7, 2, 45, tzinfo=Eastern2)
+        self.assertEqual(hash(t_fold), hash(t_fold.replace(fold=1)))
+        self.assertEqual(hash(t_gap), hash(t_gap.replace(fold=1)))
+
+SEC = timedelta(0, 1)
+
+def pairs(iterable):
+    a, b = itertools.tee(iterable)
+    next(b, None)
+    return zip(a, b)
+
+class ZoneInfo(tzinfo):
+    zoneroot = '/usr/share/zoneinfo'
+    def __init__(self, ut, ti):
+        """
+
+        :param ut: array
+            Array of transition point timestamps
+        :param ti: list
+            A list of (offset, isdst, abbr) tuples
+        :return: None
+        """
+        self.ut = ut
+        self.ti = ti
+        self.lt = self.invert(ut, ti)
+
+    @staticmethod
+    def invert(ut, ti):
+        lt = (ut.__copy__(), ut.__copy__())
+        if ut:
+            offset = ti[0][0] // SEC
+            lt[0][0] = max(-2**31, lt[0][0] + offset)
+            lt[1][0] = max(-2**31, lt[1][0] + offset)
+            for i in range(1, len(ut)):
+                lt[0][i] += ti[i-1][0] // SEC
+                lt[1][i] += ti[i][0] // SEC
+        return lt
+
+    @classmethod
+    def fromfile(cls, fileobj):
+        if fileobj.read(4).decode() != "TZif":
+            raise ValueError("not a zoneinfo file")
+        fileobj.seek(32)
+        counts = array('i')
+        counts.fromfile(fileobj, 3)
+        if sys.byteorder != 'big':
+            counts.byteswap()
+
+        ut = array('i')
+        ut.fromfile(fileobj, counts[0])
+        if sys.byteorder != 'big':
+            ut.byteswap()
+
+        type_indices = array('B')
+        type_indices.fromfile(fileobj, counts[0])
+
+        ttis = []
+        for i in range(counts[1]):
+            ttis.append(struct.unpack(">lbb", fileobj.read(6)))
+
+        abbrs = fileobj.read(counts[2])
+
+        # Convert ttis
+        for i, (gmtoff, isdst, abbrind) in enumerate(ttis):
+            abbr = abbrs[abbrind:abbrs.find(0, abbrind)].decode()
+            ttis[i] = (timedelta(0, gmtoff), isdst, abbr)
+
+        ti = [None] * len(ut)
+        for i, idx in enumerate(type_indices):
+            ti[i] = ttis[idx]
+
+        self = cls(ut, ti)
+
+        return self
+
+    @classmethod
+    def fromname(cls, name):
+        path = os.path.join(cls.zoneroot, name)
+        with open(path, 'rb') as f:
+            return cls.fromfile(f)
+
+    EPOCHORDINAL = date(1970, 1, 1).toordinal()
+
+    def fromutc(self, dt):
+        """datetime in UTC -> datetime in local time."""
+
+        if not isinstance(dt, datetime):
+            raise TypeError("fromutc() requires a datetime argument")
+        if dt.tzinfo is not self:
+            raise ValueError("dt.tzinfo is not self")
+
+        timestamp = ((dt.toordinal() - self.EPOCHORDINAL) * 86400
+                     + dt.hour * 3600
+                     + dt.minute * 60
+                     + dt.second)
+
+        if timestamp < self.ut[1]:
+            tti = self.ti[0]
+            fold = 0
+        else:
+            idx = bisect.bisect_right(self.ut, timestamp)
+            assert self.ut[idx-1] <= timestamp
+            assert idx == len(self.ut) or timestamp < self.ut[idx]
+            tti_prev, tti = self.ti[idx-2:idx]
+            # Detect fold
+            shift = tti_prev[0] - tti[0]
+            fold = (shift > timedelta(0, timestamp - self.ut[idx-1]))
+        dt += tti[0]
+        if fold:
+            return dt.replace(fold=1)
+        else:
+            return dt
+
+    def _find_ti(self, dt, i):
+        timestamp = ((dt.toordinal() - self.EPOCHORDINAL) * 86400
+             + dt.hour * 3600
+             + dt.minute * 60
+             + dt.second)
+        lt = self.lt[dt.fold]
+        idx = bisect.bisect_right(lt, timestamp)
+
+        return self.ti[max(0, idx - 1)][i]
+
+    def utcoffset(self, dt):
+        return self._find_ti(dt, 0)
+
+    def dst(self, dt):
+        isdst = self._find_ti(dt, 1)
+        # XXX: We cannot accurately determine the "save" value,
+        # so let's return 1h whenever DST is in effect.  Since
+        # we don't use dst() in fromutc(), it is unlikely that
+        # it will be needed for anything more than bool(dst()).
+        return ZERO if isdst else HOUR
+
+    def tzname(self, dt):
+        return self._find_ti(dt, 2)
+
+    @classmethod
+    def zonenames(cls, zonedir=None):
+        if zonedir is None:
+            zonedir = cls.zoneroot
+        for root, _, files in os.walk(zonedir):
+            for f in files:
+                p = os.path.join(root, f)
+                with open(p, 'rb') as o:
+                    magic =  o.read(4)
+                if magic == b'TZif':
+                    yield p[len(zonedir) + 1:]
+
+    @classmethod
+    def stats(cls, start_year=1):
+        count = gap_count = fold_count = zeros_count = 0
+        min_gap = min_fold = timedelta.max
+        max_gap = max_fold = ZERO
+        min_gap_datetime = max_gap_datetime = datetime.min
+        min_gap_zone = max_gap_zone = None
+        min_fold_datetime = max_fold_datetime = datetime.min
+        min_fold_zone = max_fold_zone = None
+        stats_since = datetime(start_year, 1, 1) # Starting from 1970 eliminates a lot of noise
+        for zonename in cls.zonenames():
+            count += 1
+            tz = cls.fromname(zonename)
+            for dt, shift in tz.transitions():
+                if dt < stats_since:
+                    continue
+                if shift > ZERO:
+                    gap_count += 1
+                    if (shift, dt) > (max_gap, max_gap_datetime):
+                        max_gap = shift
+                        max_gap_zone = zonename
+                        max_gap_datetime = dt
+                    if (shift, datetime.max - dt) < (min_gap, datetime.max - min_gap_datetime):
+                        min_gap = shift
+                        min_gap_zone = zonename
+                        min_gap_datetime = dt
+                elif shift < ZERO:
+                    fold_count += 1
+                    shift = -shift
+                    if (shift, dt) > (max_fold, max_fold_datetime):
+                        max_fold = shift
+                        max_fold_zone = zonename
+                        max_fold_datetime = dt
+                    if (shift, datetime.max - dt) < (min_fold, datetime.max - min_fold_datetime):
+                        min_fold = shift
+                        min_fold_zone = zonename
+                        min_fold_datetime = dt
+                else:
+                    zeros_count += 1
+        trans_counts = (gap_count, fold_count, zeros_count)
+        print("Number of zones:       %5d" % count)
+        print("Number of transitions: %5d = %d (gaps) + %d (folds) + %d (zeros)" %
+              ((sum(trans_counts),) + trans_counts))
+        print("Min gap:         %16s at %s in %s" % (min_gap, min_gap_datetime, min_gap_zone))
+        print("Max gap:         %16s at %s in %s" % (max_gap, max_gap_datetime, max_gap_zone))
+        print("Min fold:        %16s at %s in %s" % (min_fold, min_fold_datetime, min_fold_zone))
+        print("Max fold:        %16s at %s in %s" % (max_fold, max_fold_datetime, max_fold_zone))
+
+
+    def transitions(self):
+        for (_, prev_ti), (t, ti) in pairs(zip(self.ut, self.ti)):
+            shift = ti[0] - prev_ti[0]
+            yield datetime.utcfromtimestamp(t), shift
+
+    def nondst_folds(self):
+        """Find all folds with the same value of isdst on both sides of the transition."""
+        for (_, prev_ti), (t, ti) in pairs(zip(self.ut, self.ti)):
+            shift = ti[0] - prev_ti[0]
+            if shift < ZERO and ti[1] == prev_ti[1]:
+                yield datetime.utcfromtimestamp(t), -shift, prev_ti[2], ti[2]
+
+    @classmethod
+    def print_all_nondst_folds(cls, same_abbr=False, start_year=1):
+        count = 0
+        for zonename in cls.zonenames():
+            tz = cls.fromname(zonename)
+            for dt, shift, prev_abbr, abbr in tz.nondst_folds():
+                if dt.year < start_year or same_abbr and prev_abbr != abbr:
+                    continue
+                count += 1
+                print("%3d) %-30s %s %10s %5s -> %s" %
+                      (count, zonename, dt, shift, prev_abbr, abbr))
+
+    def folds(self):
+        for t, shift in self.transitions():
+            if shift < ZERO:
+                yield t, -shift
+
+    def gaps(self):
+        for t, shift in self.transitions():
+            if shift > ZERO:
+                yield t, shift
+
+    def zeros(self):
+        for t, shift in self.transitions():
+            if not shift:
+                yield t
+
+
+class ZoneInfoTest(unittest.TestCase):
+    zonename = 'America/New_York'
+
+    def setUp(self):
+        if sys.platform == "win32":
+            self.skipTest("Skipping zoneinfo tests on Windows")
+        self.tz = ZoneInfo.fromname(self.zonename)
+
+    def assertEquivDatetimes(self, a, b):
+        self.assertEqual((a.replace(tzinfo=None), a.fold, id(a.tzinfo)),
+                         (b.replace(tzinfo=None), b.fold, id(b.tzinfo)))
+
+    def test_folds(self):
+        tz = self.tz
+        for dt, shift in tz.folds():
+            for x in [0 * shift, 0.5 * shift, shift - timedelta.resolution]:
+                udt = dt + x
+                ldt = tz.fromutc(udt.replace(tzinfo=tz))
+                self.assertEqual(ldt.fold, 1)
+                adt = udt.replace(tzinfo=timezone.utc).astimezone(tz)
+                self.assertEquivDatetimes(adt, ldt)
+                utcoffset = ldt.utcoffset()
+                self.assertEqual(ldt.replace(tzinfo=None), udt + utcoffset)
+                # Round trip
+                self.assertEquivDatetimes(ldt.astimezone(timezone.utc),
+                                          udt.replace(tzinfo=timezone.utc))
+
+
+            for x in [-timedelta.resolution, shift]:
+                udt = dt + x
+                udt = udt.replace(tzinfo=tz)
+                ldt = tz.fromutc(udt)
+                self.assertEqual(ldt.fold, 0)
+
+    def test_gaps(self):
+        tz = self.tz
+        for dt, shift in tz.gaps():
+            for x in [0 * shift, 0.5 * shift, shift - timedelta.resolution]:
+                udt = dt + x
+                udt = udt.replace(tzinfo=tz)
+                ldt = tz.fromutc(udt)
+                self.assertEqual(ldt.fold, 0)
+                adt = udt.replace(tzinfo=timezone.utc).astimezone(tz)
+                self.assertEquivDatetimes(adt, ldt)
+                utcoffset = ldt.utcoffset()
+                self.assertEqual(ldt.replace(tzinfo=None), udt.replace(tzinfo=None) + utcoffset)
+                # Create a local time inside the gap
+                ldt = tz.fromutc(dt.replace(tzinfo=tz)) - shift + x
+                self.assertLess(ldt.replace(fold=1).utcoffset(),
+                                ldt.replace(fold=0).utcoffset(),
+                                "At %s." % ldt)
+
+            for x in [-timedelta.resolution, shift]:
+                udt = dt + x
+                ldt = tz.fromutc(udt.replace(tzinfo=tz))
+                self.assertEqual(ldt.fold, 0)
+
+    def test_system_transitions(self):
+        if ('Riyadh8' in self.zonename or
+            # From tzdata NEWS file:
+            # The files solar87, solar88, and solar89 are no longer distributed.
+            # They were a negative experiment - that is, a demonstration that
+            # tz data can represent solar time only with some difficulty and error.
+            # Their presence in the distribution caused confusion, as Riyadh
+            # civil time was generally not solar time in those years.
+                self.zonename.startswith('right/')):
+            self.skipTest("Skipping %s" % self.zonename)
+        tz = ZoneInfo.fromname(self.zonename)
+        TZ = os.environ.get('TZ')
+        os.environ['TZ'] = self.zonename
+        try:
+            _time.tzset()
+            for udt, shift in tz.transitions():
+                if self.zonename == 'Europe/Tallinn' and udt.date() == date(1999, 10, 31):
+                    print("Skip %s %s transition" % (self.zonename, udt))
+                    continue
+                s0 = (udt - datetime(1970, 1, 1)) // SEC
+                ss = shift // SEC   # shift seconds
+                for x in [-40 * 3600, -20*3600, -1, 0,
+                          ss - 1, ss + 20 * 3600, ss + 40 * 3600]:
+                    s = s0 + x
+                    sdt = datetime.fromtimestamp(s)
+                    tzdt = datetime.fromtimestamp(s, tz).replace(tzinfo=None)
+                    self.assertEquivDatetimes(sdt, tzdt)
+                    s1 = sdt.timestamp()
+                    self.assertEqual(s, s1)
+                if ss > 0:  # gap
+                    # Create local time inside the gap
+                    dt = datetime.fromtimestamp(s0) - shift / 2
+                    ts0 = dt.timestamp()
+                    ts1 = dt.replace(fold=1).timestamp()
+                    self.assertEqual(ts0, s0 + ss / 2)
+                    self.assertEqual(ts1, s0 - ss / 2)
+        finally:
+            if TZ is None:
+                del os.environ['TZ']
+            else:
+                os.environ['TZ'] = TZ
+            _time.tzset()
+
+
+class ZoneInfoCompleteTest(unittest.TestCase):
+    def test_all(self):
+        requires('tzdata', 'test requires tzdata and a long time to run')
+        for name in ZoneInfo.zonenames():
+            class Test(ZoneInfoTest):
+                zonename = name
+            for suffix in ['folds', 'gaps', 'system_transitions']:
+                test = Test('test_' + suffix)
+                result = test.run()
+                self.assertTrue(result.wasSuccessful(), name + ' ' + suffix)
+
+# Iran had a sub-minute UTC offset before 1946.
+class IranTest(ZoneInfoTest):
+    zonename = 'Iran'
+
 if __name__ == "__main__":
     unittest.main()