Provide access to new "alts" data in tzlookup.xml

Provide access to new alternative IDs (alts=) data in tzlookup.xml and
add tests.

There are various synonyms in IANA data and occasionally zone IDs are
obsoleted in favor of new ones that are functionally identical.

The alternative IDs in tzlookup.xml provide the information needed to
determine region even if alernative zone IDs are provided than those
that Android uses by default.

Bug: 155738410
Test: atest com.android.i18n.test.timezone (ZoneInfoDbTest fails, but
      atest / permission issue?)
Test: run cts -m CtsIcuTestCases -t com.android.i18n.test.timezone.ZoneInfoDbTest
Change-Id: I9ee8283bc6cdbe81b5961a5945dc33cfdfa51e3c
diff --git a/android_icu4j/api/legacy_platform/current.txt b/android_icu4j/api/legacy_platform/current.txt
index c76cccb..3795e83 100644
--- a/android_icu4j/api/legacy_platform/current.txt
+++ b/android_icu4j/api/legacy_platform/current.txt
@@ -71,7 +71,8 @@
   }
 
   public static final class CountryTimeZones.TimeZoneMapping {
-    method public static com.android.i18n.timezone.CountryTimeZones.TimeZoneMapping createForTests(String, boolean, Long);
+    method public static com.android.i18n.timezone.CountryTimeZones.TimeZoneMapping createForTests(String, boolean, Long, java.util.List<java.lang.String>);
+    method public java.util.List<java.lang.String> getAlternativeIds();
     method public Long getNotUsedAfter();
     method public android.icu.util.TimeZone getTimeZone();
     method public String getTimeZoneId();
diff --git a/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/CountryTimeZones.java b/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/CountryTimeZones.java
index e89b577..ed72e27 100644
--- a/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/CountryTimeZones.java
+++ b/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/CountryTimeZones.java
@@ -46,14 +46,17 @@
         private final String timeZoneId;
         private final boolean shownInPicker;
         private final Long notUsedAfter;
+        private final List<String> alternativeIds;
 
         /** Memoized TimeZone object for {@link #timeZoneId}. */
         private TimeZone timeZone;
 
-        TimeZoneMapping(String timeZoneId, boolean shownInPicker, Long notUsedAfter) {
+        TimeZoneMapping(String timeZoneId, boolean shownInPicker, Long notUsedAfter,
+                List<String> alternativeIds) {
             this.timeZoneId = Objects.requireNonNull(timeZoneId);
             this.shownInPicker = shownInPicker;
             this.notUsedAfter = notUsedAfter;
+            this.alternativeIds = Collections.unmodifiableList(new ArrayList<>(alternativeIds));
         }
 
         @libcore.api.CorePlatformApi
@@ -72,6 +75,15 @@
         }
 
         /**
+         * Returns a list of alternative time zone IDs that are linked to this one. Can be empty,
+         * never returns null.
+         */
+        @libcore.api.CorePlatformApi
+        public List<String> getAlternativeIds() {
+            return alternativeIds;
+        }
+
+        /**
          * Returns a {@link TimeZone} object for this mapping, or {@code null} if the ID is unknown.
          */
         @libcore.api.CorePlatformApi
@@ -104,9 +116,9 @@
 
         // VisibleForTesting
         @libcore.api.CorePlatformApi
-        public static TimeZoneMapping createForTests(
-                String timeZoneId, boolean showInPicker, Long notUsedAfter) {
-            return new TimeZoneMapping(timeZoneId, showInPicker, notUsedAfter);
+        public static TimeZoneMapping createForTests(String timeZoneId, boolean showInPicker,
+                Long notUsedAfter, List<String> alternativeIds) {
+            return new TimeZoneMapping(timeZoneId, showInPicker, notUsedAfter, alternativeIds);
         }
 
         @Override
@@ -120,12 +132,13 @@
             TimeZoneMapping that = (TimeZoneMapping) o;
             return shownInPicker == that.shownInPicker &&
                     Objects.equals(timeZoneId, that.timeZoneId) &&
-                    Objects.equals(notUsedAfter, that.notUsedAfter);
+                    Objects.equals(notUsedAfter, that.notUsedAfter) &&
+                    Objects.equals(alternativeIds, that.alternativeIds);
         }
 
         @Override
         public int hashCode() {
-            return Objects.hash(timeZoneId, shownInPicker, notUsedAfter);
+            return Objects.hash(timeZoneId, shownInPicker, notUsedAfter, alternativeIds);
         }
 
         @Override
@@ -134,6 +147,7 @@
                     + "timeZoneId='" + timeZoneId + '\''
                     + ", shownInPicker=" + shownInPicker
                     + ", notUsedAfter=" + notUsedAfter
+                    + ", alternativeIds=" + alternativeIds
                     + '}';
         }
 
