1 /* 2 * Copyright (C) 2020 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package com.android.libcore.timezone.tzlookup; 17 18 import java.io.IOException; 19 import java.nio.charset.StandardCharsets; 20 import java.nio.file.Files; 21 import java.nio.file.Paths; 22 import java.text.ParseException; 23 import java.util.Collections; 24 import java.util.HashMap; 25 import java.util.HashSet; 26 import java.util.LinkedList; 27 import java.util.List; 28 import java.util.Map; 29 import java.util.Set; 30 import java.util.stream.Collectors; 31 32 /** 33 * A class that knows about the structure of the IANA tzdb backward file. 34 */ 35 final class BackwardFile { 36 37 private final Map<String, String> links = new HashMap<>(); 38 private Map<String, String> directLinks; 39 BackwardFile()40 private BackwardFile() {} 41 parse(String backwardFile)42 static BackwardFile parse(String backwardFile) throws IOException, ParseException { 43 BackwardFile backward = new BackwardFile(); 44 45 List<String> lines = Files 46 .readAllLines(Paths.get(backwardFile), StandardCharsets.US_ASCII); 47 48 // Remove comments 49 List<String> linkLines = 50 lines.stream() 51 .filter(s -> !(s.startsWith("#") || s.isEmpty())) 52 .collect(Collectors.toList()); 53 54 for (String linkLine : linkLines) { 55 String[] fields = linkLine.split("\t+"); 56 if (fields.length < 3 || !fields[0].equals("Link")) { 57 throw new ParseException("Line is malformed: " + linkLine, 0); 58 } 59 backward.addLink(fields[1], fields[2]); 60 } 61 return backward; 62 } 63 64 /** 65 * Add a link entry. 66 * 67 * @param target the new tz ID 68 * @param linkName the old tz ID 69 */ addLink(String target, String linkName)70 private void addLink(String target, String linkName) { 71 String oldValue = links.put(linkName, target); 72 if (oldValue != null) { 73 throw new IllegalStateException("Duplicate link from " + linkName); 74 } 75 } 76 77 /** 78 * Returns a set of IDs linked to the supplied ID, even intermediate ones in a chain of links. 79 */ getAllAlternativeIds(String zoneId)80 Set<String> getAllAlternativeIds(String zoneId) { 81 Set<String> knownAlternativeIds = new HashSet<>(); 82 // Add the ID we're searching for. We don't need to look for it. 83 knownAlternativeIds.add(zoneId); 84 85 LinkedList<String> searchIdQueue = new LinkedList<>(); 86 searchIdQueue.add(zoneId); 87 while (!searchIdQueue.isEmpty()) { 88 String searchId = searchIdQueue.removeLast(); 89 for (Map.Entry<String, String> entry : links.entrySet()) { 90 String fromId = entry.getKey(); 91 String toId = entry.getValue(); 92 if (fromId.equals(searchId)) { 93 if (knownAlternativeIds.add(toId)) { 94 searchIdQueue.add(toId); 95 } 96 } else if (toId.equals(searchId)) { 97 if (knownAlternativeIds.add(fromId)) { 98 searchIdQueue.add(fromId); 99 } 100 } 101 } 102 } 103 104 // Remove the zone we were searching for - it's not an alternative for itself. 105 knownAlternativeIds.remove(zoneId); 106 return Collections.unmodifiableSet(knownAlternativeIds); 107 } 108 getLinks()109 Map<String, String> getLinks() { 110 return Collections.unmodifiableMap(links); 111 } 112 113 /** Returns a mapping from linkName (old tz ID) to target (new tz ID). */ getDirectLinks()114 Map<String, String> getDirectLinks() { 115 if (directLinks == null) { 116 // Validate links for cycles and collapse the links to remove intermediates if there are 117 // links to links. There's a simple check to confirm that no chain is longer than a 118 // fixed length, to guard against cycles. 119 final int maxChainLength = 2; 120 Map<String, String> collapsedLinks = new HashMap<>(); 121 for (String fromId : links.keySet()) { 122 int chainLength = 0; 123 String currentId = fromId; 124 String lastId = null; 125 while ((currentId = links.get(currentId)) != null) { 126 chainLength++; 127 lastId = currentId; 128 if (chainLength > maxChainLength) { 129 throw new IllegalStateException( 130 "Chain from " + fromId + " is longer than " + maxChainLength); 131 } 132 } 133 if (chainLength == 0) { 134 throw new IllegalStateException("Null Link targetId for " + fromId); 135 } 136 collapsedLinks.put(fromId, lastId); 137 } 138 directLinks = Collections.unmodifiableMap(collapsedLinks); 139 } 140 return directLinks; 141 } 142 } 143