Add support for Android to use old Olson IDs

IANA's tzdb 2020a update raised the possibility of Android continuing to
use old IDs. The tooling deliberately fails when Android isn't using
the same IDs as IANA's data. This tooling update has been prepared as
insurance in case Android needs to use old IDs in future. The existing
behavior (to error if a different ID from the IANA ID has been used)
has been retained, but with an override using "aliasId" in the
countryzones.txt.

Bug: 155738410
Test: atest --host tzlookup_generator_tests
Test: Ran the tool manually and inspected
Change-Id: I9fc5738d573d8cfe0e32a668a22eb40c49c56e82
diff --git a/input_data/android/countryzones.txt b/input_data/android/countryzones.txt
index a78447b..9b82265 100644
--- a/input_data/android/countryzones.txt
+++ b/input_data/android/countryzones.txt
@@ -91,7 +91,15 @@
 # TimeZoneMapping:
 #
 # id:
-# The ID of the time zone.
+# The ID of the time zone to use on device. See also aliasId.
+#
+# aliasId:
+# (Optional) Used to identify the modern Olson ID when the id property is
+# using an obsoleted time zone ID. A legacy time zone ID may be used on device
+# to avoid problems if the zone ID is widely used. This is intentionally
+# explicit to make it clear the use of an old ID is intentional rather than an
+# accident. The id must also link to the aliasId in IANA's data (see the IANA
+# "backward" file).
 #
 # utcOffset:
 # The expected non-DST offset for the time zone. Used as a form of
diff --git a/input_tools/android/tzlookup_generator/src/main/java/com/android/libcore/timezone/tzlookup/BackwardFile.java b/input_tools/android/tzlookup_generator/src/main/java/com/android/libcore/timezone/tzlookup/BackwardFile.java
new file mode 100644
index 0000000..161a6b8
--- /dev/null
+++ b/input_tools/android/tzlookup_generator/src/main/java/com/android/libcore/timezone/tzlookup/BackwardFile.java
@@ -0,0 +1,99 @@
+/*
+ * Copyright (C) 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.android.libcore.timezone.tzlookup;
+
+import java.io.IOException;
+import java.nio.charset.StandardCharsets;
+import java.nio.file.Files;
+import java.nio.file.Paths;
+import java.text.ParseException;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.stream.Collectors;
+
+/**
+ * A class that knows about the structure of the backward file.
+ */
+final class BackwardFile {
+
+    private final Map<String, String> links = new HashMap<>();
+
+    private BackwardFile() {}
+
+    static BackwardFile parse(String backwardFile) throws IOException, ParseException {
+        BackwardFile backward = new BackwardFile();
+
+        List<String> lines = Files
+                .readAllLines(Paths.get(backwardFile), StandardCharsets.US_ASCII);
+
+        // Remove comments
+        List<String> linkLines =
+                lines.stream()
+                        .filter(s -> !(s.startsWith("#") || s.isEmpty()))
+                        .collect(Collectors.toList());
+
+        for (String linkLine : linkLines) {
+            String[] fields = linkLine.split("\t+");
+            if (fields.length < 3 || !fields[0].equals("Link")) {
+                throw new ParseException("Line is malformed: " + linkLine, 0);
+            }
+            backward.addLink(fields[1], fields[2]);
+        }
+        return backward;
+    }
+
+    /**
+     * Add a link entry.
+     *
+     * @param target the new tz ID
+     * @param linkName the old tz ID
+     */
+    private void addLink(String target, String linkName) {
+        String oldValue = links.put(linkName, target);
+        if (oldValue != null) {
+            throw new IllegalStateException("Duplicate link from " + linkName);
+        }
+    }
+
+    /** Returns a mapping from linkName (old tz ID) to target (new tz ID). */
+    Map<String, String> getDirectLinks() {
+        // Validate links for cycles and collapse the links if there are links to links. There's a
+        // simple check to confirm that no chain is longer than a fixed length, to guard against
+        // cycles.
+        final int maxChainLength = 2;
+        Map<String, String> collapsedLinks = new HashMap<>();
+        for (String fromId : links.keySet()) {
+            int chainLength = 0;
+            String currentId = fromId;
+            String lastId = null;
+            while ((currentId = links.get(currentId)) != null) {
+                chainLength++;
+                lastId = currentId;
+                if (chainLength >= maxChainLength) {
+                    throw new IllegalStateException(
+                            "Chain from " + fromId + " is longer than " + maxChainLength);
+                }
+            }
+            if (chainLength == 0) {
+                throw new IllegalStateException("Null Link targetId for " + fromId);
+            }
+            collapsedLinks.put(fromId, lastId);
+        }
+        return Collections.unmodifiableMap(collapsedLinks);
+    }
+}
diff --git a/input_tools/android/tzlookup_generator/src/main/java/com/android/libcore/timezone/tzlookup/TzLookupGenerator.java b/input_tools/android/tzlookup_generator/src/main/java/com/android/libcore/timezone/tzlookup/TzLookupGenerator.java
index f1175f0..b6d368b 100644
--- a/input_tools/android/tzlookup_generator/src/main/java/com/android/libcore/timezone/tzlookup/TzLookupGenerator.java
+++ b/input_tools/android/tzlookup_generator/src/main/java/com/android/libcore/timezone/tzlookup/TzLookupGenerator.java
@@ -30,6 +30,7 @@
 import java.text.ParseException;
 import java.time.Instant;
 import java.time.temporal.ChronoUnit;