diff --git a/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/CountryZonesFinder.java b/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/CountryZonesFinder.java
index 2f3b9c8..80a316e 100644
--- a/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/CountryZonesFinder.java
+++ b/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/CountryZonesFinder.java
@@ -57,15 +57,32 @@
 
     /**
      * Returns an immutable list of {@link CountryTimeZones} for countries that use the specified
-     * time zone. An exact, case-sensitive match is performed on the zone ID. This method never
-     * returns null.
+     * time zone. An exact, case-sensitive match is performed on the zone ID. If the match  but the method also
+     * checks for alternative zone IDs. This method never returns null and will usually return a
+     * list containing a single element. It can return an empty list if the zone ID is
+     * not recognized or it is not associated with a country.
      */
     @libcore.api.CorePlatformApi
     public List<CountryTimeZones> lookupCountryTimeZonesForZoneId(String zoneId) {
         List<CountryTimeZones> matches = new ArrayList<>(2);
+
+        // This implementation is deliberately flexible about supporting alternative (newer or
+        // legacy) IDs, e.g. zoneId might have come from the device's persist.sys.timezone setting,
+        // which may have been set before a tzdb upgrade, so we look at alternative IDs and accept
+        // them too. Most of the ~250 countries have a small number of zones (most have 1-2, the max
+        // is ~30), and most zones do not have an alternative ID, those that do have 1-2.
         for (CountryTimeZones countryTimeZones : countryTimeZonesList) {
-            boolean match = TimeZoneMapping.containsTimeZoneId(
-                    countryTimeZones.getTimeZoneMappings(), zoneId);
+            boolean match = false;
+            // We get all time zone mappings, even those with a notafter= value to ensure the most
+            // complete search.
+            List<TimeZoneMapping> countryTimeZoneMappings = countryTimeZones.getTimeZoneMappings();
+            for (TimeZoneMapping timeZoneMapping : countryTimeZoneMappings) {
+                if (timeZoneMapping.getTimeZoneId().equals(zoneId)
+                        || timeZoneMapping.getAlternativeIds().contains(zoneId)) {
+                    match = true;
+                    break;
+                }
+            }
             if (match) {
                 matches.add(countryTimeZones);
             }
diff --git a/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/TimeZoneFinder.java b/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/TimeZoneFinder.java
index e0621a6..bf04b1b 100644
--- a/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/TimeZoneFinder.java
+++ b/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/TimeZoneFinder.java
@@ -24,6 +24,7 @@
 import static com.android.i18n.timezone.XmlUtils.normalizeCountryIso;
 import static com.android.i18n.timezone.XmlUtils.parseBooleanAttribute;
 import static com.android.i18n.timezone.XmlUtils.parseLongAttribute;
+import static com.android.i18n.timezone.XmlUtils.parseStringListAttribute;
 
 import org.xmlpull.v1.XmlPullParser;
 import org.xmlpull.v1.XmlPullParserException;
@@ -68,14 +69,17 @@
     private static final String EVER_USES_UTC_ATTRIBUTE = "everutc";
 
     // Country -> Time zone mapping. e.g. <id>ZoneId</id>, <id picker="n">ZoneId</id>,
-    // <id notafter={timestamp}>ZoneId</id>
+    // <id notafter={timestamp} alts="{alternative ids}">ZoneId</id>
     // The default for the picker attribute when unspecified is "y".
     // The notafter attribute is optional. It specifies a timestamp (time in milliseconds from Unix
     // epoch start) after which the zone is not (effectively) in use. If unspecified the zone is in
     // use forever.
+    // The alts attribute is optional. It contains a comma-separated String of alternative IDs that
+    // are exact synonyms for the ZoneId.
     private static final String ZONE_ID_ELEMENT = "id";
     private static final String ZONE_SHOW_IN_PICKER_ATTRIBUTE = "picker";
     private static final String ZONE_NOT_USED_AFTER_ATTRIBUTE = "notafter";
+    private static final String ZONE_ALTERNATIVE_IDS_ATTRIBUTE = "alts";
 
     private static TimeZoneFinder instance;
 
@@ -352,6 +356,8 @@
                     parser, ZONE_SHOW_IN_PICKER_ATTRIBUTE, true /* defaultValue */);
             Long notUsedAfter = parseLongAttribute(
                     parser, ZONE_NOT_USED_AFTER_ATTRIBUTE, null /* defaultValue */);
+            List<String> alternativeIds = parseStringListAttribute(
+                    parser, ZONE_ALTERNATIVE_IDS_ATTRIBUTE, Collections.emptyList());
             String zoneIdString = consumeText(parser);
 
             // Make sure we are on the </id> element.
@@ -364,7 +370,7 @@
             }
 
             TimeZoneMapping timeZoneMapping =
