summaryrefslogtreecommitdiff
path: root/absl/time/internal/cctz/src/time_zone_info.cc
blob: 20bba28b363bf0d3aed56d6eb66acbe4bfb481a5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
// Copyright 2016 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//   http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

// This file implements the TimeZoneIf interface using the "zoneinfo"
// data provided by the IANA Time Zone Database (i.e., the only real game
// in town).
//
// TimeZoneInfo represents the history of UTC-offset changes within a time
// zone. Most changes are due to daylight-saving rules, but occasionally
// shifts are made to the time-zone's base offset. The database only attempts
// to be definitive for times since 1970, so be wary of local-time conversions
// before that. Also, rule and zone-boundary changes are made at the whim
// of governments, so the conversion of future times needs to be taken with
// a grain of salt.
//
// For more information see tzfile(5), http://www.iana.org/time-zones, or
// http://en.wikipedia.org/wiki/Zoneinfo.
//
// Note that we assume the proleptic Gregorian calendar and 60-second
// minutes throughout.

#include "time_zone_info.h"

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <memory>
#include <sstream>
#include <string>

#include "absl/time/internal/cctz/include/cctz/civil_time.h"
#include "time_zone_fixed.h"
#include "time_zone_posix.h"

namespace absl {
namespace time_internal {
namespace cctz {

namespace {

inline bool IsLeap(year_t year) {
  return (year % 4) == 0 && ((year % 100) != 0 || (year % 400) == 0);
}

// The number of days in non-leap and leap years respectively.
const std::int_least32_t kDaysPerYear[2] = {365, 366};

// The day offsets of the beginning of each (1-based) month in non-leap and
// leap years respectively (e.g., 335 days before December in a leap year).
const std::int_least16_t kMonthOffsets[2][1 + 12 + 1] = {
  {-1, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365},
  {-1, 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366},
};

// We reject leap-second encoded zoneinfo and so assume 60-second minutes.
const std::int_least32_t kSecsPerDay = 24 * 60 * 60;

// 400-year chunks always have 146097 days (20871 weeks).
const std::int_least64_t kSecsPer400Years = 146097LL * kSecsPerDay;

// Like kDaysPerYear[] but scaled up by a factor of kSecsPerDay.
const std::int_least32_t kSecsPerYear[2] = {
  365 * kSecsPerDay,
  366 * kSecsPerDay,
};

// Single-byte, unsigned numeric values are encoded directly.
inline std::uint_fast8_t Decode8(const char* cp) {
  return static_cast<std::uint_fast8_t>(*cp) & 0xff;
}

// Multi-byte, numeric values are encoded using a MSB first,
// twos-complement representation. These helpers decode, from
// the given address, 4-byte and 8-byte values respectively.
// Note: If int_fastXX_t == intXX_t and this machine is not
// twos complement, then there will be at least one input value
// we cannot represent.
std::int_fast32_t Decode32(const char* cp) {
  std::uint_fast32_t v = 0;
  for (int i = 0; i != (32 / 8); ++i) v = (v << 8) | Decode8(cp++);
  const std::int_fast32_t s32max = 0x7fffffff;
  const auto s32maxU = static_cast<std::uint_fast32_t>(s32max);
  if (v <= s32maxU) return static_cast<std::int_fast32_t>(v);
  return static_cast<std::int_fast32_t>(v - s32maxU - 1) - s32max - 1;
}

std::int_fast64_t Decode64(const char* cp) {
  std::uint_fast64_t v = 0;
  for (int i = 0; i != (64 / 8); ++i) v = (v << 8) | Decode8(cp++);
  const std::int_fast64_t s64max = 0x7fffffffffffffff;
  const auto s64maxU = static_cast<std::uint_fast64_t>(s64max);
  if (v <= s64maxU) return static_cast<std::int_fast64_t>(v);
  return static_cast<std::int_fast64_t>(v - s64maxU - 1) - s64max - 1;
}

// Generate a year-relative offset for a PosixTransition.
std::int_fast64_t TransOffset(bool leap_year, int jan1_weekday,
                              const PosixTransition& pt) {
  std::int_fast64_t days = 0;
  switch (pt.date.fmt) {
    case PosixTransition::J: {
      days = pt.date.j.day;
      if (!leap_year || days < kMonthOffsets[1][3]) days -= 1;
      break;
    }
    case PosixTransition::N: {
      days = pt.date.n.day;
      break;
    }
    case PosixTransition::M: {
      const bool last_week = (pt.date.m.week == 5);
      days = kMonthOffsets[leap_year][pt.date.m.month + last_week];
      const std::int_fast64_t weekday = (jan1_weekday + days) % 7;
      if (last_week) {
        days -= (weekday + 7 - 1 - pt.date.m.weekday) % 7 + 1;
      } else {
        days += (pt.date.m.weekday + 7 - weekday) % 7;
        days += (pt.date.m.week - 1) * 7;
      }
      break;
    }
  }
  return (days * kSecsPerDay) + pt.time.offset;
}

inline time_zone::civil_lookup MakeUnique(const time_point<sys_seconds>& tp) {
  time_zone::civil_lookup cl;
  cl.kind = time_zone::civil_lookup::UNIQUE;
  cl.pre = cl.trans = cl.post = tp;
  return cl;
}

inline time_zone::civil_lookup MakeUnique(std::int_fast64_t unix_time) {
  return MakeUnique(FromUnixSeconds(unix_time));
}

inline time_zone::civil_lookup MakeSkipped(const Transition& tr,
                                           const civil_second& cs) {
  time_zone::civil_lookup cl;
  cl.kind = time_zone::civil_lookup::SKIPPED;
  cl.pre = FromUnixSeconds(tr.unix_time - 1 + (cs - tr.prev_civil_sec));
  cl.trans = FromUnixSeconds(tr.unix_time);
  cl.post = FromUnixSeconds(tr.unix_time - (tr.civil_sec - cs));
  return cl;
}

inline time_zone::civil_lookup MakeRepeated(const Transition& tr,
                                            const civil_second& cs) {
  time_zone::civil_lookup cl;
  cl.kind = time_zone::civil_lookup::REPEATED;
  cl.pre = FromUnixSeconds(tr.unix_time - 1 - (tr.prev_civil_sec - cs));
  cl.trans = FromUnixSeconds(tr.unix_time);
  cl.post = FromUnixSeconds(tr.unix_time + (cs - tr.civil_sec));
  return cl;
}

inline civil_second YearShift(const civil_second& cs, year_t shift) {
  return civil_second(cs.year() + shift, cs.month(), cs.day(),
                      cs.hour(), cs.minute(), cs.second());
}

}  // namespace

// What (no leap-seconds) UTC+seconds zoneinfo would look like.
bool TimeZoneInfo::ResetToBuiltinUTC(const sys_seconds& offset) {
  transition_types_.resize(1);
  TransitionType& tt(transition_types_.back());
  tt.utc_offset = static_cast<std::int_least32_t>(offset.count());
  tt.is_dst = false;
  tt.abbr_index = 0;

  // We temporarily add some redundant, contemporary (2012 through 2021)
  // transitions for performance reasons.  See TimeZoneInfo::LocalTime().
  // TODO: Fix the performance issue and remove the extra transitions.
  transitions_.clear();
  transitions_.reserve(12);
  for (const std::int_fast64_t unix_time : {
           -(1LL << 59),  // BIG_BANG
           1325376000LL,  // 2012-01-01T00:00:00+00:00
           1356998400LL,  // 2013-01-01T00:00:00+00:00
           1388534400LL,  // 2014-01-01T00:00:00+00:00
           1420070400LL,  // 2015-01-01T00:00:00+00:00
           1451606400LL,  // 2016-01-01T00:00:00+00:00
           1483228800LL,  // 2017-01-01T00:00:00+00:00
           1514764800LL,  // 2018-01-01T00:00:00+00:00
           1546300800LL,  // 2019-01-01T00:00:00+00:00
           1577836800LL,  // 2020-01-01T00:00:00+00:00
           1609459200LL,  // 2021-01-01T00:00:00+00:00
           2147483647LL,  // 2^31 - 1
       }) {
    Transition& tr(*transitions_.emplace(transitions_.end()));
    tr.unix_time = unix_time;
    tr.type_index = 0;
    tr.civil_sec = LocalTime(tr.unix_time, tt).cs;
    tr.prev_civil_sec = tr.civil_sec - 1;
  }

  default_transition_type_ = 0;
  abbreviations_ = FixedOffsetToAbbr(offset);
  abbreviations_.append(1, '\0');  // add NUL
  future_spec_.clear();  // never needed for a fixed-offset zone
  extended_ = false;

  tt.civil_max = LocalTime(sys_seconds::max().count(), tt).cs;
  tt.civil_min = LocalTime(sys_seconds::min().count(), tt).cs;

  transitions_.shrink_to_fit();
  return true;
}

// Builds the in-memory header using the raw bytes from the file.
bool TimeZoneInfo::Header::Build(const tzhead& tzh) {
  std::int_fast32_t v;
  if ((v = Decode32(tzh.tzh_timecnt)) < 0) return false;
  timecnt = static_cast<std::size_t>(v);
  if ((v = Decode32(tzh.tzh_typecnt)) < 0) return false;
  typecnt = static_cast<std::size_t>(v);
  if ((v = Decode32(tzh.tzh_charcnt)) < 0) return false;
  charcnt = static_cast<std::size_t>(v);
  if ((v = Decode32(tzh.tzh_leapcnt)) < 0) return false;
  leapcnt = static_cast<std::size_t>(v);
  if ((v = Decode32(tzh.tzh_ttisstdcnt)) < 0) return false;
  ttisstdcnt = static_cast<std::size_t>(v);
  if ((v = Decode32(tzh.tzh_ttisgmtcnt)) < 0) return false;
  ttisgmtcnt = static_cast<std::size_t>(v);
  return true;
}

// How many bytes of data are associated with this header. The result
// depends upon whether this is a section with 4-byte or 8-byte times.
std::size_t TimeZoneInfo::Header::DataLength(std::size_t time_len) const {
  std::size_t len = 0;
  len += (time_len + 1) * timecnt;  // unix_time + type_index
  len += (4 + 1 + 1) * typecnt;     // utc_offset + is_dst + abbr_index
  len += 1 * charcnt;               // abbreviations
  len += (time_len + 4) * leapcnt;  // leap-time + TAI-UTC
  len += 1 * ttisstdcnt;            // UTC/local indicators
  len += 1 * ttisgmtcnt;            // standard/wall indicators
  return len;
}

// Check that the TransitionType has the expected offset/is_dst/abbreviation.
void TimeZoneInfo::CheckTransition(const std::string& name,
                                   const TransitionType& tt,
                                   std::int_fast32_t offset, bool is_dst,
                                   const std::string& abbr) const {
  if (tt.utc_offset != offset || tt.is_dst != is_dst ||
      &abbreviations_[tt.abbr_index] != abbr) {
    std::clog << name << ": Transition"
              << " offset=" << tt.utc_offset << "/"
              << (tt.is_dst ? "DST" : "STD")
              << "/abbr=" << &abbreviations_[tt.abbr_index]
              << " does not match POSIX spec '" << future_spec_ << "'\n";
  }
}

// zic(8) can generate no-op transitions when a zone changes rules at an
// instant when there is actually no discontinuity.  So we check whether
// two transitions have equivalent types (same offset/is_dst/abbr).
bool TimeZoneInfo::EquivTransitions(std::uint_fast8_t tt1_index,
                                    std::uint_fast8_t tt2_index) const {
  if (tt1_index == tt2_index) return true;
  const TransitionType& tt1(transition_types_[tt1_index]);
  const TransitionType& tt2(transition_types_[tt2_index]);
  if (tt1.is_dst != tt2.is_dst) return false;
  if (tt1.utc_offset != tt2.utc_offset) return false;
  if (tt1.abbr_index != tt2.abbr_index) return false;
  return true;
}

// Use the POSIX-TZ-environment-variable-style std::string to handle times
// in years after the last transition stored in the zoneinfo data.
void TimeZoneInfo::ExtendTransitions(const std::string& name,
                                     const Header& hdr) {
  extended_ = false;
  bool extending = !future_spec_.empty();

  PosixTimeZone posix;
  if (extending && !ParsePosixSpec(future_spec_, &posix)) {
    std::clog << name << ": Failed to parse '" << future_spec_ << "'\n";
    extending = false;
  }

  if (extending && posix.dst_abbr.empty()) {  // std only
    // The future specification should match the last/default transition,
    // and that means that handling the future will fall out naturally.
    std::uint_fast8_t index = default_transition_type_;
    if (hdr.timecnt != 0) index = transitions_[hdr.timecnt - 1].type_index;
    const TransitionType& tt(transition_types_[index]);
    CheckTransition(name, tt, posix.std_offset, false, posix.std_abbr);
    extending = false;
  }

  if (extending && hdr.timecnt < 2) {
    std::clog << name << ": Too few transitions for POSIX spec\n";
    extending = false;
  }

  if (!extending) {
    // Ensure that there is always a transition in the second half of the
    // time line (the BIG_BANG transition is in the first half) so that the
    // signed difference between a civil_second and the civil_second of its
    // previous transition is always representable, without overflow.
    const Transition& last(transitions_.back());
    if (last.unix_time < 0) {
      const std::uint_fast8_t type_index = last.type_index;
      Transition& tr(*transitions_.emplace(transitions_.end()));
      tr.unix_time = 2147483647;  // 2038-01-19T03:14:07+00:00
      tr.type_index = type_index;
    }
    return;  // last transition wins
  }

  // Extend the transitions for an additional 400 years using the
  // future specification. Years beyond those can be handled by
  // mapping back to a cycle-equivalent year within that range.
  // zic(8) should probably do this so that we don't have to.
  // TODO: Reduce the extension by the number of compatible
  // transitions already in place.
  transitions_.reserve(hdr.timecnt + 400 * 2 + 1);
  transitions_.resize(hdr.timecnt + 400 * 2);
  extended_ = true;

  // The future specification should match the last two transitions,
  // and those transitions should have different is_dst flags.  Note
  // that nothing says the UTC offset used by the is_dst transition
  // must be greater than that used by the !is_dst transition.  (See
  // Europe/Dublin, for example.)
  const Transition* tr0 = &transitions_[hdr.timecnt - 1];
  const Transition* tr1 = &transitions_[hdr.timecnt - 2];
  const TransitionType* tt0 = &transition_types_[tr0->type_index];
  const TransitionType* tt1 = &transition_types_[tr1->type_index];
  const TransitionType& dst(tt0->is_dst ? *tt0 : *tt1);
  const TransitionType& std(tt0->is_dst ? *tt1 : *tt0);
  CheckTransition(name, dst, posix.dst_offset, true, posix.dst_abbr);
  CheckTransition(name, std, posix.std_offset, false, posix.std_abbr);

  // Add the transitions to tr1 and back to tr0 for each extra year.
  last_year_ = LocalTime(tr0->unix_time, *tt0).cs.year();
  bool leap_year = IsLeap(last_year_);
  const civil_day jan1(last_year_, 1, 1);
  std::int_fast64_t jan1_time = civil_second(jan1) - civil_second();
  int jan1_weekday = (static_cast<int>(get_weekday(jan1)) + 1) % 7;
  Transition* tr = &transitions_[hdr.timecnt];  // next trans to fill
  if (LocalTime(tr1->unix_time, *tt1).cs.year() != last_year_) {
    // Add a single extra transition to align to a calendar year.
    transitions_.resize(transitions_.size() + 1);
    assert(tr == &transitions_[hdr.timecnt]);  // no reallocation
    const PosixTransition& pt1(tt0->is_dst ? posix.dst_end : posix.dst_start);
    std::int_fast64_t tr1_offset = TransOffset(leap_year, jan1_weekday, pt1);
    tr->unix_time = jan1_time + tr1_offset - tt0->utc_offset;
    tr++->type_index = tr1->type_index;
    tr0 = &transitions_[hdr.timecnt];
    tr1 = &transitions_[hdr.timecnt - 1];
    tt0 = &transition_types_[tr0->type_index];
    tt1 = &transition_types_[tr1->type_index];
  }
  const PosixTransition& pt1(tt0->is_dst ? posix.dst_end : posix.dst_start);
  const PosixTransition& pt0(tt0->is_dst ? posix.dst_start : posix.dst_end);
  for (const year_t limit = last_year_ + 400; last_year_ < limit;) {
    last_year_ += 1;  // an additional year of generated transitions
    jan1_time += kSecsPerYear[leap_year];
    jan1_weekday = (jan1_weekday + kDaysPerYear[leap_year]) % 7;
    leap_year = !leap_year && IsLeap(last_year_);
    std::int_fast64_t tr1_offset = TransOffset(leap_year, jan1_weekday, pt1);
    tr->unix_time = jan1_time + tr1_offset - tt0->utc_offset;
    tr++->type_index = tr1->type_index;
    std::int_fast64_t tr0_offset = TransOffset(leap_year, jan1_weekday, pt0);
    tr->unix_time = jan1_time + tr0_offset - tt1->utc_offset;
    tr++->type_index = tr0->type_index;
  }
  assert(tr == &transitions_[0] + transitions_.size());
}

bool TimeZoneInfo::Load(const std::string& name, ZoneInfoSource* zip) {
  // Read and validate the header.
  tzhead tzh;
  if (zip->Read(&tzh, sizeof(tzh)) != sizeof(tzh))
    return false;
  if (strncmp(tzh.tzh_magic, TZ_MAGIC, sizeof(tzh.tzh_magic)) != 0)
    return false;
  Header hdr;
  if (!hdr.Build(tzh))
    return false;
  std::size_t time_len = 4;
  if (tzh.tzh_version[0] != '\0') {
    // Skip the 4-byte data.
    if (zip->Skip(hdr.DataLength(time_len)) != 0)
      return false;
    // Read and validate the header for the 8-byte data.
    if (zip->Read(&tzh, sizeof(tzh)) != sizeof(tzh))
      return false;
    if (strncmp(tzh.tzh_magic, TZ_MAGIC, sizeof(tzh.tzh_magic)) != 0)
      return false;
    if (tzh.tzh_version[0] == '\0')
      return false;
    if (!hdr.Build(tzh))
      return false;
    time_len = 8;
  }
  if (hdr.typecnt == 0)
    return false;
  if (hdr.leapcnt != 0) {
    // This code assumes 60-second minutes so we do not want
    // the leap-second encoded zoneinfo. We could reverse the
    // compensation, but the "right" encoding is rarely used
    // so currently we simply reject such data.
    return false;
  }
  if (hdr.ttisstdcnt != 0 && hdr.ttisstdcnt != hdr.typecnt)
    return false;
  if (hdr.ttisgmtcnt != 0 && hdr.ttisgmtcnt != hdr.typecnt)
    return false;

  // Read the data into a local buffer.
  std::size_t len = hdr.DataLength(time_len);
  std::vector<char> tbuf(len);
  if (zip->Read(tbuf.data(), len) != len)
    return false;
  const char* bp = tbuf.data();

  // Decode and validate the transitions.
  transitions_.reserve(hdr.timecnt + 2);  // We might add a couple.
  transitions_.resize(hdr.timecnt);
  for (std::size_t i = 0; i != hdr.timecnt; ++i) {
    transitions_[i].unix_time = (time_len == 4) ? Decode32(bp) : Decode64(bp);
    bp += time_len;
    if (i != 0) {
      // Check that the transitions are ordered by time (as zic guarantees).
      if (!Transition::ByUnixTime()(transitions_[i - 1], transitions_[i]))
        return false;  // out of order
    }
  }
  bool seen_type_0 = false;
  for (std::size_t i = 0; i != hdr.timecnt; ++i) {
    transitions_[i].type_index = Decode8(bp++);
    if (transitions_[i].type_index >= hdr.typecnt)
      return false;
    if (transitions_[i].type_index == 0)
      seen_type_0 = true;
  }

  // Decode and validate the transition types.
  transition_types_.resize(hdr.typecnt);
  for (std::size_t i = 0; i != hdr.typecnt; ++i) {
    transition_types_[i].utc_offset =
        static_cast<std::int_least32_t>(Decode32(bp));
    if (transition_types_[i].utc_offset >= kSecsPerDay ||
        transition_types_[i].utc_offset <= -kSecsPerDay)
      return false;
    bp += 4;
    transition_types_[i].is_dst = (Decode8(bp++) != 0);
    transition_types_[i].abbr_index = Decode8(bp++);
    if (transition_types_[i].abbr_index >= hdr.charcnt)
      return false;
  }

  // Determine the before-first-transition type.
  default_transition_type_ = 0;
  if (seen_type_0 && hdr.timecnt != 0) {
    std::uint_fast8_t index = 0;
    if (transition_types_[0].is_dst) {
      index = transitions_[0].type_index;
      while (index != 0 && transition_types_[index].is_dst)
        --index;
    }
    while (index != hdr.typecnt && transition_types_[index].is_dst)
      ++index;
    if (index != hdr.typecnt)
      default_transition_type_ = index;
  }

  // Copy all the abbreviations.
  abbreviations_.assign(bp, hdr.charcnt);
  bp += hdr.charcnt;

  // Skip the unused portions. We've already dispensed with leap-second
  // encoded zoneinfo. The ttisstd/ttisgmt indicators only apply when
  // interpreting a POSIX spec that does not include start/end rules, and
  // that isn't the case here (see "zic -p").
  bp += (8 + 4) * hdr.leapcnt;  // leap-time + TAI-UTC
  bp += 1 * hdr.ttisstdcnt;     // UTC/local indicators
  bp += 1 * hdr.ttisgmtcnt;     // standard/wall indicators
  assert(bp == tbuf.data() + tbuf.size());

  future_spec_.clear();
  if (tzh.tzh_version[0] != '\0') {
    // Snarf up the NL-enclosed future POSIX spec. Note
    // that version '3' files utilize an extended format.
    auto get_char = [](ZoneInfoSource* zip) -> int {
      unsigned char ch;  // all non-EOF results are positive
      return (zip->Read(&ch, 1) == 1) ? ch : EOF;
    };
    if (get_char(zip) != '\n')
      return false;
    for (int c = get_char(zip); c != '\n'; c = get_char(zip)) {
      if (c == EOF)
        return false;
      future_spec_.push_back(static_cast<char>(c));
    }
  }

  // We don't check for EOF so that we're forwards compatible.

  // Trim redundant transitions. zic may have added these to work around
  // differences between the glibc and reference implementations (see
  // zic.c:dontmerge) and the Qt library (see zic.c:WORK_AROUND_QTBUG_53071).
  // For us, they just get in the way when we do future_spec_ extension.
  while (hdr.timecnt > 1) {
    if (!EquivTransitions(transitions_[hdr.timecnt - 1].type_index,
                          transitions_[hdr.timecnt - 2].type_index)) {
      break;
    }
    hdr.timecnt -= 1;
  }
  transitions_.resize(hdr.timecnt);

  // Ensure that there is always a transition in the first half of the
  // time line (the second half is handled in ExtendTransitions()) so that
  // the signed difference between a civil_second and the civil_second of
  // its previous transition is always representable, without overflow.
  // A contemporary zic will usually have already done this for us.
  if (transitions_.empty() || transitions_.front().unix_time >= 0) {
    Transition& tr(*transitions_.emplace(transitions_.begin()));
    tr.unix_time = -(1LL << 59);  // see tz/zic.c "BIG_BANG"
    tr.type_index = default_transition_type_;
    hdr.timecnt += 1;
  }

  // Extend the transitions using the future specification.
  ExtendTransitions(name, hdr);

  // Compute the local civil time for each transition and the preceding
  // second. These will be used for reverse conversions in MakeTime().
  const TransitionType* ttp = &transition_types_[default_transition_type_];
  for (std::size_t i = 0; i != transitions_.size(); ++i) {
    Transition& tr(transitions_[i]);
    tr.prev_civil_sec = LocalTime(tr.unix_time, *ttp).cs - 1;
    ttp = &transition_types_[tr.type_index];
    tr.civil_sec = LocalTime(tr.unix_time, *ttp).cs;
    if (i != 0) {
      // Check that the transitions are ordered by civil time. Essentially
      // this means that an offset change cannot cross another such change.
      // No one does this in practice, and we depend on it in MakeTime().
      if (!Transition::ByCivilTime()(transitions_[i - 1], tr))
        return false;  // out of order
    }
  }

  // Compute the maximum/minimum civil times that can be converted to a
  // time_point<sys_seconds> for each of the zone's transition types.
  for (auto& tt : transition_types_) {
    tt.civil_max = LocalTime(sys_seconds::max().count(), tt).cs;
    tt.civil_min = LocalTime(sys_seconds::min().count(), tt).cs;
  }

  transitions_.shrink_to_fit();
  return true;
}

namespace {

// fopen(3) adaptor.
inline FILE* FOpen(const char* path, const char* mode) {
#if defined(_MSC_VER)
  FILE* fp;
  if (fopen_s(&fp, path, mode) != 0) fp = nullptr;
  return fp;
#else
  return fopen(path, mode);  // TODO: Enable the close-on-exec flag.
#endif
}

// A stdio(3)-backed implementation of ZoneInfoSource.
class FileZoneInfoSource : public ZoneInfoSource {
 public:
  static std::unique_ptr<ZoneInfoSource> Open(const std::string& name);