+import java.util.ArrayList;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
@@ -71,25 +72,29 @@
 
     private final String countryZonesFile;
     private final String zoneTabFile;
+    private final String backwardFile;
     private final String outputFile;
 
     /**
      * Executes the generator.
      */
     public static void main(String[] args) throws Exception {
-        if (args.length != 3) {
+        if (args.length != 4) {
             System.err.println(
                     "usage: java com.android.libcore.timezone.tzlookup.TzLookupGenerator"
-                            + " <input proto file> <zone.tab file> <output xml file>");
+                            + " <input proto file> <zone.tab file> <backward file>"
+                            + " <output xml file>");
             System.exit(0);
         }
-        boolean success = new TzLookupGenerator(args[0], args[1], args[2]).execute();
+        boolean success = new TzLookupGenerator(args[0], args[1], args[2], args[3]).execute();
         System.exit(success ? 0 : 1);
     }
 
-    TzLookupGenerator(String countryZonesFile, String zoneTabFile, String outputFile) {
+    TzLookupGenerator(String countryZonesFile, String zoneTabFile, String backwardFile,
+            String outputFile) {
         this.countryZonesFile = countryZonesFile;
         this.zoneTabFile = zoneTabFile;
+        this.backwardFile = backwardFile;
         this.outputFile = outputFile;
     }
 
@@ -142,8 +147,12 @@
                         + " not present in zonetab.");
             }
 
+            // Obtain and validate a mapping from old IDs to new IDs.
+            Map<String, String> zoneIdLinks = parseAndValidateBackwardFile(backwardFile, errors);
+            errors.throwIfError("Errors accumulated");
+
             TzLookupFile.TimeZones timeZonesOut = createOutputTimeZones(
-                    inputIanaVersion, zoneTabMapping, countriesIn, errors);
+                    inputIanaVersion, zoneTabMapping, countriesIn, zoneIdLinks, errors);
             errors.throwIfError("Errors accumulated");
 
             // Write the output structure if there wasn't an error.
@@ -179,6 +188,36 @@
         }
     }
 