-                    new TimeZoneMapping(zoneIdString, showInPicker, notUsedAfter);
+                    new TimeZoneMapping(zoneIdString, showInPicker, notUsedAfter, alternativeIds);
             timeZoneMappings.add(timeZoneMapping);
         }
 
diff --git a/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/XmlUtils.java b/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/XmlUtils.java
index 9ff0a68..fc2535d 100644
--- a/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/XmlUtils.java
+++ b/android_icu4j/libcore_bridge/src/java/com/android/i18n/timezone/XmlUtils.java
@@ -27,7 +27,10 @@
 import java.nio.file.Files;
 import java.nio.file.Path;
 import java.nio.file.Paths;
+import java.util.ArrayList;
+import java.util.List;
 import java.util.Locale;
+import java.util.StringTokenizer;
 
 class XmlUtils {
 
@@ -76,6 +79,26 @@
     }
 
     /**
+     * Parses an attribute value, which must be either {@code null} or a comma-separated String
+     * list. There is no support for escaping the comma. If the attribute value is {@code null} then
+     * {@code defaultValue} is returned.
+     */
+    static List<String> parseStringListAttribute(XmlPullParser parser, String attributeName,
+            List<String> defaultValue) throws XmlPullParserException {
+        String attributeValueString = parser.getAttributeValue(null /* namespace */, attributeName);
+        if (attributeValueString == null) {
+            return defaultValue;
+        }
+        StringTokenizer stringTokenizer = new StringTokenizer(attributeValueString, ",", false);
+        ArrayList<String> strings = new ArrayList<>();
+        while (stringTokenizer.hasMoreTokens()) {
+            strings.add(stringTokenizer.nextToken());
+        }
+        strings.trimToSize();
+        return strings;
+    }
+
+    /**
      * Advances the the parser to the START_TAG for the specified element without decreasing the
      * depth, or increasing the depth by more than one (i.e. no recursion into child nodes).
      * If the next (non-nested) END_TAG an exception is thrown. Throws an exception if the end of
diff --git a/android_icu4j/testing/src/com/android/i18n/test/timezone/CountryTimeZonesTest.java b/android_icu4j/testing/src/com/android/i18n/test/timezone/CountryTimeZonesTest.java
index 71f1074..7d78f93 100644
--- a/android_icu4j/testing/src/com/android/i18n/test/timezone/CountryTimeZonesTest.java
+++ b/android_icu4j/testing/src/com/android/i18n/test/timezone/CountryTimeZonesTest.java
@@ -23,6 +23,7 @@
 
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.List;
 import java.util.Objects;
 import java.util.function.Function;
@@ -31,6 +32,7 @@
 import com.android.i18n.timezone.CountryTimeZones.OffsetResult;
 import com.android.i18n.timezone.CountryTimeZones.TimeZoneMapping;
 
+import static java.util.Collections.emptyList;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNull;
@@ -481,7 +483,7 @@
     @Test
     public void timeZoneMapping_getTimeZone_badZoneId() {
         TimeZoneMapping timeZoneMapping =
-                TimeZoneMapping.createForTests("DOES_NOT_EXIST", true, 1234L);
+                TimeZoneMapping.createForTests("DOES_NOT_EXIST", true, 1234L, list());
         try {
             timeZoneMapping.getTimeZone();
             fail();
@@ -492,7 +494,7 @@
     @Test
     public void timeZoneMapping_getTimeZone_validZoneId() {
         TimeZoneMapping timeZoneMapping =
-                TimeZoneMapping.createForTests("Europe/London", true, 1234L);
+                TimeZoneMapping.createForTests("Europe/London", true, 1234L, list());
         TimeZone timeZone = timeZoneMapping.getTimeZone();
         assertTrue(timeZone.isFrozen());
         assertEquals("Europe/London", timeZone.getID());
@@ -531,7 +533,7 @@
      */
     private static TimeZoneMapping timeZoneMapping(String timeZoneId, Long notUsedAfterMillis) {
         return TimeZoneMapping.createForTests(
-                        timeZoneId, true /* picker */, notUsedAfterMillis);
+                        timeZoneId, true /* picker */, notUsedAfterMillis, list());
     }
 
     /**
@@ -539,8 +541,7 @@
      */
     private static List<TimeZoneMapping> timeZoneMappings(String... timeZoneIds) {
         return Arrays.stream(timeZoneIds)
-                .map(x -> TimeZoneMapping.createForTests(
-                        x, true /* picker */, null /* notUsedAfter */))
+                .map(x -> timeZoneMapping(x, null /* notUsedAfter */))
                 .collect(Collectors.toList());
     }
 
