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