+    /**
+     * Load the backward file and return the links contained within. This is used as the source of
+     * equivalent time zone IDs.
+     */
+    private static Map<String, String> parseAndValidateBackwardFile(
+            String backwardFile, Errors errors) {
+        errors.pushScope("Parsing " + backwardFile);
+        try {
+            BackwardFile backwardIn = BackwardFile.parse(backwardFile);
+
+            // Validate the links.
+            Map<String, String> zoneIdLinks = backwardIn.getDirectLinks();
+            zoneIdLinks.forEach(
+                    (k, v) -> {
+                        if (invalidTimeZoneId(k)) {
+                            errors.addError("Bad 'from' link: " + k + "->" + v);
+                        }
+                        if (invalidTimeZoneId(v)) {
+                            errors.addError("Bad 'to' link: " + k + "->" + v);
+                        }
+                    });
+            return zoneIdLinks;
+        } catch (ParseException | IOException e) {
+            errors.addError("Unable to parse " + backwardFile, e);
+            return null;
+        } finally {
+            errors.popScope();
+        }
+    }
+
     private static CountryZonesFile.CountryZones parseAndValidateCountryZones(
             String countryZonesFile, Errors errors) throws HaltExecutionException {
         errors.pushScope("Parsing " + countryZonesFile);
@@ -195,7 +234,8 @@
 
     private static TzLookupFile.TimeZones createOutputTimeZones(String inputIanaVersion,
             Map<String, List<String>> zoneTabMapping, List<CountryZonesFile.Country> countriesIn,
-            Errors errors) throws HaltExecutionException {
+            Map<String, String> zoneIdLinks, Errors errors)
+            throws HaltExecutionException {
 
         // Start constructing the output structure.
         TzLookupFile.TimeZones timeZonesOut = new TzLookupFile.TimeZones(inputIanaVersion);
@@ -222,7 +262,7 @@
 
             TzLookupFile.Country countryOut = processCountry(
                     offsetSampleTimeMillis, everUseUtcStartTimeMillis, countryIn,
-                    zoneTabCountryTimeZoneIds, errors);
+                    zoneTabCountryTimeZoneIds, zoneIdLinks, errors);
             if (countryOut == null) {
                 // Continue processing countries if there are only errors.
                 continue;
@@ -235,7 +275,8 @@
 
     private static TzLookupFile.Country processCountry(long offsetSampleTimeMillis,
             long everUseUtcStartTimeMillis, CountryZonesFile.Country countryIn,
-            List<String> zoneTabCountryTimeZoneIds, Errors errors) {
+            List<String> zoneTabCountryTimeZoneIds, Map<String, String> zoneIdLinks,
+            Errors errors) {
         String isoCode = countryIn.getIsoCode();
         errors.pushScope("country=" + isoCode);
         try {
@@ -304,10 +345,12 @@
                     return null;
                 }
 
-                if (!Utils.setEquals(zoneTabCountryTimeZoneIds, countryTimeZoneIds)) {
-                    errors.addError("IANA lists " + isoCode
-                            + " as having zones: " + zoneTabCountryTimeZoneIds
-                            + ", but countryzones has " + countryTimeZoneIds);
+                // Validate the IDs being used against the IANA data for the country. If it fails
+                // the countryzones.txt needs to be updated with new IDs (or an alias can be added
+                // if there's some reason to keep using the old ID).
+                validateCountryZonesTzIdsAgainstIana(isoCode, zoneTabCountryTimeZoneIds,
+                        timeZonesIn, zoneIdLinks, errors);
+                if (errors.hasError()) {
                     // No point in continuing.
                     return null;
                 }
@@ -364,6 +407,37 @@
         }
     }
 
+    private static void validateCountryZonesTzIdsAgainstIana(String isoCode,
+            List<String> zoneTabCountryTimeZoneIds,
+            List<CountryZonesFile.TimeZoneMapping> timeZoneMappings,
+            Map<String, String> zoneIdLinks, Errors errors) {
+
+        List<String> expectedIanaTimeZoneIds = new ArrayList<>();
+        for (CountryZonesFile.TimeZoneMapping mapping : timeZoneMappings) {
+            String timeZoneId = mapping.getId();
+            String expectedIanaTimeZoneId;
+            if (!mapping.hasAliasId()) {
+                expectedIanaTimeZoneId = timeZoneId;
+            } else {
+                String aliasTimeZoneId = mapping.getAliasId();
+
+                // Confirm the alias is valid.
+                if (!aliasTimeZoneId.equals(zoneIdLinks.get(timeZoneId))) {
+                    errors.addError(timeZoneId + " does not link to " + aliasTimeZoneId);
+                    return;
+                }
+                expectedIanaTimeZoneId = aliasTimeZoneId;
+            }
+            expectedIanaTimeZoneIds.add(expectedIanaTimeZoneId);
+        }
+
+        if (!Utils.setEquals(zoneTabCountryTimeZoneIds, expectedIanaTimeZoneIds)) {
+            errors.addError("IANA lists " + isoCode
+                    + " as having zones: " + zoneTabCountryTimeZoneIds
+                    + ", but countryzones has " + expectedIanaTimeZoneIds);
+        }
+    }
+
     /**
      * Determines the default zone ID for the country.
      */
diff --git a/input_tools/android/tzlookup_generator/src/main/proto/country_zones_file.proto b/input_tools/android/tzlookup_generator/src/main/proto/country_zones_file.proto
index 6da1c29..9ed5644 100644
--- a/input_tools/android/tzlookup_generator/src/main/proto/country_zones_file.proto
+++ b/input_tools/android/tzlookup_generator/src/main/proto/country_zones_file.proto
@@ -35,7 +35,8 @@
 
 message TimeZoneMapping {
     required string id = 1;
-    required string utcOffset = 2;
-    optional bool shownInPicker = 3 [default = true];
-    optional uint32 priority = 4 [default = 1];
+    optional string aliasId = 2;
+    required string utcOffset = 3;
+    optional bool shownInPicker = 4 [default = true];
+    optional uint32 priority = 5 [default = 1];
 }
diff --git a/input_tools/android/tzlookup_generator/src/test/java/com/android/libcore/timezone/tzlookup/BackwardFileTest.java b/input_tools/android/tzlookup_generator/src/test/java/com/android/libcore/timezone/tzlookup/BackwardFileTest.java
new file mode 100644
index 0000000..c575a8e
--- /dev/null
+++ b/input_tools/android/tzlookup_generator/src/test/java/com/android/libcore/timezone/tzlookup/BackwardFileTest.java
@@ -0,0 +1,122 @@
+/*
+ * Copyright (C) 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.libcore.timezone.tzlookup;
+
+import static junit.framework.TestCase.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import com.android.libcore.timezone.testing.TestUtils;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.text.ParseException;
+import java.util.HashMap;
+import java.util.Map;
+
+public class BackwardFileTest {
+
+    private Path tempDir;
+
+    @Before
+    public void setUp() throws Exception {
+        tempDir = Files.createTempDirectory("BackwardFileTest");
+    }
+
+    @After
+    public void tearDown() throws Exception {
+        TestUtils.deleteDir(tempDir);
+    }
+
+    @Test
+    public void parseEmpty() throws Exception {
+        String file = createFile("");
+        BackwardFile backward = BackwardFile.parse(file);
+        assertTrue(backward.getDirectLinks().isEmpty());
+    }
+
+    @Test
+    public void parseIgnoresCommentsAndEmptyLines() throws Exception {
+        String file = createFile(
+                "# This is a comment",
+                "",
+                "# And another",
+                "Link\tAmerica/Nuuk\t\tAmerica/Godthab"
+        );
+        BackwardFile backward = BackwardFile.parse(file);
+
+        Map<String, String> expectedLinks = new HashMap<>();
+        expectedLinks.put("America/Godthab", "America/Nuuk");
+        assertEquals(expectedLinks, backward.getDirectLinks());
+    }
+
+    @Test
+    public void parse() throws Exception {
+        String file = createFile(
+                "# This is a comment",
+                "Link\tAmerica/Nuuk\t\tAmerica/Godthab",
+                "# This is a comment",
+                "Link\tAfrica/Nairobi\t\tAfrica/Asmera",
+                "# This is a comment",
+                "Link\tAfrica/Abidjan\t\tAfrica/Timbuktu",
+                "# This is a comment"
+        );
+        BackwardFile backward = BackwardFile.parse(file);
+        Map<String, String> expectedLinks = new HashMap<>();
+        expectedLinks.put("America/Godthab", "America/Nuuk");
+        expectedLinks.put("Africa/Asmera", "Africa/Nairobi");
+        expectedLinks.put("Africa/Timbuktu", "Africa/Abidjan");
+
+        assertEquals(expectedLinks, backward.getDirectLinks());
+    }
+
+    @Test(expected = IllegalStateException.class)
+    public void getLinksWithLoop() throws Exception {
+        String file = createFile(
+                "Link\tAmerica/New_York\t\tAmerica/Los_Angeles",
+                "Link\tAmerica/Los_Angeles\t\tAmerica/Phoenix",
+                "Link\tAmerica/Phoenix\t\tAmerica/New_York"
+        );
+        BackwardFile backward = BackwardFile.parse(file);
+        backward.getDirectLinks();
+    }
+
+    @Test(expected = IllegalStateException.class)
+    public void parseWithDupes() throws Exception {
+        String file = createFile(
+                "Link\tAmerica/New_York\t\tAmerica/Los_Angeles",
+                "Link\tAmerica/Phoenix\t\tAmerica/Los_Angeles"
+        );
+        BackwardFile.parse(file);
+    }
+
+    @Test(expected = ParseException.class)
+    public void parseMalformedFile() throws Exception {
+        // Mapping lines are expected to have at least three tab-separated columns.
+        String file = createFile("NotLink\tBooHoo");
+        BackwardFile.parse(file);
+    }
+
+    private String createFile(String... lines) throws IOException {
+        return TestUtils.createFile(tempDir, lines);
+    }
+}
diff --git a/input_tools/android/tzlookup_generator/src/test/java/com/android/libcore/timezone/tzlookup/TzLookupGeneratorTest.java b/input_tools/android/tzlookup_generator/src/test/java/com/android/libcore/timezone/tzlookup/TzLookupGeneratorTest.java
index 6a4843f..d8677cc 100644
--- a/input_tools/android/tzlookup_generator/src/test/java/com/android/libcore/timezone/tzlookup/TzLookupGeneratorTest.java
+++ b/input_tools/android/tzlookup_generator/src/test/java/com/android/libcore/timezone/tzlookup/TzLookupGeneratorTest.java
@@ -32,7 +32,9 @@
 import java.nio.file.Paths;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
 import java.util.stream.Collectors;
 
 import static com.android.libcore.timezone.testing.TestUtils.assertAbsent;
@@ -64,10 +66,11 @@
         String countryZonesFile = createFile(tempDir, "THIS IS NOT A VALID FILE");
         List<ZoneTabFile.CountryEntry> gbZoneTabEntries = createValidZoneTabEntriesGb();
         String zoneTabFile = createZoneTabFile(gbZoneTabEntries);
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
     }
 
@@ -82,11 +85,12 @@
 
         List<ZoneTabFile.CountryEntry> gbZoneTabEntries = createValidZoneTabEntriesGb();
         String zoneTabFile = createZoneTabFile(gbZoneTabEntries);
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
 
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -100,13 +104,14 @@
                 createValidCountryGb().toBuilder().clearTimeZoneMappings().build();
         CountryZonesFile.CountryZones countryZones = createValidCountryZones(gbWithoutZones);
         String countryZonesFile = createCountryZonesFile(countryZones);
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
 
         String zoneTabFile = createZoneTabFile(createValidZoneTabEntriesGb());
 
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -125,13 +130,14 @@
         CountryZonesFile.CountryZones countryZones =
                 createValidCountryZones(gbWithDuplicateZones);
         String countryZonesFile = createCountryZonesFile(countryZones);
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
 
         String zoneTabFile = createZoneTabFile(createValidZoneTabEntriesGb());
 
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -150,11 +156,12 @@
 
         List<ZoneTabFile.CountryEntry> gbZoneTabEntries = createValidZoneTabEntriesGb();
         String zoneTabFile = createZoneTabFile(gbZoneTabEntries);
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
 
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -172,11 +179,12 @@
 
         List<ZoneTabFile.CountryEntry> gbZoneTabEntries = createValidZoneTabEntriesGb();
         String zoneTabFile = createZoneTabFile(gbZoneTabEntries);
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
 
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -194,7 +202,8 @@
                 .clearDefaultTimeZoneId().build();
         List<ZoneTabFile.CountryEntry> gbZoneTabEntries = createValidZoneTabEntriesGb();
 
-        String tzLookupXml = generateTzLookupXml(gbWithoutDefault, gbZoneTabEntries);
+        String tzLookupXml = generateTzLookupXml(gbWithoutDefault, gbZoneTabEntries,
+                createValidBackwardLinks());
 
         // Check gb's time zone was defaulted.
         assertContains(tzLookupXml, "code=\"gb\" default=\"" + gbTimeZoneId + "\"");
@@ -211,7 +220,8 @@
                         .build();
         List<ZoneTabFile.CountryEntry> gbZoneTabEntries = createValidZoneTabEntriesGb();
 
-        String tzLookupXml = generateTzLookupXml(gbWithExplicitDefaultTimeZone, gbZoneTabEntries);
+        String tzLookupXml = generateTzLookupXml(gbWithExplicitDefaultTimeZone, gbZoneTabEntries,
+                createValidBackwardLinks());
 
         // Check gb's time zone was defaulted.
         assertContains(tzLookupXml, "code=\"gb\" default=\"" + gbTimeZoneId + "\"");
@@ -229,11 +239,12 @@
 
         List<ZoneTabFile.CountryEntry> gbZoneTabEntries = createValidZoneTabEntriesGb();
         String zoneTabFile = createZoneTabFile(gbZoneTabEntries);
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
 
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -251,11 +262,12 @@
 
         List<ZoneTabFile.CountryEntry> gbZoneTabEntries = createValidZoneTabEntriesGb();
         String zoneTabFile = createZoneTabFile(gbZoneTabEntries);
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
 
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -271,11 +283,11 @@
 
         String zoneTabFile =
                 createZoneTabFile(createValidZoneTabEntriesFr(), createValidZoneTabEntriesUs());
-
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -293,11 +305,11 @@
         String countryZonesFile = createCountryZonesFile(countryZones);
 
         String zoneTabFile = createZoneTabFile(createValidZoneTabEntriesGb());
-
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -313,10 +325,11 @@
         String zoneTabFileWithDupes = createZoneTabFile(
                 createValidZoneTabEntriesGb(), createValidZoneTabEntriesGb());
 
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
-        TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFileWithDupes, outputFile);
+        TzLookupGenerator tzLookupGenerator = new TzLookupGenerator(
+                countryZonesFile, zoneTabFileWithDupes, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -334,11 +347,12 @@
         String countryZonesFile = createCountryZonesFile(countryZones);
 
         String zoneTabFile = createZoneTabFile(createValidZoneTabEntriesGb());
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
 
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -360,11 +374,12 @@
                 new ArrayList<>(createValidZoneTabEntriesGb());
         zoneTabEntriesWithBadId.add(new ZoneTabFile.CountryEntry("GB", INVALID_TIME_ZONE_ID));
         String zoneTabFile = createZoneTabFile(zoneTabEntriesWithBadId);
+        String backwardFile = createBackwardFile(createValidBackwardLinks());
 
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertFalse(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -372,9 +387,121 @@
     }
 
     @Test
+    public void badBackwardFile() throws Exception {
+        CountryZonesFile.CountryZones countryZones = createValidCountryZones(createValidCountryGb());
+        String countryZonesFile = createCountryZonesFile(countryZones);
+        String zoneTabFile = createZoneTabFile(createValidZoneTabEntriesGb());
+
+        String badBackwardFile = TestUtils.createFile(tempDir, "THIS IS NOT VALID");
+
+        String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
+
+        TzLookupGenerator tzLookupGenerator =
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, badBackwardFile, outputFile);
+        assertFalse(tzLookupGenerator.execute());
+
+        Path outputFilePath = Paths.get(outputFile);
+        assertEquals(0, Files.size(outputFilePath));
+    }
+
+    @Test
+    public void usingOldLinksValid() throws Exception {
+        // This simulates a case where America/Godthab has been superseded by America/Nuuk in IANA
+        // data, but Android wants to continue using America/Godthab.
+        String countryZonesWithOldIdText =
+                "isoCode:\"gl\"\n"
+                + "defaultTimeZoneId:\"America/Godthab\"\n"
+                + "timeZoneMappings:<\n"
+                + "  utcOffset:\"0:00\"\n"
+                + "  id:\"America/Danmarkshavn\"\n"
+                + ">\n"
+                + "\n"
+                + "timeZoneMappings:<\n"
+                + "  utcOffset:\"-1:00\"\n"
+                + "  id:\"America/Scoresbysund\"\n"
+                + ">\n"
+                + "\n"
+                + "timeZoneMappings:<\n"
+                + "  utcOffset:\"-3:00\"\n"
+                + "  id:\"America/Godthab\"\n"
+                + "  aliasId:\"America/Nuuk\"\n"
+                + ">\n"
+                + "\n"
+                + "timeZoneMappings:<\n"
+                + "  utcOffset:\"-4:00\"\n"
+                + "  id:\"America/Thule\"\n"
+                + ">\n";
+        Country country = parseCountry(countryZonesWithOldIdText);
+        List<ZoneTabFile.CountryEntry> zoneTabWithNewIds = Arrays.asList(
+                new ZoneTabFile.CountryEntry("GL", "America/Nuuk"),
+                new ZoneTabFile.CountryEntry("GL", "America/Danmarkshavn"),
+                new ZoneTabFile.CountryEntry("GL", "America/Scoresbysund"),
+                new ZoneTabFile.CountryEntry("GL", "America/Thule")
+        );
+        Map<String, String> links = new HashMap<>();
+        links.put("America/Godthab", "America/Nuuk");
+
+        String tzLookupXml = generateTzLookupXml(country, zoneTabWithNewIds, links);
+
+        String expectedOutput =
+                "<id>America/Danmarkshavn</id>\n"
+                        + "<id>America/Scoresbysund</id>\n"
+                        + "<id>America/Godthab</id>\n"
+                        + "<id>America/Thule</id>\n";
+        String[] expectedLines = expectedOutput.split("\\n");
+        for (String expectedLine : expectedLines) {
+            assertContains(tzLookupXml, expectedLine);
+        }
+    }
+
+    @Test
+    public void usingOldLinksMissingAlias() throws Exception {
+        // This simulates a case where America/Godthab has been superseded by America/Nuuk in IANA
+        // data, but the Android file hasn't been updated properly.
+        String countryZonesWithOldIdText =
+                "isoCode:\"gl\"\n"
+                + "defaultTimeZoneId:\"America/Godthab\"\n"
+                + "timeZoneMappings:<\n"
+                + "  utcOffset:\"0:00\"\n"
+                + "  id:\"America/Danmarkshavn\"\n"
+                + ">\n"
+                + "\n"
+                + "timeZoneMappings:<\n"
+                + "  utcOffset:\"-1:00\"\n"
+                + "  id:\"America/Scoresbysund\"\n"
+                + ">\n"
+                + "\n"
+                + "timeZoneMappings:<\n"
+                + "  utcOffset:\"-3:00\"\n"
+                + "  id:\"America/Godthab\"\n"
+
+                // Exclude the crucial line that tells the generator we meant to use an old ID...
+                /* + "  aliasId:\"America/Nuuk\"\n" */
+
+                + ">\n"
+                + "\n"
+                + "timeZoneMappings:<\n"
+                + "  utcOffset:\"-4:00\"\n"
+                + "  id:\"America/Thule\"\n"
+                + ">\n";
+        Country country = parseCountry(countryZonesWithOldIdText);
+        List<ZoneTabFile.CountryEntry> zoneTabWithNewIds = Arrays.asList(
+                new ZoneTabFile.CountryEntry("GL", "America/Nuuk"),
+                new ZoneTabFile.CountryEntry("GL", "America/Danmarkshavn"),
+                new ZoneTabFile.CountryEntry("GL", "America/Scoresbysund"),
+                new ZoneTabFile.CountryEntry("GL", "America/Thule")
+        );
+        Map<String, String> links = new HashMap<>();
+        links.put("America/Godthab", "America/Nuuk");
+
+        generateTzLookupXmlExpectFailure(country, zoneTabWithNewIds, links);
+    }
+
+    @Test
     public void everUtc_true() throws Exception {
         CountryZonesFile.Country validCountryGb = createValidCountryGb();
-        String tzLookupXml = generateTzLookupXml(validCountryGb, createValidZoneTabEntriesGb());
+        String tzLookupXml = generateTzLookupXml(validCountryGb, createValidZoneTabEntriesGb(),
+                createValidBackwardLinks());
 
         // Check gb's entry contains everutc="y".
         assertContains(tzLookupXml, "everutc=\"y\"");
@@ -383,7 +510,8 @@
     @Test
     public void everUtc_false() throws Exception {
         CountryZonesFile.Country validCountryFr = createValidCountryFr();
-        String tzLookupXml = generateTzLookupXml(validCountryFr, createValidZoneTabEntriesFr());
+        String tzLookupXml = generateTzLookupXml(validCountryFr, createValidZoneTabEntriesFr(),
+                createValidBackwardLinks());
 
         // Check fr's entry contains everutc="n".
         assertContains(tzLookupXml, "everutc=\"n\"");
@@ -401,7 +529,8 @@
         countryBuilder.setTimeZoneMappings(0, timeZoneMappingBuilder);
         CountryZonesFile.Country country = countryBuilder.build();
 
-        String tzLookupXml = generateTzLookupXml(country, createValidZoneTabEntriesFr());
+        String tzLookupXml = generateTzLookupXml(country, createValidZoneTabEntriesFr(),
+                createValidBackwardLinks());
 
         assertContains(tzLookupXml, "picker=\"n\"");
     }
@@ -418,7 +547,8 @@
         countryBuilder.setTimeZoneMappings(0, timeZoneMappingBuilder);
         CountryZonesFile.Country country = countryBuilder.build();
 
-        String tzLookupXml = generateTzLookupXml(country, createValidZoneTabEntriesFr());
+        String tzLookupXml = generateTzLookupXml(country, createValidZoneTabEntriesFr(),
+                createValidBackwardLinks());
 
         // We should not see anything "picker="y" is the implicit default.
         assertAbsent(tzLookupXml, "picker=");
@@ -428,7 +558,8 @@
     public void notAfter() throws Exception {
         CountryZonesFile.Country country = createValidCountryUs();
         List<ZoneTabFile.CountryEntry> zoneTabEntries = createValidZoneTabEntriesUs();
-        String tzLookupXml = generateTzLookupXml(country, zoneTabEntries);
+        String tzLookupXml = generateTzLookupXml(country, zoneTabEntries,
+                createValidBackwardLinks());
         String expectedOutput =
                 "<id>America/New_York</id>\n"
                 + "<id notafter=\"167814000000\">America/Detroit</id>\n"
@@ -466,17 +597,19 @@
     }
 
     private String generateTzLookupXml(CountryZonesFile.Country country,
-            List<ZoneTabFile.CountryEntry> zoneTabEntries) throws Exception {
+            List<ZoneTabFile.CountryEntry> zoneTabEntries, Map<String, String> backwardLinks)
+            throws Exception {
 
         CountryZonesFile.CountryZones countryZones = createValidCountryZones(country);
         String countryZonesFile = createCountryZonesFile(countryZones);
 
         String zoneTabFile = createZoneTabFile(zoneTabEntries);
+        String backwardFile = createBackwardFile(backwardLinks);
 
         String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
 
         TzLookupGenerator tzLookupGenerator =
-                new TzLookupGenerator(countryZonesFile, zoneTabFile, outputFile);
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
         assertTrue(tzLookupGenerator.execute());
 
         Path outputFilePath = Paths.get(outputFile);
@@ -485,6 +618,23 @@
         return readFileToString(outputFilePath);
     }
 
+    private void generateTzLookupXmlExpectFailure(CountryZonesFile.Country country,
+            List<ZoneTabFile.CountryEntry> zoneTabEntries, Map<String, String> backwardLinks)
+            throws Exception {
+
+        CountryZonesFile.CountryZones countryZones = createValidCountryZones(country);
+        String countryZonesFile = createCountryZonesFile(countryZones);
+
+        String zoneTabFile = createZoneTabFile(zoneTabEntries);
+        String backwardFile = createBackwardFile(backwardLinks);
+
+        String outputFile = Files.createTempFile(tempDir, "out", null /* suffix */).toString();
+
+        TzLookupGenerator tzLookupGenerator =
+                new TzLookupGenerator(countryZonesFile, zoneTabFile, backwardFile, outputFile);
+        assertFalse(tzLookupGenerator.execute());
+    }
+
     private static String readFileToString(Path file) throws IOException {
         return new String(Files.readAllBytes(file), StandardCharsets.UTF_8);
     }
@@ -709,6 +859,19 @@
                 new ZoneTabFile.CountryEntry("FR", "Europe/Paris"));
     }
 