diff --git a/android_icu4j/testing/src/com/android/i18n/test/timezone/CountryZonesFinderTest.java b/android_icu4j/testing/src/com/android/i18n/test/timezone/CountryZonesFinderTest.java
index 62a8624..64ec0fd 100644
--- a/android_icu4j/testing/src/com/android/i18n/test/timezone/CountryZonesFinderTest.java
+++ b/android_icu4j/testing/src/com/android/i18n/test/timezone/CountryZonesFinderTest.java
@@ -19,6 +19,7 @@
 import org.junit.Test;
 
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.List;
 import java.util.stream.Collectors;
 import com.android.i18n.timezone.CountryTimeZones;
@@ -36,19 +37,19 @@
 public class CountryZonesFinderTest {
 
     private static final CountryTimeZones GB_ZONES = CountryTimeZones.createValidated(
-            "gb", "Europe/London", false /* defaultTimeZoneBoost */, true,
+            "gb", "Europe/London", false /* defaultTimeZoneBoost */, true /* everUsesUtc */,
             timeZoneMappings("Europe/London"), "test");
 
     private static final CountryTimeZones IM_ZONES = CountryTimeZones.createValidated(
-            "im", "Europe/London", false /* defaultTimeZoneBoost */, true,
+            "im", "Europe/London", false /* defaultTimeZoneBoost */, true  /* everUsesUtc */,
             timeZoneMappings("Europe/London"), "test");
 
     private static final CountryTimeZones FR_ZONES = CountryTimeZones.createValidated(
-            "fr", "Europe/Paris", false /* defaultTimeZoneBoost */, true,
+            "fr", "Europe/Paris", false /* defaultTimeZoneBoost */, true  /* everUsesUtc */,
             timeZoneMappings("Europe/Paris"), "test");
 
     private static final CountryTimeZones US_ZONES = CountryTimeZones.createValidated(
-            "us", "America/New_York", false /* defaultTimeZoneBoost */, true,
+            "us", "America/New_York", false /* defaultTimeZoneBoost */, false  /* everUsesUtc */,
             timeZoneMappings("America/New_York", "America/Los_Angeles"), "test");
 
     @Test
@@ -83,6 +84,33 @@
     }
 
     @Test
+    public void lookupCountryCodesForZoneId_alternativeIds() throws Exception {
+        TimeZoneMapping usesNewZoneId = timeZoneMappingWithAlts("America/Detroit",
+                list("US/Michigan"));
+        TimeZoneMapping usesOldZoneId = timeZoneMappingWithAlts("US/Central",
+                list("America/Chicago"));
+        CountryTimeZones countryWithAlternativeZones = CountryTimeZones.createValidated(
+                "us", "America/Detroit" /* defaultTimeZoneId */, false /* defaultTimeZoneBoost */,
+                false /* everUsesUtc */,
+                list(usesNewZoneId, usesOldZoneId),
+                "debug info");
+
+        CountryZonesFinder countryZonesFinder = CountryZonesFinder.createForTests(
+                list(GB_ZONES, IM_ZONES, FR_ZONES, countryWithAlternativeZones));
+
+        assertEqualsAndImmutable(list(countryWithAlternativeZones),
+                countryZonesFinder.lookupCountryTimeZonesForZoneId("America/Detroit"));
+        assertEqualsAndImmutable(list(countryWithAlternativeZones),
+                countryZonesFinder.lookupCountryTimeZonesForZoneId("US/Michigan"));
+        assertEqualsAndImmutable(list(countryWithAlternativeZones),
+                countryZonesFinder.lookupCountryTimeZonesForZoneId("US/Central"));
+        assertEqualsAndImmutable(list(countryWithAlternativeZones),
+                countryZonesFinder.lookupCountryTimeZonesForZoneId("America/Chicago"));
+        assertEqualsAndImmutable(list(),
+                countryZonesFinder.lookupCountryTimeZonesForZoneId("DOES_NOT_EXIST"));
+    }
+
+    @Test
     public void lookupCountryTimeZones() throws Exception {
         CountryZonesFinder countryZonesFinder =
                 CountryZonesFinder.createForTests(list(GB_ZONES, IM_ZONES, FR_ZONES, US_ZONES));
@@ -113,8 +141,16 @@
      */
     private static List<TimeZoneMapping> timeZoneMappings(String... timeZoneIds) {
         return Arrays.stream(timeZoneIds)
-                .map(x -> TimeZoneMapping.createForTests(
-                        x, true /* picker */, null /* notUsedAfter */))
+                .map(x -> timeZoneMappingWithAlts(x, Collections.emptyList()))
                 .collect(Collectors.toList());
     }
+
+    /**
+     * Creates a {@link TimeZoneMapping} object with the specified time zone ID and alternative IDs.
+     */
+    private static TimeZoneMapping timeZoneMappingWithAlts(
+            String timeZoneId, List<String> alternativeIds) {
+        return TimeZoneMapping.createForTests(
+                timeZoneId, true /* picker */, null /* notUsedAfter */, alternativeIds);
+    }
 }