  std::size_t Read(void* ptr, std::size_t size) override {
    size = std::min(size, len_);
    std::size_t nread = fread(ptr, 1, size, fp_.get());
    len_ -= nread;
    return nread;
  }
  int Skip(std::size_t offset) override {
    offset = std::min(offset, len_);
    int rc = fseek(fp_.get(), static_cast<long>(offset), SEEK_CUR);
    if (rc == 0) len_ -= offset;
    return rc;
  }

 protected:
  explicit FileZoneInfoSource(
      FILE* fp, std::size_t len = std::numeric_limits<std::size_t>::max())
      : fp_(fp, fclose), len_(len) {}

 private:
  std::unique_ptr<FILE, int(*)(FILE*)> fp_;
  std::size_t len_;
};

std::unique_ptr<ZoneInfoSource> FileZoneInfoSource::Open(
    const std::string& name) {
  // Use of the "file:" prefix is intended for testing purposes only.
  if (name.compare(0, 5, "file:") == 0) return Open(name.substr(5));

  // Map the time-zone name to a path name.
  std::string path;
  if (name.empty() || name[0] != '/') {
    const char* tzdir = "/usr/share/zoneinfo";
    char* tzdir_env = nullptr;
#if defined(_MSC_VER)
    _dupenv_s(&tzdir_env, nullptr, "TZDIR");
#else
    tzdir_env = std::getenv("TZDIR");
#endif
    if (tzdir_env && *tzdir_env) tzdir = tzdir_env;
    path += tzdir;
    path += '/';
#if defined(_MSC_VER)
    free(tzdir_env);
#endif
  }
  path += name;

  // Open the zoneinfo file.
  FILE* fp = FOpen(path.c_str(), "rb");
  if (fp == nullptr) return nullptr;
  std::size_t length = 0;
  if (fseek(fp, 0, SEEK_END) == 0) {
    long pos = ftell(fp);
    if (pos >= 0) {
      length = static_cast<std::size_t>(pos);
    }
    rewind(fp);
  }
  return std::unique_ptr<ZoneInfoSource>(new FileZoneInfoSource(fp, length));
}

#if defined(__ANDROID__)
class AndroidZoneInfoSource : public FileZoneInfoSource {
 public:
  static std::unique_ptr<ZoneInfoSource> Open(const std::string& name);

