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