diff --git a/android_icu4j/testing/src/com/android/i18n/test/timezone/TimeZoneFinderTest.java b/android_icu4j/testing/src/com/android/i18n/test/timezone/TimeZoneFinderTest.java
index a850419..8ebeebb 100644
--- a/android_icu4j/testing/src/com/android/i18n/test/timezone/TimeZoneFinderTest.java
+++ b/android_icu4j/testing/src/com/android/i18n/test/timezone/TimeZoneFinderTest.java
@@ -460,19 +460,24 @@
                 + "      <id>America/Los_Angeles</id>\n"
                 + "      <!-- Explicit picker=\"n\" -->\n"
                 + "      <id picker=\"n\">America/Indiana/Vincennes</id>\n"
+                + "      <!-- Explicit notafter=\"1234\" alts=\"abc,def\"-->\n"
+                + "      <id notafter=\"972802800000\" alts=\"America/New_York\">"
+                + "America/Kentucky/Monticello</id>\n"
                 + "    </country>\n"
                 + "  </countryzones>\n"
                 + "</timezones>\n");
         CountryTimeZones usTimeZones = finder.lookupCountryTimeZones("us");
         List<TimeZoneMapping> actualTimeZoneMappings = usTimeZones.getTimeZoneMappings();
         List<TimeZoneMapping> expectedTimeZoneMappings = list(
-                TimeZoneMapping.createForTests(
-                        "America/New_York", true /* shownInPicker */, null /* notUsedAfter */),
-                TimeZoneMapping.createForTests(
-                        "America/Los_Angeles", true /* shownInPicker */, null /* notUsedAfter */),
-                TimeZoneMapping.createForTests(
-                        "America/Indiana/Vincennes", false /* shownInPicker */,
-                        null /* notUsedAfter */)
+                TimeZoneMapping.createForTests("America/New_York", true /* shownInPicker */,
+                        null /* notUsedAfter */, list()),
+                TimeZoneMapping.createForTests("America/Los_Angeles", true /* shownInPicker */,
+                        null /* notUsedAfter */, list()),
+                TimeZoneMapping.createForTests("America/Indiana/Vincennes",
+                        false /* shownInPicker */, null /* notUsedAfter */, list()),
+                TimeZoneMapping.createForTests("America/Kentucky/Monticello",
+                        true /* shownInPicker */, 972802800000L /* notUsedAfter */,
+                        list("America/New_York"))
         );
         assertEquals(expectedTimeZoneMappings, actualTimeZoneMappings);
     }
@@ -503,11 +508,10 @@
         CountryTimeZones usTimeZones = finder.lookupCountryTimeZones("us");
         List<TimeZoneMapping> actualTimeZoneMappings = usTimeZones.getTimeZoneMappings();
         List<TimeZoneMapping> expectedTimeZoneMappings = list(
-                TimeZoneMapping.createForTests(
-                        "America/New_York", true /* shownInPicker */, 1234L /* notUsedAfter */),
-                TimeZoneMapping.createForTests(
-                        "America/Indiana/Vincennes", true /* shownInPicker */,
-                        null /* notUsedAfter */)
+                TimeZoneMapping.createForTests("America/New_York", true /* shownInPicker */,
+                        1234L /* notUsedAfter */, list()),
+                TimeZoneMapping.createForTests("America/Indiana/Vincennes",
+                        true /* shownInPicker */, null /* notUsedAfter */, list())
         );
         assertEquals(expectedTimeZoneMappings, actualTimeZoneMappings);
     }
@@ -638,7 +642,7 @@
     private static List<TimeZoneMapping> timeZoneMappings(String... timeZoneIds) {
         return Arrays.stream(timeZoneIds)
                 .map(x -> TimeZoneMapping.createForTests(
-                        x, true /* showInPicker */, null /* notUsedAfter */))
+                        x, true /* showInPicker */, null /* notUsedAfter */, list()))
                 .collect(Collectors.toList());
     }