1 /*
   2  * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 
  27 package build.tools.tzdb;
  28 
  29 import java.io.IOException;
  30 import java.nio.charset.StandardCharsets;
  31 import java.nio.file.Files;
  32 import java.nio.file.Path;
  33 import java.nio.file.Paths;
  34 import java.util.ArrayList;
  35 import java.util.Collections;
  36 import java.util.HashMap;
  37 import java.util.HashSet;
  38 import java.util.List;
  39 import java.util.Map;
  40 import java.util.Map.Entry;
  41 import java.util.NavigableMap;
  42 import java.util.Objects;
  43 import java.util.Set;
  44 import java.util.TreeMap;
  45 import java.util.TreeSet;
  46 import java.util.concurrent.ConcurrentHashMap;
  47 import java.time.*;
  48 import java.time.Year;
  49 import java.time.chrono.IsoChronology;
  50 import java.time.temporal.TemporalAdjusters;
  51 import java.time.zone.ZoneOffsetTransition;
  52 import java.time.zone.ZoneOffsetTransitionRule;
  53 import java.time.zone.ZoneOffsetTransitionRule.TimeDefinition;
  54 import java.time.zone.ZoneRulesException;
  55 
  56 /**
  57  * Compile and build time-zone rules from IANA timezone data
  58  *
  59  * @author Xueming Shen
  60  * @author Stephen Colebourne
  61  * @author Michael Nascimento Santos
  62  *
  63  * @since   1.9
  64  */
  65 
  66 class TzdbZoneRulesProvider {
  67 
  68     /**
  69      * Creates an instance.
  70      *
  71      * @throws ZoneRulesException if unable to load
  72      */
  73     public TzdbZoneRulesProvider(List<Path> files) {
  74         try {
  75              load(files);
  76         } catch (Exception ex) {
  77             throw new ZoneRulesException("Unable to load TZDB time-zone rules", ex);
  78         }
  79     }
  80 
  81     public Set<String> getZoneIds() {
  82         return new TreeSet(regionIds);
  83     }
  84 
  85     public Map<String, String> getAliasMap() {
  86         return links;
  87     }
  88 
  89     public ZoneRules getZoneRules(String zoneId) {
  90         Object obj = zones.get(zoneId);
  91         if (obj == null) {
  92             String zoneId0 = zoneId;
  93             if (links.containsKey(zoneId)) {
  94                 zoneId = links.get(zoneId);
  95                 obj = zones.get(zoneId);
  96             }
  97             if (obj == null) {
  98                 // Timezone link can be located in 'backward' file and it
  99                 // can refer to another link, so we need to check for
 100                 // link one more time, before throwing an exception
 101                 String zoneIdBack = zoneId;
 102                 if (links.containsKey(zoneId)) {
 103                     zoneId = links.get(zoneId);
 104                     obj = zones.get(zoneId);
 105                 }
 106                 if (obj == null) {
 107                     throw new ZoneRulesException("Unknown time-zone ID: " + zoneIdBack);
 108                 }
 109             }
 110         }
 111         if (obj instanceof ZoneRules) {
 112             return (ZoneRules)obj;
 113         }
 114         try {
 115             ZoneRules zrules = buildRules(zoneId, (List<ZoneLine>)obj);
 116             zones.put(zoneId, zrules);
 117             return zrules;
 118         } catch (Exception ex) {
 119             throw new ZoneRulesException(
 120                 "Invalid binary time-zone data: TZDB:" + zoneId, ex);
 121         }
 122     }
 123 
 124     //////////////////////////////////////////////////////////////////////
 125 
 126     /**
 127      * All the regions that are available.
 128      */
 129     private List<String> regionIds = new ArrayList<>(600);
 130 
 131     /**
 132      * Zone region to rules mapping
 133      */
 134     private final Map<String, Object> zones = new ConcurrentHashMap<>();
 135 
 136     /**
 137      * compatibility list
 138      */
 139     private static HashSet<String> excludedZones;
 140     static {
 141         // (1) exclude EST, HST and MST. They are supported
 142         //     via the short-id mapping
 143         // (2) remove UTC and GMT
 144         // (3) remove ROC, which is not supported in j.u.tz
 145         excludedZones = new HashSet<>(10);
 146         excludedZones.add("EST");
 147         excludedZones.add("HST");
 148         excludedZones.add("MST");
 149         excludedZones.add("GMT+0");
 150         excludedZones.add("GMT-0");
 151         excludedZones.add("ROC");
 152     }
 153 
 154     private Map<String, String> links = new HashMap<>(150);
 155     private Map<String, List<RuleLine>> rules = new HashMap<>(500);
 156 
 157     private void load(List<Path> files) throws IOException {
 158 
 159         for (Path file : files) {
 160             List<ZoneLine> openZone = null;
 161             try {
 162                 for (String line : Files.readAllLines(file, StandardCharsets.ISO_8859_1)) {
 163                     if (line.length() == 0 || line.charAt(0) == '#') {
 164                         continue;
 165                     }
 166                     //StringIterator itr = new StringIterator(line);
 167                     String[] tokens = split(line);
 168                     if (openZone != null &&               // continuing zone line
 169                         Character.isWhitespace(line.charAt(0)) &&
 170                         tokens.length > 0) {
 171                         ZoneLine zLine = new ZoneLine();
 172                         openZone.add(zLine);
 173                         if (zLine.parse(tokens, 0)) {
 174                             openZone = null;
 175                         }
 176                         continue;
 177                     }
 178                     if (line.startsWith("Zone")) {        // parse Zone line
 179                         String name = tokens[1];
 180                         if (excludedZones.contains(name)){
 181                             continue;
 182                         }
 183                         if (zones.containsKey(name)) {
 184                             throw new IllegalArgumentException(
 185                                 "Duplicated zone name in file: " + name +
 186                                 ", line: [" + line + "]");
 187                         }
 188                         openZone = new ArrayList<>(10);
 189                         zones.put(name, openZone);
 190                         regionIds.add(name);
 191                         ZoneLine zLine = new ZoneLine();
 192                         openZone.add(zLine);
 193                         if (zLine.parse(tokens, 2)) {
 194                             openZone = null;
 195                         }
 196                     } else if (line.startsWith("Rule")) { // parse Rule line
 197                         String name = tokens[1];
 198                         if (!rules.containsKey(name)) {
 199                             rules.put(name, new ArrayList<RuleLine>(10));
 200                         }
 201                         rules.get(name).add(new RuleLine().parse(tokens));
 202                     } else if (line.startsWith("Link")) { // parse link line
 203                         if (tokens.length >= 3) {
 204                             String realId = tokens[1];
 205                             String aliasId = tokens[2];
 206                             if (excludedZones.contains(aliasId)){
 207                                 continue;
 208                             }
 209                             links.put(aliasId, realId);
 210                             regionIds.add(aliasId);
 211                         } else {
 212                             throw new IllegalArgumentException(
 213                                 "Invalid Link line in file" +
 214                                 file + ", line: [" + line + "]");
 215                         }
 216                     } else {
 217                         // skip unknown line
 218                     }
 219                 }
 220 
 221             } catch (Exception ex) {
 222                 throw new RuntimeException("Failed while processing file [" + file +
 223                                            "]", ex);
 224             }
 225         }
 226     }
 227 
 228     private String[] split(String str) {
 229         int off = 0;
 230         int end = str.length();
 231         ArrayList<String> list = new ArrayList<>(10);
 232         while (off < end) {
 233             char c = str.charAt(off);
 234             if (c == '\t' || c == ' ') {
 235                 off++;
 236                 continue;
 237             }
 238             if (c == '#') {    // comment
 239                 break;
 240             }
 241             int start = off;
 242             while (off < end) {
 243                 c = str.charAt(off);
 244                 if (c == ' ' || c == '\t') {
 245                     break;
 246                 }
 247                 off++;
 248             }
 249             if (start != off) {
 250                 list.add(str.substring(start, off));
 251             }
 252         }
 253         return list.toArray(new String[list.size()]);
 254     }
 255 
 256     /**
 257      * Class representing a month-day-time in the TZDB file.
 258      */
 259     private static abstract class MonthDayTime {
 260         /** The month of the cutover. */
 261         Month month = Month.JANUARY;
 262 
 263         /** The day-of-month of the cutover. */
 264         int dayOfMonth = 1;
 265 
 266         /** Whether to adjust forwards. */
 267         boolean adjustForwards = true;
 268 
 269         /** The day-of-week of the cutover. */
 270         DayOfWeek dayOfWeek;
 271 
 272         /** The time of the cutover, in second of day */
 273         int secsOfDay = 0;
 274 
 275         /** Whether this is midnight end of day. */
 276         boolean endOfDay;
 277         /** The time of the cutover. */
 278 
 279         TimeDefinition timeDefinition = TimeDefinition.WALL;
 280 
 281         void adjustToForwards(int year) {
 282             if (adjustForwards == false && dayOfMonth > 0) {
 283                 // weekDay<=monthDay case, don't have it in tzdb data for now
 284                 LocalDate adjustedDate = LocalDate.of(year, month, dayOfMonth).minusDays(6);
 285                 dayOfMonth = adjustedDate.getDayOfMonth();
 286                 month = adjustedDate.getMonth();
 287                 adjustForwards = true;
 288             }
 289         }
 290 
 291         LocalDateTime toDateTime(int year) {
 292             LocalDate date;
 293             if (dayOfMonth < 0) {
 294                 int monthLen = month.length(IsoChronology.INSTANCE.isLeapYear(year));
 295                 date = LocalDate.of(year, month, monthLen + 1 + dayOfMonth);
 296                 if (dayOfWeek != null) {
 297                     date = date.with(TemporalAdjusters.previousOrSame(dayOfWeek));
 298                 }
 299             } else {
 300                 date = LocalDate.of(year, month, dayOfMonth);
 301                 if (dayOfWeek != null) {
 302                     date = date.with(TemporalAdjusters.nextOrSame(dayOfWeek));
 303                 }
 304             }
 305             if (endOfDay) {
 306                 date = date.plusDays(1);
 307             }
 308             return LocalDateTime.of(date, LocalTime.ofSecondOfDay(secsOfDay));
 309         }
 310 
 311         /**
 312          * Parses the MonthDaytime segment of a tzdb line.
 313          */
 314         private void parse(String[] tokens, int off) {
 315             month = parseMonth(tokens[off++]);
 316             if (off < tokens.length) {
 317                 String dayRule = tokens[off++];
 318                 if (dayRule.startsWith("last")) {
 319                     dayOfMonth = -1;
 320                     dayOfWeek = parseDayOfWeek(dayRule.substring(4));
 321                     adjustForwards = false;
 322                 } else {
 323                     int index = dayRule.indexOf(">=");
 324                     if (index > 0) {
 325                         dayOfWeek = parseDayOfWeek(dayRule.substring(0, index));
 326                         dayRule = dayRule.substring(index + 2);
 327                     } else {
 328                         index = dayRule.indexOf("<=");
 329                         if (index > 0) {
 330                             dayOfWeek = parseDayOfWeek(dayRule.substring(0, index));
 331                             adjustForwards = false;
 332                             dayRule = dayRule.substring(index + 2);
 333                         }
 334                     }
 335                     dayOfMonth = Integer.parseInt(dayRule);
 336                     if (dayOfMonth < -28 || dayOfMonth > 31 || dayOfMonth == 0) {
 337                        throw new IllegalArgumentException(
 338                           "Day of month indicator must be between -28 and 31 inclusive excluding zero");
 339                     }
 340                 }
 341                 if (off < tokens.length) {
 342                     String timeStr = tokens[off++];
 343                     secsOfDay = parseSecs(timeStr);
 344                     if (secsOfDay == 86400) {
 345                         // time must be midnight when end of day flag is true
 346                         endOfDay = true;
 347                         secsOfDay = 0;
 348                     }
 349                     timeDefinition = parseTimeDefinition(timeStr.charAt(timeStr.length() - 1));
 350                 }
 351             }
 352         }
 353 
 354         int parseYear(String year, int defaultYear) {
 355             switch (year.toLowerCase()) {
 356             case "min":  return 1900;
 357             case "max":  return Year.MAX_VALUE;
 358             case "only": return defaultYear;
 359             }
 360             return Integer.parseInt(year);
 361         }
 362 
 363         Month parseMonth(String mon) {
 364             switch (mon) {
 365             case "Jan": return Month.JANUARY;
 366             case "Feb": return Month.FEBRUARY;
 367             case "Mar": return Month.MARCH;
 368             case "Apr": return Month.APRIL;
 369             case "May": return Month.MAY;
 370             case "Jun": return Month.JUNE;
 371             case "Jul": return Month.JULY;
 372             case "Aug": return Month.AUGUST;
 373             case "Sep": return Month.SEPTEMBER;
 374             case "Oct": return Month.OCTOBER;
 375             case "Nov": return Month.NOVEMBER;
 376             case "Dec": return Month.DECEMBER;
 377             }
 378             throw new IllegalArgumentException("Unknown month: " + mon);
 379         }
 380 
 381         DayOfWeek parseDayOfWeek(String dow) {
 382             switch (dow) {
 383             case "Mon": return DayOfWeek.MONDAY;
 384             case "Tue": return DayOfWeek.TUESDAY;
 385             case "Wed": return DayOfWeek.WEDNESDAY;
 386             case "Thu": return DayOfWeek.THURSDAY;
 387             case "Fri": return DayOfWeek.FRIDAY;
 388             case "Sat": return DayOfWeek.SATURDAY;
 389             case "Sun": return DayOfWeek.SUNDAY;
 390             }
 391             throw new IllegalArgumentException("Unknown day-of-week: " + dow);
 392         }
 393 
 394         String parseOptional(String str) {
 395             return str.equals("-") ? null : str;
 396         }
 397 
 398         static final boolean isDigit(char c) {
 399             return c >= '0' && c <= '9';
 400         }
 401 
 402         private int parseSecs(String time) {
 403             if (time.equals("-")) {
 404                 return 0;
 405             }
 406             // faster hack
 407             int secs = 0;
 408             int sign = 1;
 409             int off = 0;
 410             int len = time.length();
 411             if (off < len && time.charAt(off) == '-') {
 412                 sign = -1;
 413                 off++;
 414             }
 415             char c0, c1;
 416             if (off < len && isDigit(c0 = time.charAt(off++))) {
 417                 int hour = c0 - '0';
 418                 if (off < len && isDigit(c1 = time.charAt(off))) {
 419                     hour = hour * 10 + c1 - '0';
 420                     off++;
 421                 }
 422                 secs = hour * 60 * 60;
 423                 if (off < len && time.charAt(off++) == ':') {
 424                     if (off + 1 < len &&
 425                         isDigit(c0 = time.charAt(off++)) &&
 426                         isDigit(c1 = time.charAt(off++))) {
 427                         // minutes
 428                         secs += ((c0 - '0') * 10 + c1 - '0') * 60;
 429                         if (off < len && time.charAt(off++) == ':') {
 430                             if (off + 1 < len &&
 431                                 isDigit(c0 = time.charAt(off++)) &&
 432                                 isDigit(c1 = time.charAt(off++))) {
 433                                 // seconds
 434                                 secs += ((c0 - '0') * 10 + c1 - '0');
 435                             }
 436                         }
 437                     }
 438 
 439                 }
 440                 return secs * sign;
 441             }
 442             throw new IllegalArgumentException("[" + time + "]");
 443         }
 444 
 445         int parseOffset(String str) {
 446             int secs = parseSecs(str);
 447             if (Math.abs(secs) > 18 * 60 * 60) {
 448                 throw new IllegalArgumentException(
 449                     "Zone offset not in valid range: -18:00 to +18:00");
 450             }
 451             return secs;
 452         }
 453 
 454         int parsePeriod(String str) {
 455             return parseSecs(str);
 456         }
 457 
 458         TimeDefinition parseTimeDefinition(char c) {
 459             switch (c) {
 460             case 's':
 461             case 'S':
 462                 // standard time
 463                 return TimeDefinition.STANDARD;
 464             case 'u':
 465             case 'U':
 466             case 'g':
 467             case 'G':
 468             case 'z':
 469             case 'Z':
 470                 // UTC
 471                 return TimeDefinition.UTC;
 472             case 'w':
 473             case 'W':
 474             default:
 475                 // wall time
 476                 return TimeDefinition.WALL;
 477             }
 478         }
 479     }
 480 
 481     /**
 482      * Class representing a rule line in the TZDB file.
 483      */
 484     private static class RuleLine extends MonthDayTime {
 485         /** The start year. */
 486         int startYear;
 487 
 488         /** The end year. */
 489         int endYear;
 490 
 491         /** The amount of savings, in seconds. */
 492         int savingsAmount;
 493 
 494         /** The text name of the zone. */
 495         String text;
 496 
 497         /**
 498          * Converts this to a transition rule.
 499          *
 500          * @param standardOffset  the active standard offset, not null
 501          * @param savingsBeforeSecs  the active savings before the transition in seconds
 502          * @return the transition, not null
 503         */
 504         ZoneOffsetTransitionRule toTransitionRule(ZoneOffset stdOffset, int savingsBefore) {
 505             // rule shared by different zones, so don't change it
 506             Month month = this.month;
 507             int dayOfMonth = this.dayOfMonth;
 508             DayOfWeek dayOfWeek = this.dayOfWeek;
 509             boolean endOfDay = this.endOfDay;
 510 
 511             // optimize stored format
 512             if (dayOfMonth < 0) {
 513                 if (month != Month.FEBRUARY) {    // not Month.FEBRUARY
 514                     dayOfMonth = month.maxLength() - 6;
 515                 }
 516             }
 517             if (endOfDay && dayOfMonth > 0 &&
 518                 (dayOfMonth == 28 && month == Month.FEBRUARY) == false) {
 519                 LocalDate date = LocalDate.of(2004, month, dayOfMonth).plusDays(1);  // leap-year
 520                 month = date.getMonth();
 521                 dayOfMonth = date.getDayOfMonth();
 522                 if (dayOfWeek != null) {
 523                     dayOfWeek = dayOfWeek.plus(1);
 524                 }
 525                 endOfDay = false;
 526             }
 527             // build rule
 528             return ZoneOffsetTransitionRule.of(
 529                     //month, dayOfMonth, dayOfWeek, time, endOfDay, timeDefinition,
 530                     month, dayOfMonth, dayOfWeek,
 531                     LocalTime.ofSecondOfDay(secsOfDay), endOfDay, timeDefinition,
 532                     stdOffset,
 533                     ZoneOffset.ofTotalSeconds(stdOffset.getTotalSeconds() + savingsBefore),
 534                     ZoneOffset.ofTotalSeconds(stdOffset.getTotalSeconds() + savingsAmount));
 535         }
 536 
 537         RuleLine parse(String[] tokens) {
 538             startYear = parseYear(tokens[2], 0);
 539             endYear = parseYear(tokens[3], startYear);
 540             if (startYear > endYear) {
 541                 throw new IllegalArgumentException(
 542                     "Invalid <Rule> line/Year order invalid:" + startYear + " > " + endYear);
 543             }
 544             //parseOptional(s.next());  // type is unused
 545             super.parse(tokens, 5);     // monthdaytime parsing
 546             savingsAmount = parsePeriod(tokens[8]);
 547             //rule.text = parseOptional(s.next());
 548             return this;
 549         }
 550     }
 551 
 552     /**
 553      * Class representing a linked set of zone lines in the TZDB file.
 554      */
 555     private static class ZoneLine extends MonthDayTime {
 556         /** The standard offset. */
 557         int stdOffsetSecs;
 558 
 559         /** The fixed savings amount. */
 560         int fixedSavingsSecs = 0;
 561 
 562         /** The savings rule. */
 563         String savingsRule;
 564 
 565         /** The text name of the zone. */
 566         String text;
 567 
 568         /** The cutover year */
 569         int year = Year.MAX_VALUE;
 570 
 571         /** The cutover date time */
 572         LocalDateTime ldt;
 573 
 574         /** The cutover date/time in epoch seconds/UTC */
 575         long ldtSecs = Long.MIN_VALUE;
 576 
 577         LocalDateTime toDateTime() {
 578             if (ldt == null) {
 579                 ldt = toDateTime(year);
 580             }
 581             return ldt;
 582         }
 583 
 584         /**
 585          * Creates the date-time epoch second in the wall offset for the local
 586          * date-time at the end of the window.
 587          *
 588          * @param savingsSecs  the amount of savings in use in seconds
 589          * @return the created date-time epoch second in the wall offset, not null
 590          */
 591         long toDateTimeEpochSecond(int savingsSecs) {
 592             if (ldtSecs == Long.MIN_VALUE) {
 593                 ldtSecs = toDateTime().toEpochSecond(ZoneOffset.UTC);
 594             }
 595             switch(timeDefinition) {
 596             case UTC:      return ldtSecs;
 597             case STANDARD: return ldtSecs - stdOffsetSecs;
 598             default:       return ldtSecs - (stdOffsetSecs + savingsSecs); // WALL
 599             }
 600         }
 601 
 602         boolean parse(String[] tokens, int off) {
 603             stdOffsetSecs = parseOffset(tokens[off++]);
 604             savingsRule = parseOptional(tokens[off++]);
 605             if (savingsRule != null && savingsRule.length() > 0 &&
 606                 (savingsRule.charAt(0) == '-' || isDigit(savingsRule.charAt(0)))) {
 607                 try {
 608                     fixedSavingsSecs = parsePeriod(savingsRule);
 609                     savingsRule = null;
 610                 } catch (Exception ex) {
 611                     fixedSavingsSecs = 0;
 612                 }
 613             }
 614             text = tokens[off++];
 615             if (off < tokens.length) {
 616                 year = Integer.parseInt(tokens[off++]);
 617                 if (off < tokens.length) {
 618                     super.parse(tokens, off);  // MonthDayTime
 619                 }
 620                 return false;
 621             } else {
 622                 return true;
 623             }
 624         }
 625     }
 626 
 627     /**
 628      * Class representing a rule line in the TZDB file for a particular year.
 629      */
 630     private static class TransRule implements Comparable<TransRule>
 631     {
 632         private int year;
 633         private RuleLine rule;
 634 
 635         /** The trans date/time */
 636         private LocalDateTime ldt;
 637 
 638         /** The trans date/time in epoch seconds (assume UTC) */
 639         long ldtSecs;
 640 
 641         TransRule(int year, RuleLine rule) {
 642             this.year = year;
 643             this.rule = rule;
 644             this.ldt = rule.toDateTime(year);
 645             this.ldtSecs = ldt.toEpochSecond(ZoneOffset.UTC);
 646         }
 647 
 648         ZoneOffsetTransition toTransition(ZoneOffset standardOffset, int savingsBeforeSecs) {
 649             // copy of code in ZoneOffsetTransitionRule to avoid infinite loop
 650             ZoneOffset wallOffset = ZoneOffset.ofTotalSeconds(
 651                 standardOffset.getTotalSeconds() + savingsBeforeSecs);
 652             ZoneOffset offsetAfter = ZoneOffset.ofTotalSeconds(
 653                 standardOffset.getTotalSeconds() + rule.savingsAmount);
 654             LocalDateTime dt = rule.timeDefinition
 655                                    .createDateTime(ldt, standardOffset, wallOffset);
 656             return ZoneOffsetTransition.of(dt, wallOffset, offsetAfter);
 657         }
 658 
 659         long toEpochSecond(ZoneOffset stdOffset, int savingsBeforeSecs) {
 660             switch(rule.timeDefinition) {
 661             case UTC:      return ldtSecs;
 662             case STANDARD: return ldtSecs - stdOffset.getTotalSeconds();
 663             default:       return ldtSecs - (stdOffset.getTotalSeconds() + savingsBeforeSecs); // WALL
 664             }
 665         }
 666 
 667         /**
 668          * Tests if this a real transition with the active savings in seconds
 669          *
 670          * @param savingsBefore the active savings in seconds
 671          * @return true, if savings changes
 672          */
 673         boolean isTransition(int savingsBefore) {
 674             return rule.savingsAmount != savingsBefore;
 675         }
 676 
 677         public int compareTo(TransRule other) {
 678             return (ldtSecs < other.ldtSecs)? -1 : ((ldtSecs == other.ldtSecs) ? 0 : 1);
 679         }
 680     }
 681 
 682     private ZoneRules buildRules(String zoneId, List<ZoneLine> zones) {
 683         if (zones.isEmpty()) {
 684             throw new IllegalStateException("No available zone window");
 685         }
 686         final List<ZoneOffsetTransition> standardTransitionList = new ArrayList<>(4);
 687         final List<ZoneOffsetTransition> transitionList = new ArrayList<>(256);
 688         final List<ZoneOffsetTransitionRule> lastTransitionRuleList = new ArrayList<>(2);
 689 
 690         final ZoneLine zone0 = zones.get(0);
 691         // initialize the standard offset, wallOffset and savings for loop
 692 
 693         //ZoneOffset stdOffset = zone0.standardOffset;
 694         ZoneOffset stdOffset = ZoneOffset.ofTotalSeconds(zone0.stdOffsetSecs);
 695 
 696         int savings = zone0.fixedSavingsSecs;
 697         ZoneOffset wallOffset = ZoneOffset.ofTotalSeconds(stdOffset.getTotalSeconds() + savings);
 698 
 699         // start ldt of each zone window
 700         LocalDateTime zoneStart = LocalDateTime.MIN;
 701 
 702         // first stanard offset
 703         ZoneOffset firstStdOffset = stdOffset;
 704         // first wall offset
 705         ZoneOffset firstWallOffset = wallOffset;
 706 
 707         for (ZoneLine zone : zones) {
 708             // check if standard offset changed, update it if yes
 709             ZoneOffset stdOffsetPrev = stdOffset;  // for effectiveSavings check
 710             if (zone.stdOffsetSecs != stdOffset.getTotalSeconds()) {
 711                 ZoneOffset stdOffsetNew = ZoneOffset.ofTotalSeconds(zone.stdOffsetSecs);
 712                 standardTransitionList.add(
 713                     ZoneOffsetTransition.of(
 714                         LocalDateTime.ofEpochSecond(zoneStart.toEpochSecond(wallOffset),
 715                                                     0,
 716                                                     stdOffset),
 717                         stdOffset,
 718                         stdOffsetNew));
 719                 stdOffset = stdOffsetNew;
 720             }
 721 
 722             LocalDateTime zoneEnd;
 723             if (zone.year == Year.MAX_VALUE) {
 724                 zoneEnd = LocalDateTime.MAX;
 725             } else {
 726                 zoneEnd = zone.toDateTime();
 727             }
 728             if (zoneEnd.compareTo(zoneStart) < 0) {
 729                 throw new IllegalStateException("Windows must be in date-time order: " +
 730                         zoneEnd + " < " + zoneStart);
 731             }
 732             // calculate effective savings at the start of the window
 733             List<TransRule> trules = null;
 734             List<TransRule> lastRules = null;
 735 
 736             int effectiveSavings = zone.fixedSavingsSecs;
 737             if (zone.savingsRule != null) {
 738                 List<RuleLine> tzdbRules = rules.get(zone.savingsRule);
 739                 if (tzdbRules == null) {
 740                    throw new IllegalArgumentException("<Rule> not found: " +
 741                                                        zone.savingsRule);
 742                 }
 743                 trules = new ArrayList<>(256);
 744                 lastRules = new ArrayList<>(2);
 745                 int lastRulesStartYear = Year.MIN_VALUE;
 746 
 747                 // merge the rules to transitions
 748                 for (RuleLine rule : tzdbRules) {
 749                     if (rule.startYear > zoneEnd.getYear()) {
 750                         // rules will not be used for this zone entry
 751                         continue;
 752                     }
 753                     rule.adjustToForwards(2004);  // irrelevant, treat as leap year
 754 
 755                     int startYear = rule.startYear;
 756                     int endYear = rule.endYear;
 757                     if (zoneEnd.equals(LocalDateTime.MAX)) {
 758                         if (endYear == Year.MAX_VALUE) {
 759                             endYear = startYear;
 760                             lastRules.add(new TransRule(endYear, rule));
 761                             lastRulesStartYear = Math.max(startYear, lastRulesStartYear);
 762                         }
 763                     } else {
 764                         if (endYear == Year.MAX_VALUE) {
 765                             //endYear = zoneEnd.getYear();
 766                             endYear = zone.year;
 767                         }
 768                     }
 769                     int year = startYear;
 770                     while (year <= endYear) {
 771                         trules.add(new TransRule(year, rule));
 772                         year++;
 773                     }
 774                 }
 775 
 776                 // last rules, fill the gap years between different last rules
 777                 if (zoneEnd.equals(LocalDateTime.MAX)) {
 778                     lastRulesStartYear = Math.max(lastRulesStartYear, zoneStart.getYear()) + 1;
 779                     for (TransRule rule : lastRules) {
 780                         if (rule.year <= lastRulesStartYear) {
 781                             int year = rule.year;
 782                             while (year <= lastRulesStartYear) {
 783                                 trules.add(new TransRule(year, rule.rule));
 784                                 year++;
 785                             }
 786                             rule.year = lastRulesStartYear;
 787                             rule.ldt = rule.rule.toDateTime(year);
 788                             rule.ldtSecs = rule.ldt.toEpochSecond(ZoneOffset.UTC);
 789                         }
 790                     }
 791                     Collections.sort(lastRules);
 792                 }
 793                 // sort the merged rules
 794                 Collections.sort(trules);
 795 
 796                 effectiveSavings = 0;
 797                 for (TransRule rule : trules) {
 798                     if (rule.toEpochSecond(stdOffsetPrev, savings) >
 799                         zoneStart.toEpochSecond(wallOffset)) {
 800                         // previous savings amount found, which could be the
 801                         // savings amount at the instant that the window starts
 802                         // (hence isAfter)
 803                         break;
 804                     }
 805                     effectiveSavings = rule.rule.savingsAmount;
 806                 }
 807             }
 808             // check if the start of the window represents a transition
 809             ZoneOffset effectiveWallOffset =
 810                 ZoneOffset.ofTotalSeconds(stdOffset.getTotalSeconds() + effectiveSavings);
 811 
 812             if (!wallOffset.equals(effectiveWallOffset)) {
 813                 transitionList.add(ZoneOffsetTransition.of(zoneStart,
 814                                                            wallOffset,
 815                                                            effectiveWallOffset));
 816             }
 817             savings = effectiveSavings;
 818             // apply rules within the window
 819             if (trules != null) {
 820                 long zoneStartEpochSecs = zoneStart.toEpochSecond(wallOffset);
 821                 for (TransRule trule : trules) {
 822                     if (trule.isTransition(savings)) {
 823                         long epochSecs = trule.toEpochSecond(stdOffset, savings);
 824                         if (epochSecs < zoneStartEpochSecs ||
 825                             epochSecs >= zone.toDateTimeEpochSecond(savings)) {
 826                             continue;
 827                         }
 828                         transitionList.add(trule.toTransition(stdOffset, savings));
 829                         savings = trule.rule.savingsAmount;
 830                     }
 831                 }
 832             }
 833             if (lastRules != null) {
 834                 for (TransRule trule : lastRules) {
 835                     lastTransitionRuleList.add(trule.rule.toTransitionRule(stdOffset, savings));
 836                     savings = trule.rule.savingsAmount;
 837                 }
 838             }
 839 
 840             // finally we can calculate the true end of the window, passing it to the next window
 841             wallOffset = ZoneOffset.ofTotalSeconds(stdOffset.getTotalSeconds() + savings);
 842             zoneStart = LocalDateTime.ofEpochSecond(zone.toDateTimeEpochSecond(savings),
 843                                                     0,
 844                                                     wallOffset);
 845         }
 846         return new ZoneRules(firstStdOffset,
 847                              firstWallOffset,
 848                              standardTransitionList,
 849                              transitionList,
 850                              lastTransitionRuleList);
 851     }
 852 
 853 }