 private:
  explicit AndroidZoneInfoSource(FILE* fp, std::size_t len)
      : FileZoneInfoSource(fp, len) {}
};

std::unique_ptr<ZoneInfoSource> AndroidZoneInfoSource::Open(
    const std::string& name) {
  // Use of the "file:" prefix is intended for testing purposes only.
  if (name.compare(0, 5, "file:") == 0) return Open(name.substr(5));

  // See Android's libc/tzcode/bionic.cpp for additional information.
  for (const char* tzdata : {"/data/misc/zoneinfo/current/tzdata",
                             "/system/usr/share/zoneinfo/tzdata"}) {
    std::unique_ptr<FILE, int (*)(FILE*)> fp(FOpen(tzdata, "rb"), fclose);
    if (fp.get() == nullptr) continue;

    char hbuf[24];  // covers header.zonetab_offset too
    if (fread(hbuf, 1, sizeof(hbuf), fp.get()) != sizeof(hbuf)) continue;
    if (strncmp(hbuf, "tzdata", 6) != 0) continue;
    const std::int_fast32_t index_offset = Decode32(hbuf + 12);
    const std::int_fast32_t data_offset = Decode32(hbuf + 16);
    if (index_offset < 0 || data_offset < index_offset) continue;
    if (fseek(fp.get(), static_cast<long>(index_offset), SEEK_SET) != 0)
      continue;

    char ebuf[52];  // covers entry.unused too
    const std::size_t index_size =
        static_cast<std::size_t>(data_offset - index_offset);
    const std::size_t zonecnt = index_size / sizeof(ebuf);
    if (zonecnt * sizeof(ebuf) != index_size) continue;
    for (std::size_t i = 0; i != zonecnt; ++i) {
      if (fread(ebuf, 1, sizeof(ebuf), fp.get()) != sizeof(ebuf)) break;
      const std::int_fast32_t start = data_offset + Decode32(ebuf + 40);
      const std::int_fast32_t length = Decode32(ebuf + 44);
      if (start < 0 || length < 0) break;
      ebuf[40] = '\0';  // ensure zone name is NUL terminated
      if (strcmp(name.c_str(), ebuf) == 0) {
        if (fseek(fp.get(), static_cast<long>(start), SEEK_SET) != 0) break;
        return std::unique_ptr<ZoneInfoSource>(new AndroidZoneInfoSource(
            fp.release(), static_cast<std::size_t>(length)));
      }
    }
  }
  return nullptr;
}
#endif

}  // namespace

bool TimeZoneInfo::Load(const std::string& name) {
  // We can ensure that the loading of UTC or any other fixed-offset
  // zone never fails because the simple, fixed-offset state can be
  // internally generated. Note that this depends on our choice to not
  // accept leap-second encoded ("right") zoneinfo.
  auto offset = sys_seconds::zero();
  if (FixedOffsetFromName(name, &offset)) {
    return ResetToBuiltinUTC(offset);
  }

  // Find and use a ZoneInfoSource to load the named zone.
  auto zip = cctz_extension::zone_info_source_factory(
      name, [](const std::string& name) -> std::unique_ptr<ZoneInfoSource> {
        if (auto zip = FileZoneInfoSource::Open(name)) return zip;
#if defined(__ANDROID__)
        if (auto zip = AndroidZoneInfoSource::Open(name)) return zip;
#endif
        return nullptr;
      });
  return zip != nullptr && Load(name, zip.get());
}

// BreakTime() translation for a particular transition type.
time_zone::absolute_lookup TimeZoneInfo::LocalTime(
    std::int_fast64_t unix_time, const TransitionType& tt) const {
  // A civil time in "+offset" looks like (time+offset) in UTC.
  // Note: We perform two additions in the civil_second domain to
  // sidestep the chance of overflow in (unix_time + tt.utc_offset).
  return {(civil_second() + unix_time) + tt.utc_offset,
          tt.utc_offset, tt.is_dst, &abbreviations_[tt.abbr_index]};
}

// BreakTime() translation for a particular transition.
time_zone::absolute_lookup TimeZoneInfo::LocalTime(
    std::int_fast64_t unix_time, const Transition& tr) const {
  const TransitionType& tt = transition_types_[tr.type_index];
  // Note: (unix_time - tr.unix_time) will never overflow as we
  // have ensured that there is always a "nearby" transition.
  return {tr.civil_sec + (unix_time - tr.unix_time),  // TODO: Optimize.
          tt.utc_offset, tt.is_dst, &abbreviations_[tt.abbr_index]};
}

// MakeTime() translation with a conversion-preserving +N * 400-year shift.
time_zone::civil_lookup TimeZoneInfo::TimeLocal(const civil_second& cs,
                                                year_t c4_shift) const {
  assert(last_year_ - 400 < cs.year() && cs.year() <= last_year_);
  time_zone::civil_lookup cl = MakeTime(cs);
  if (c4_shift > sys_seconds::max().count() / kSecsPer400Years) {
    cl.pre = cl.trans = cl.post = time_point<sys_seconds>::max();
  } else {
    const auto offset = sys_seconds(c4_shift * kSecsPer400Years);
    const auto limit = time_point<sys_seconds>::max() - offset;
    for (auto* tp : {&cl.pre, &cl.trans, &cl.post}) {
      if (*tp > limit) {
        *tp = time_point<sys_seconds>::max();
      } else {
        *tp += offset;
      }
    }
  }
  return cl;
}

time_zone::absolute_lookup TimeZoneInfo::BreakTime(
    const time_point<sys_seconds>& tp) const {
  std::int_fast64_t unix_time = ToUnixSeconds(tp);
  const std::size_t timecnt = transitions_.size();
  assert(timecnt != 0);  // We always add a transition.

  if (unix_time < transitions_[0].unix_time) {
    return LocalTime(unix_time, transition_types_[default_transition_type_]);
  }
  if (unix_time >= transitions_[timecnt - 1].unix_time) {
    // After the last transition. If we extended the transitions using
    // future_spec_, shift back to a supported year using the 400-year
    // cycle of calendaric equivalence and then compensate accordingly.
    if (extended_) {
      const std::int_fast64_t diff =
          unix_time - transitions_[timecnt - 1].unix_time;
      const year_t shift = diff / kSecsPer400Years + 1;
      const auto d = sys_seconds(shift * kSecsPer400Years);
      time_zone::absolute_lookup al = BreakTime(tp - d);
      al.cs = YearShift(al.cs, shift * 400);
      return al;
    }
    return LocalTime(unix_time, transitions_[timecnt - 1]);
  }

  const std::size_t hint = local_time_hint_.load(std::memory_order_relaxed);
  if (0 < hint && hint < timecnt) {
    if (transitions_[hint - 1].unix_time <= unix_time) {
      if (unix_time < transitions_[hint].unix_time) {
        return LocalTime(unix_time, transitions_[hint - 1]);
      }
    }
  }

  const Transition target = {unix_time, 0, civil_second(), civil_second()};
  const Transition* begin = &transitions_[0];
  const Transition* tr = std::upper_bound(begin, begin + timecnt, target,
                                          Transition::ByUnixTime());
  local_time_hint_.store(static_cast<std::size_t>(tr - begin),
                         std::memory_order_relaxed);
  return LocalTime(unix_time, *--tr);
}

time_zone::civil_lookup TimeZoneInfo::MakeTime(const civil_second& cs) const {
  const std::size_t timecnt = transitions_.size();
  assert(timecnt != 0);  // We always add a transition.

  // Find the first transition after our target civil time.
  const Transition* tr = nullptr;
  const Transition* begin = &transitions_[0];
  const Transition* end = begin + timecnt;
  if (cs < begin->civil_sec) {
    tr = begin;
  } else if (cs >= transitions_[timecnt - 1].civil_sec) {
    tr = end;
  } else {
    const std::size_t hint = time_local_hint_.load(std::memory_order_relaxed);
    if (0 < hint && hint < timecnt) {
      if (transitions_[hint - 1].civil_sec <= cs) {
        if (cs < transitions_[hint].civil_sec) {
          tr = begin + hint;
        }
      }
    }
    if (tr == nullptr) {
      const Transition target = {0, 0, cs, civil_second()};
      tr = std::upper_bound(begin, end, target, Transition::ByCivilTime());
      time_local_hint_.store(static_cast<std::size_t>(tr - begin),
                             std::memory_order_relaxed);
    }
  }

  if (tr == begin) {
    if (tr->prev_civil_sec >= cs) {
      // Before first transition, so use the default offset.
      const TransitionType& tt(transition_types_[default_transition_type_]);
      if (cs < tt.civil_min) return MakeUnique(time_point<sys_seconds>::min());
      return MakeUnique(cs - (civil_second() + tt.utc_offset));
    }
    // tr->prev_civil_sec < cs < tr->civil_sec
    return MakeSkipped(*tr, cs);
  }

  if (tr == end) {
    if (cs > (--tr)->prev_civil_sec) {
      // After the last transition. If we extended the transitions using
      // future_spec_, shift back to a supported year using the 400-year
      // cycle of calendaric equivalence and then compensate accordingly.
      if (extended_ && cs.year() > last_year_) {
        const year_t shift = (cs.year() - last_year_ - 1) / 400 + 1;
        return TimeLocal(YearShift(cs, shift * -400), shift);
      }
      const TransitionType& tt(transition_types_[tr->type_index]);
      if (cs > tt.civil_max) return MakeUnique(time_point<sys_seconds>::max());
      return MakeUnique(tr->unix_time + (cs - tr->civil_sec));
    }
    // tr->civil_sec <= cs <= tr->prev_civil_sec
    return MakeRepeated(*tr, cs);
  }

  if (tr->prev_civil_sec < cs) {
    // tr->prev_civil_sec < cs < tr->civil_sec
    return MakeSkipped(*tr, cs);
  }

  if (cs <= (--tr)->prev_civil_sec) {
    // tr->civil_sec <= cs <= tr->prev_civil_sec
    return MakeRepeated(*tr, cs);
  }

  // In between transitions.
  return MakeUnique(tr->unix_time + (cs - tr->civil_sec));
}

std::string TimeZoneInfo::Description() const {
  std::ostringstream oss;
  // TODO: It would nice if the zoneinfo data included the zone name.
  // TODO: It would nice if the zoneinfo data included the tzdb version.
  oss << "#trans=" << transitions_.size();
  oss << " #types=" << transition_types_.size();
  oss << " spec='" << future_spec_ << "'";
  return oss.str();
}

bool TimeZoneInfo::NextTransition(time_point<sys_seconds>* tp) const {
  if (transitions_.empty()) return false;
  const Transition* begin = &transitions_[0];
  const Transition* end = begin + transitions_.size();
  if (begin->unix_time <= -(1LL << 59)) {
    // Do not report the BIG_BANG found in recent zoneinfo data as it is
    // really a sentinel, not a transition.  See tz/zic.c.
    ++begin;
  }
  std::int_fast64_t unix_time = ToUnixSeconds(*tp);
  const Transition target = { unix_time };
  const Transition* tr = std::upper_bound(begin, end, target,
                                          Transition::ByUnixTime());
  if (tr != begin) {  // skip no-op transitions
    for (; tr != end; ++tr) {
      if (!EquivTransitions(tr[-1].type_index, tr[0].type_index)) break;
    }
  }
  // When tr == end we return false, ignoring future_spec_.
  if (tr == end) return false;
  *tp = FromUnixSeconds(tr->unix_time);
  return true;
}

bool TimeZoneInfo::PrevTransition(time_point<sys_seconds>* tp) const {
  if (transitions_.empty()) return false;
  const Transition* begin = &transitions_[0];
  const Transition* end = begin + transitions_.size();
  if (begin->unix_time <= -(1LL << 59)) {
    // Do not report the BIG_BANG found in recent zoneinfo data as it is
    // really a sentinel, not a transition.  See tz/zic.c.
    ++begin;
  }
  std::int_fast64_t unix_time = ToUnixSeconds(*tp);
  if (FromUnixSeconds(unix_time) != *tp) {
    if (unix_time == std::numeric_limits<std::int_fast64_t>::max()) {
      if (end == begin) return false;  // Ignore future_spec_.
      *tp = FromUnixSeconds((--end)->unix_time);
      return true;
    }
    unix_time += 1;  // ceils
  }
  const Transition target = { unix_time };
  const Transition* tr = std::lower_bound(begin, end, target,
                                          Transition::ByUnixTime());
  if (tr != begin) {  // skip no-op transitions
    for (; tr - 1 != begin; --tr) {
      if (!EquivTransitions(tr[-2].type_index, tr[-1].type_index)) break;
    }
  }
  // When tr == end we return the "last" transition, ignoring future_spec_.
  if (tr == begin) return false;
  *tp = FromUnixSeconds((--tr)->unix_time);
  return true;
}

}  // namespace cctz
}  // namespace time_internal
}  // namespace absl