+    private String createBackwardFile(Map<String, String> links) throws Exception {
+        List<String> lines = links.entrySet().stream()
+                .map(x -> "Link\t" + x.getValue() + "\t\t" + x.getKey())
+                .collect(Collectors.toList());
+        return TestUtils.createFile(tempDir, lines.toArray(new String[0]));
+    }
+
+    private static Map<String, String> createValidBackwardLinks() {
+        Map<String, String> map = new HashMap<>();
+        map.put("America/Godthab", "America/Nuuk");
+        return map;
+    }
+
     private static Country parseCountry(String text) throws Exception {
         Country.Builder builder = Country.newBuilder();
         TextFormat.getParser().merge(text, builder);
diff --git a/update-tzdata.py b/update-tzdata.py
index 61ab30e..ee370c1 100755
--- a/update-tzdata.py
+++ b/update-tzdata.py
@@ -184,8 +184,10 @@
   tzdatautil.InvokeSoong(android_build_top, ['tzlookup_generator'])
 
   zone_tab_file = '%s/zone.tab' % iana_data_dir
+  backward_file = '%s/backward' % iana_data_dir
   command = '%s/bin/tzlookup_generator' % android_host_out
-  subprocess.check_call([command, countryzones_source_file, zone_tab_file, tzlookup_dest_file])
+  subprocess.check_call([command, countryzones_source_file, zone_tab_file, backward_file,
+                         tzlookup_dest_file])
 
 
 def BuildTelephonylookup():