1// Copyright 2016 Google Inc. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15// This file implements the TimeZoneIf interface using the "zoneinfo"
16// data provided by the IANA Time Zone Database (i.e., the only real game
17// in town).
18//
19// TimeZoneInfo represents the history of UTC-offset changes within a time
20// zone. Most changes are due to daylight-saving rules, but occasionally
21// shifts are made to the time-zone's base offset. The database only attempts
22// to be definitive for times since 1970, so be wary of local-time conversions
23// before that. Also, rule and zone-boundary changes are made at the whim
24// of governments, so the conversion of future times needs to be taken with
25// a grain of salt.
26//
27// For more information see tzfile(5), http://www.iana.org/time-zones, or
28// http://en.wikipedia.org/wiki/Zoneinfo.
29//
30// Note that we assume the proleptic Gregorian calendar and 60-second
31// minutes throughout.
32
33#include "time_zone_info.h"
34
35#include <algorithm>
36#include <cassert>
37#include <chrono>
38#include <cstdint>
39#include <cstdio>
40#include <cstdlib>
41#include <cstring>
42#include <functional>
43#include <iostream>
44#include <memory>
45#include <sstream>
46#include <string>
47
48#include "cctz/civil_time.h"
49#include "time_zone_fixed.h"
50#include "time_zone_posix.h"
51
52namespace cctz {
53
54namespace {
55
56inline bool IsLeap(cctz::year_t year) {
57 return (year % 4) == 0 && ((year % 100) != 0 || (year % 400) == 0);
58}
59
60// The number of days in non-leap and leap years respectively.
61const std::int_least32_t kDaysPerYear[2] = {365, 366};
62
63// The day offsets of the beginning of each (1-based) month in non-leap and
64// leap years respectively (e.g., 335 days before December in a leap year).
65const std::int_least16_t kMonthOffsets[2][1 + 12 + 1] = {
66 {-1, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365},
67 {-1, 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366},
68};
69
70// We reject leap-second encoded zoneinfo and so assume 60-second minutes.
71const std::int_least32_t kSecsPerDay = 24 * 60 * 60;
72
73// 400-year chunks always have 146097 days (20871 weeks).
74const std::int_least64_t kSecsPer400Years = 146097LL * kSecsPerDay;
75
76// Like kDaysPerYear[] but scaled up by a factor of kSecsPerDay.
77const std::int_least32_t kSecsPerYear[2] = {
78 365 * kSecsPerDay,
79 366 * kSecsPerDay,
80};
81
82// Single-byte, unsigned numeric values are encoded directly.
83inline std::uint_fast8_t Decode8(const char* cp) {
84 return static_cast<std::uint_fast8_t>(*cp) & 0xff;
85}
86
87// Multi-byte, numeric values are encoded using a MSB first,
88// twos-complement representation. These helpers decode, from
89// the given address, 4-byte and 8-byte values respectively.
90// Note: If int_fastXX_t == intXX_t and this machine is not
91// twos complement, then there will be at least one input value
92// we cannot represent.
93std::int_fast32_t Decode32(const char* cp) {
94 std::uint_fast32_t v = 0;
95 for (int i = 0; i != (32 / 8); ++i) v = (v << 8) | Decode8(cp++);
96 const std::int_fast32_t s32max = 0x7fffffff;
97 const auto s32maxU = static_cast<std::uint_fast32_t>(s32max);
98 if (v <= s32maxU) return static_cast<std::int_fast32_t>(v);
99 return static_cast<std::int_fast32_t>(v - s32maxU - 1) - s32max - 1;
100}
101
102std::int_fast64_t Decode64(const char* cp) {
103 std::uint_fast64_t v = 0;
104 for (int i = 0; i != (64 / 8); ++i) v = (v << 8) | Decode8(cp++);
105 const std::int_fast64_t s64max = 0x7fffffffffffffff;
106 const auto s64maxU = static_cast<std::uint_fast64_t>(s64max);
107 if (v <= s64maxU) return static_cast<std::int_fast64_t>(v);
108 return static_cast<std::int_fast64_t>(v - s64maxU - 1) - s64max - 1;
109}
110
111// Generate a year-relative offset for a PosixTransition.
112std::int_fast64_t TransOffset(bool leap_year, int jan1_weekday,
113 const PosixTransition& pt) {
114 std::int_fast64_t days = 0;
115 switch (pt.date.fmt) {
116 case PosixTransition::J: {
117 days = pt.date.j.day;
118 if (!leap_year || days < kMonthOffsets[1][3]) days -= 1;
119 break;
120 }
121 case PosixTransition::N: {
122 days = pt.date.n.day;
123 break;
124 }
125 case PosixTransition::M: {
126 const bool last_week = (pt.date.m.week == 5);
127 days = kMonthOffsets[leap_year][pt.date.m.month + last_week];
128 const std::int_fast64_t weekday = (jan1_weekday + days) % 7;
129 if (last_week) {
130 days -= (weekday + 7 - 1 - pt.date.m.weekday) % 7 + 1;
131 } else {
132 days += (pt.date.m.weekday + 7 - weekday) % 7;
133 days += (pt.date.m.week - 1) * 7;
134 }
135 break;
136 }
137 }
138 return (days * kSecsPerDay) + pt.time.offset;
139}
140
141inline time_zone::civil_lookup MakeUnique(const time_point<sys_seconds>& tp) {
142 time_zone::civil_lookup cl;
143 cl.kind = time_zone::civil_lookup::UNIQUE;
144 cl.pre = cl.trans = cl.post = tp;
145 return cl;
146}
147
148inline time_zone::civil_lookup MakeUnique(std::int_fast64_t unix_time) {
149 return MakeUnique(FromUnixSeconds(unix_time));
150}
151
152inline time_zone::civil_lookup MakeSkipped(const Transition& tr,
153 const civil_second& cs) {
154 time_zone::civil_lookup cl;
155 cl.kind = time_zone::civil_lookup::SKIPPED;
156 cl.pre = FromUnixSeconds(tr.unix_time - 1 + (cs - tr.prev_civil_sec));
157 cl.trans = FromUnixSeconds(tr.unix_time);
158 cl.post = FromUnixSeconds(tr.unix_time - (tr.civil_sec - cs));
159 return cl;
160}
161
162inline time_zone::civil_lookup MakeRepeated(const Transition& tr,
163 const civil_second& cs) {
164 time_zone::civil_lookup cl;
165 cl.kind = time_zone::civil_lookup::REPEATED;
166 cl.pre = FromUnixSeconds(tr.unix_time - 1 - (tr.prev_civil_sec - cs));
167 cl.trans = FromUnixSeconds(tr.unix_time);
168 cl.post = FromUnixSeconds(tr.unix_time + (cs - tr.civil_sec));
169 return cl;
170}
171
172inline civil_second YearShift(const civil_second& cs, cctz::year_t shift) {
173 return civil_second(cs.year() + shift, cs.month(), cs.day(),
174 cs.hour(), cs.minute(), cs.second());
175}
176
177} // namespace
178
179// What (no leap-seconds) UTC+seconds zoneinfo would look like.
180bool TimeZoneInfo::ResetToBuiltinUTC(const sys_seconds& offset) {
181 transition_types_.resize(1);
182 TransitionType& tt(transition_types_.back());
183 tt.utc_offset = static_cast<std::int_least32_t>(offset.count());
184 tt.is_dst = false;
185 tt.abbr_index = 0;
186
187 // We temporarily add some redundant, contemporary (2012 through 2021)
188 // transitions for performance reasons. See TimeZoneInfo::LocalTime().
189 // TODO: Fix the performance issue and remove the extra transitions.
190 transitions_.clear();
191 transitions_.reserve(12);
192 for (const std::int_fast64_t unix_time : {
193 -(1LL << 59), // BIG_BANG
194 1325376000LL, // 2012-01-01T00:00:00+00:00
195 1356998400LL, // 2013-01-01T00:00:00+00:00
196 1388534400LL, // 2014-01-01T00:00:00+00:00
197 1420070400LL, // 2015-01-01T00:00:00+00:00
198 1451606400LL, // 2016-01-01T00:00:00+00:00
199 1483228800LL, // 2017-01-01T00:00:00+00:00
200 1514764800LL, // 2018-01-01T00:00:00+00:00
201 1546300800LL, // 2019-01-01T00:00:00+00:00
202 1577836800LL, // 2020-01-01T00:00:00+00:00
203 1609459200LL, // 2021-01-01T00:00:00+00:00
204 2147483647LL, // 2^31 - 1
205 }) {
206 Transition& tr(*transitions_.emplace(transitions_.end()));
207 tr.unix_time = unix_time;
208 tr.type_index = 0;
209 tr.civil_sec = LocalTime(tr.unix_time, tt).cs;
210 tr.prev_civil_sec = tr.civil_sec - 1;
211 }
212
213 default_transition_type_ = 0;
214 abbreviations_ = FixedOffsetToAbbr(offset);
215 abbreviations_.append(1, '\0'); // add NUL
216 future_spec_.clear(); // never needed for a fixed-offset zone
217 extended_ = false;
218
219 tt.civil_max = LocalTime(sys_seconds::max().count(), tt).cs;
220 tt.civil_min = LocalTime(sys_seconds::min().count(), tt).cs;
221
222 transitions_.shrink_to_fit();
223 return true;
224}
225
226// Builds the in-memory header using the raw bytes from the file.
227bool TimeZoneInfo::Header::Build(const tzhead& tzh) {
228 std::int_fast32_t v;
229 if ((v = Decode32(tzh.tzh_timecnt)) < 0) return false;
230 timecnt = static_cast<std::size_t>(v);
231 if ((v = Decode32(tzh.tzh_typecnt)) < 0) return false;
232 typecnt = static_cast<std::size_t>(v);
233 if ((v = Decode32(tzh.tzh_charcnt)) < 0) return false;
234 charcnt = static_cast<std::size_t>(v);
235 if ((v = Decode32(tzh.tzh_leapcnt)) < 0) return false;
236 leapcnt = static_cast<std::size_t>(v);
237 if ((v = Decode32(tzh.tzh_ttisstdcnt)) < 0) return false;
238 ttisstdcnt = static_cast<std::size_t>(v);
239 if ((v = Decode32(tzh.tzh_ttisgmtcnt)) < 0) return false;
240 ttisgmtcnt = static_cast<std::size_t>(v);
241 return true;
242}
243
244// How many bytes of data are associated with this header. The result
245// depends upon whether this is a section with 4-byte or 8-byte times.
246std::size_t TimeZoneInfo::Header::DataLength(std::size_t time_len) const {
247 std::size_t len = 0;
248 len += (time_len + 1) * timecnt; // unix_time + type_index
249 len += (4 + 1 + 1) * typecnt; // utc_offset + is_dst + abbr_index
250 len += 1 * charcnt; // abbreviations
251 len += (time_len + 4) * leapcnt; // leap-time + TAI-UTC
252 len += 1 * ttisstdcnt; // UTC/local indicators
253 len += 1 * ttisgmtcnt; // standard/wall indicators
254 return len;
255}
256
257// Check that the TransitionType has the expected offset/is_dst/abbreviation.
258void TimeZoneInfo::CheckTransition(const std::string& name,
259 const TransitionType& tt,
260 std::int_fast32_t offset, bool is_dst,
261 const std::string& abbr) const {
262 if (tt.utc_offset != offset || tt.is_dst != is_dst ||
263 &abbreviations_[tt.abbr_index] != abbr) {
264 std::clog << name << ": Transition"
265 << " offset=" << tt.utc_offset << "/"
266 << (tt.is_dst ? "DST" : "STD")
267 << "/abbr=" << &abbreviations_[tt.abbr_index]
268 << " does not match POSIX spec '" << future_spec_ << "'\n";
269 }
270}
271
272// zic(8) can generate no-op transitions when a zone changes rules at an
273// instant when there is actually no discontinuity. So we check whether
274// two transitions have equivalent types (same offset/is_dst/abbr).
275bool TimeZoneInfo::EquivTransitions(std::uint_fast8_t tt1_index,
276 std::uint_fast8_t tt2_index) const {
277 if (tt1_index == tt2_index) return true;
278 const TransitionType& tt1(transition_types_[tt1_index]);
279 const TransitionType& tt2(transition_types_[tt2_index]);
280 if (tt1.is_dst != tt2.is_dst) return false;
281 if (tt1.utc_offset != tt2.utc_offset) return false;
282 if (tt1.abbr_index != tt2.abbr_index) return false;
283 return true;
284}
285
286// Use the POSIX-TZ-environment-variable-style string to handle times
287// in years after the last transition stored in the zoneinfo data.
288void TimeZoneInfo::ExtendTransitions(const std::string& name,
289 const Header& hdr) {
290 extended_ = false;
291 bool extending = !future_spec_.empty();
292
293 PosixTimeZone posix;
294 if (extending && !ParsePosixSpec(future_spec_, &posix)) {
295 std::clog << name << ": Failed to parse '" << future_spec_ << "'\n";
296 extending = false;
297 }
298
299 if (extending && posix.dst_abbr.empty()) { // std only
300 // The future specification should match the last/default transition,
301 // and that means that handling the future will fall out naturally.
302 std::uint_fast8_t index = default_transition_type_;
303 if (hdr.timecnt != 0) index = transitions_[hdr.timecnt - 1].type_index;
304 const TransitionType& tt(transition_types_[index]);
305 CheckTransition(name, tt, posix.std_offset, false, posix.std_abbr);
306 extending = false;
307 }
308
309 if (extending && hdr.timecnt < 2) {
310 std::clog << name << ": Too few transitions for POSIX spec\n";
311 extending = false;
312 }
313
314 if (!extending) {
315 // Ensure that there is always a transition in the second half of the
316 // time line (the BIG_BANG transition is in the first half) so that the
317 // signed difference between a civil_second and the civil_second of its
318 // previous transition is always representable, without overflow.
319 const Transition& last(transitions_.back());
320 if (last.unix_time < 0) {
321 const std::uint_fast8_t type_index = last.type_index;
322 Transition& tr(*transitions_.emplace(transitions_.end()));
323 tr.unix_time = 2147483647; // 2038-01-19T03:14:07+00:00
324 tr.type_index = type_index;
325 }
326 return; // last transition wins
327 }
328
329 // Extend the transitions for an additional 400 years using the
330 // future specification. Years beyond those can be handled by
331 // mapping back to a cycle-equivalent year within that range.
332 // zic(8) should probably do this so that we don't have to.
333 // TODO: Reduce the extension by the number of compatible
334 // transitions already in place.
335 transitions_.reserve(hdr.timecnt + 400 * 2 + 1);
336 transitions_.resize(hdr.timecnt + 400 * 2);
337 extended_ = true;
338
339 // The future specification should match the last two transitions,
340 // and those transitions should have different is_dst flags.
341 const Transition* tr0 = &transitions_[hdr.timecnt - 1];
342 const Transition* tr1 = &transitions_[hdr.timecnt - 2];
343 const TransitionType* tt0 = &transition_types_[tr0->type_index];
344 const TransitionType* tt1 = &transition_types_[tr1->type_index];
345 const TransitionType& spring(tt0->is_dst ? *tt0 : *tt1);
346 const TransitionType& autumn(tt0->is_dst ? *tt1 : *tt0);
347 CheckTransition(name, spring, posix.dst_offset, true, posix.dst_abbr);
348 CheckTransition(name, autumn, posix.std_offset, false, posix.std_abbr);
349
350 // Add the transitions to tr1 and back to tr0 for each extra year.
351 last_year_ = LocalTime(tr0->unix_time, *tt0).cs.year();
352 bool leap_year = IsLeap(last_year_);
353 const civil_day jan1(last_year_, 1, 1);
354 std::int_fast64_t jan1_time = civil_second(jan1) - civil_second();
355 int jan1_weekday = (static_cast<int>(get_weekday(jan1)) + 1) % 7;
356 Transition* tr = &transitions_[hdr.timecnt]; // next trans to fill
357 if (LocalTime(tr1->unix_time, *tt1).cs.year() != last_year_) {
358 // Add a single extra transition to align to a calendar year.
359 transitions_.resize(transitions_.size() + 1);
360 assert(tr == &transitions_[hdr.timecnt]); // no reallocation
361 const PosixTransition& pt1(tt0->is_dst ? posix.dst_end : posix.dst_start);
362 std::int_fast64_t tr1_offset = TransOffset(leap_year, jan1_weekday, pt1);
363 tr->unix_time = jan1_time + tr1_offset - tt0->utc_offset;
364 tr++->type_index = tr1->type_index;
365 tr0 = &transitions_[hdr.timecnt];
366 tr1 = &transitions_[hdr.timecnt - 1];
367 tt0 = &transition_types_[tr0->type_index];
368 tt1 = &transition_types_[tr1->type_index];
369 }
370 const PosixTransition& pt1(tt0->is_dst ? posix.dst_end : posix.dst_start);
371 const PosixTransition& pt0(tt0->is_dst ? posix.dst_start : posix.dst_end);
372 for (const cctz::year_t limit = last_year_ + 400; last_year_ < limit;) {
373 last_year_ += 1; // an additional year of generated transitions
374 jan1_time += kSecsPerYear[leap_year];
375 jan1_weekday = (jan1_weekday + kDaysPerYear[leap_year]) % 7;
376 leap_year = !leap_year && IsLeap(last_year_);
377 std::int_fast64_t tr1_offset = TransOffset(leap_year, jan1_weekday, pt1);
378 tr->unix_time = jan1_time + tr1_offset - tt0->utc_offset;
379 tr++->type_index = tr1->type_index;
380 std::int_fast64_t tr0_offset = TransOffset(leap_year, jan1_weekday, pt0);
381 tr->unix_time = jan1_time + tr0_offset - tt1->utc_offset;
382 tr++->type_index = tr0->type_index;
383 }
384 assert(tr == &transitions_[0] + transitions_.size());
385}
386
387bool TimeZoneInfo::Load(const std::string& name, ZoneInfoSource* zip) {
388 // Read and validate the header.
389 tzhead tzh;
390 if (zip->Read(&tzh, sizeof(tzh)) != sizeof(tzh))
391 return false;
392 if (strncmp(tzh.tzh_magic, TZ_MAGIC, sizeof(tzh.tzh_magic)) != 0)
393 return false;
394 Header hdr;
395 if (!hdr.Build(tzh))
396 return false;
397 std::size_t time_len = 4;
398 if (tzh.tzh_version[0] != '\0') {
399 // Skip the 4-byte data.
400 if (zip->Skip(hdr.DataLength(time_len)) != 0)
401 return false;
402 // Read and validate the header for the 8-byte data.
403 if (zip->Read(&tzh, sizeof(tzh)) != sizeof(tzh))
404 return false;
405 if (strncmp(tzh.tzh_magic, TZ_MAGIC, sizeof(tzh.tzh_magic)) != 0)
406 return false;
407 if (tzh.tzh_version[0] == '\0')
408 return false;
409 if (!hdr.Build(tzh))
410 return false;
411 time_len = 8;
412 }
413 if (hdr.typecnt == 0)
414 return false;
415 if (hdr.leapcnt != 0) {
416 // This code assumes 60-second minutes so we do not want
417 // the leap-second encoded zoneinfo. We could reverse the
418 // compensation, but the "right" encoding is rarely used
419 // so currently we simply reject such data.
420 return false;
421 }
422 if (hdr.ttisstdcnt != 0 && hdr.ttisstdcnt != hdr.typecnt)
423 return false;
424 if (hdr.ttisgmtcnt != 0 && hdr.ttisgmtcnt != hdr.typecnt)
425 return false;
426
427 // Read the data into a local buffer.
428 std::size_t len = hdr.DataLength(time_len);
429 std::vector<char> tbuf(len);
430 if (zip->Read(tbuf.data(), len) != len)
431 return false;
432 const char* bp = tbuf.data();
433
434 // Decode and validate the transitions.
435 transitions_.reserve(hdr.timecnt + 2); // We might add a couple.
436 transitions_.resize(hdr.timecnt);
437 for (std::size_t i = 0; i != hdr.timecnt; ++i) {
438 transitions_[i].unix_time = (time_len == 4) ? Decode32(bp) : Decode64(bp);
439 bp += time_len;
440 if (i != 0) {
441 // Check that the transitions are ordered by time (as zic guarantees).
442 if (!Transition::ByUnixTime()(transitions_[i - 1], transitions_[i]))
443 return false; // out of order
444 }
445 }
446 bool seen_type_0 = false;
447 for (std::size_t i = 0; i != hdr.timecnt; ++i) {
448 transitions_[i].type_index = Decode8(bp++);
449 if (transitions_[i].type_index >= hdr.typecnt)
450 return false;
451 if (transitions_[i].type_index == 0)
452 seen_type_0 = true;
453 }
454
455 // Decode and validate the transition types.
456 transition_types_.resize(hdr.typecnt);
457 for (std::size_t i = 0; i != hdr.typecnt; ++i) {
458 transition_types_[i].utc_offset =
459 static_cast<std::int_least32_t>(Decode32(bp));
460 if (transition_types_[i].utc_offset >= kSecsPerDay ||
461 transition_types_[i].utc_offset <= -kSecsPerDay)
462 return false;
463 bp += 4;
464 transition_types_[i].is_dst = (Decode8(bp++) != 0);
465 transition_types_[i].abbr_index = Decode8(bp++);
466 if (transition_types_[i].abbr_index >= hdr.charcnt)
467 return false;
468 }
469
470 // Determine the before-first-transition type.
471 default_transition_type_ = 0;
472 if (seen_type_0 && hdr.timecnt != 0) {
473 std::uint_fast8_t index = 0;
474 if (transition_types_[0].is_dst) {
475 index = transitions_[0].type_index;
476 while (index != 0 && transition_types_[index].is_dst)
477 --index;
478 }
479 while (index != hdr.typecnt && transition_types_[index].is_dst)
480 ++index;
481 if (index != hdr.typecnt)
482 default_transition_type_ = index;
483 }
484
485 // Copy all the abbreviations.
486 abbreviations_.assign(bp, hdr.charcnt);
487 bp += hdr.charcnt;
488
489 // Skip the unused portions. We've already dispensed with leap-second
490 // encoded zoneinfo. The ttisstd/ttisgmt indicators only apply when
491 // interpreting a POSIX spec that does not include start/end rules, and
492 // that isn't the case here (see "zic -p").
493 bp += (8 + 4) * hdr.leapcnt; // leap-time + TAI-UTC
494 bp += 1 * hdr.ttisstdcnt; // UTC/local indicators
495 bp += 1 * hdr.ttisgmtcnt; // standard/wall indicators
496 assert(bp == tbuf.data() + tbuf.size());
497
498 future_spec_.clear();
499 if (tzh.tzh_version[0] != '\0') {
500 // Snarf up the NL-enclosed future POSIX spec. Note
501 // that version '3' files utilize an extended format.
502 auto get_char = [](ZoneInfoSource* zip) -> int {
503 unsigned char ch; // all non-EOF results are positive
504 return (zip->Read(&ch, 1) == 1) ? ch : EOF;
505 };
506 if (get_char(zip) != '\n')
507 return false;
508 for (int c = get_char(zip); c != '\n'; c = get_char(zip)) {
509 if (c == EOF)
510 return false;
511 future_spec_.push_back(static_cast<char>(c));
512 }
513 }
514
515 // We don't check for EOF so that we're forwards compatible.
516
517 // Trim redundant transitions. zic may have added these to work around
518 // differences between the glibc and reference implementations (see
519 // zic.c:dontmerge) and the Qt library (see zic.c:WORK_AROUND_QTBUG_53071).
520 // For us, they just get in the way when we do future_spec_ extension.
521 while (hdr.timecnt > 1) {
522 if (!EquivTransitions(transitions_[hdr.timecnt - 1].type_index,
523 transitions_[hdr.timecnt - 2].type_index)) {
524 break;
525 }
526 hdr.timecnt -= 1;
527 }
528 transitions_.resize(hdr.timecnt);
529
530 // Ensure that there is always a transition in the first half of the
531 // time line (the second half is handled in ExtendTransitions()) so that
532 // the signed difference between a civil_second and the civil_second of
533 // its previous transition is always representable, without overflow.
534 // A contemporary zic will usually have already done this for us.
535 if (transitions_.empty() || transitions_.front().unix_time >= 0) {
536 Transition& tr(*transitions_.emplace(transitions_.begin()));
537 tr.unix_time = -(1LL << 59); // see tz/zic.c "BIG_BANG"
538 tr.type_index = default_transition_type_;
539 hdr.timecnt += 1;
540 }
541
542 // Extend the transitions using the future specification.
543 ExtendTransitions(name, hdr);
544
545 // Compute the local civil time for each transition and the preceding
546 // second. These will be used for reverse conversions in MakeTime().
547 const TransitionType* ttp = &transition_types_[default_transition_type_];
548 for (std::size_t i = 0; i != transitions_.size(); ++i) {
549 Transition& tr(transitions_[i]);
550 tr.prev_civil_sec = LocalTime(tr.unix_time, *ttp).cs - 1;
551 ttp = &transition_types_[tr.type_index];
552 tr.civil_sec = LocalTime(tr.unix_time, *ttp).cs;
553 if (i != 0) {
554 // Check that the transitions are ordered by civil time. Essentially
555 // this means that an offset change cannot cross another such change.
556 // No one does this in practice, and we depend on it in MakeTime().
557 if (!Transition::ByCivilTime()(transitions_[i - 1], tr))
558 return false; // out of order
559 }
560 }
561
562 // Compute the maximum/minimum civil times that can be converted to a
563 // time_point<sys_seconds> for each of the zone's transition types.
564 for (auto& tt : transition_types_) {
565 tt.civil_max = LocalTime(sys_seconds::max().count(), tt).cs;
566 tt.civil_min = LocalTime(sys_seconds::min().count(), tt).cs;
567 }
568
569 transitions_.shrink_to_fit();
570 return true;
571}
572
573namespace {
574
575// A stdio(3)-backed implementation of ZoneInfoSource.
576class FileZoneInfoSource : public ZoneInfoSource {
577 public:
578 static std::unique_ptr<ZoneInfoSource> Open(const std::string& name);
579
580 std::size_t Read(void* ptr, std::size_t size) override {
581 return fread(ptr, 1, size, fp_);
582 }
583 int Skip(std::size_t offset) override {
584 return fseek(fp_, static_cast<long>(offset), SEEK_CUR);
585 }
586
587 private:
588 explicit FileZoneInfoSource(FILE* fp) : fp_(fp) {}
589 ~FileZoneInfoSource() { fclose(fp_); }
590
591 FILE* const fp_;
592};
593
594std::unique_ptr<ZoneInfoSource> FileZoneInfoSource::Open(
595 const std::string& name) {
596 // Use of the "file:" prefix is intended for testing purposes only.
597 if (name.compare(0, 5, "file:") == 0) return Open(name.substr(5));
598
599 // Map the time-zone name to a path name.
600 std::string path;
601 if (name.empty() || name[0] != '/') {
602 const char* tzdir = "/usr/share/zoneinfo";
603 char* tzdir_env = nullptr;
604#if defined(_MSC_VER)
605 _dupenv_s(&tzdir_env, nullptr, "TZDIR");
606#else
607 tzdir_env = std::getenv("TZDIR");
608#endif
609 if (tzdir_env && *tzdir_env) tzdir = tzdir_env;
610 path += tzdir;
611 path += '/';
612#if defined(_MSC_VER)
613 free(tzdir_env);
614#endif
615 }
616 path += name;
617
618 // Open the zoneinfo file.
619#if defined(_MSC_VER)
620 FILE* fp;
621 if (fopen_s(&fp, path.c_str(), "rb") != 0) fp = nullptr;
622#else
623 FILE* fp = fopen(path.c_str(), "rb");
624#endif
625 if (fp == nullptr) return nullptr;
626 return std::unique_ptr<ZoneInfoSource>(new FileZoneInfoSource(fp));
627}
628
629} // namespace
630
631bool TimeZoneInfo::Load(const std::string& name) {
632 // We can ensure that the loading of UTC or any other fixed-offset
633 // zone never fails because the simple, fixed-offset state can be
634 // internally generated. Note that this depends on our choice to not
635 // accept leap-second encoded ("right") zoneinfo.
636 auto offset = sys_seconds::zero();
637 if (FixedOffsetFromName(name, &offset)) {
638 return ResetToBuiltinUTC(offset);
639 }
640
641 // Find and use a ZoneInfoSource to load the named zone.
642 auto zip = cctz_extension::zone_info_source_factory(
643 name, [](const std::string& name) {
644 return FileZoneInfoSource::Open(name); // fallback factory
645 });
646 return zip != nullptr && Load(name, zip.get());
647}
648
649// BreakTime() translation for a particular transition type.
650time_zone::absolute_lookup TimeZoneInfo::LocalTime(
651 std::int_fast64_t unix_time, const TransitionType& tt) const {
652 // A civil time in "+offset" looks like (time+offset) in UTC.
653 // Note: We perform two additions in the civil_second domain to
654 // sidestep the chance of overflow in (unix_time + tt.utc_offset).
655 return {(civil_second() + unix_time) + tt.utc_offset,
656 tt.utc_offset, tt.is_dst, &abbreviations_[tt.abbr_index]};
657}
658
659// BreakTime() translation for a particular transition.
660time_zone::absolute_lookup TimeZoneInfo::LocalTime(
661 std::int_fast64_t unix_time, const Transition& tr) const {
662 const TransitionType& tt = transition_types_[tr.type_index];
663 // Note: (unix_time - tr.unix_time) will never overflow as we
664 // have ensured that there is always a "nearby" transition.
665 return {tr.civil_sec + (unix_time - tr.unix_time), // TODO: Optimize.
666 tt.utc_offset, tt.is_dst, &abbreviations_[tt.abbr_index]};
667}
668
669// MakeTime() translation with a conversion-preserving +N * 400-year shift.
670time_zone::civil_lookup TimeZoneInfo::TimeLocal(const civil_second& cs,
671 cctz::year_t c4_shift) const {
672 assert(last_year_ - 400 < cs.year() && cs.year() <= last_year_);
673 time_zone::civil_lookup cl = MakeTime(cs);
674 if (c4_shift > sys_seconds::max().count() / kSecsPer400Years) {
675 cl.pre = cl.trans = cl.post = time_point<sys_seconds>::max();
676 } else {
677 const auto offset = sys_seconds(c4_shift * kSecsPer400Years);
678 const auto limit = time_point<sys_seconds>::max() - offset;
679 for (auto* tp : {&cl.pre, &cl.trans, &cl.post}) {
680 if (*tp > limit) {
681 *tp = time_point<sys_seconds>::max();
682 } else {
683 *tp += offset;
684 }
685 }
686 }
687 return cl;
688}
689
690time_zone::absolute_lookup TimeZoneInfo::BreakTime(
691 const time_point<sys_seconds>& tp) const {
692 std::int_fast64_t unix_time = ToUnixSeconds(tp);
693 const std::size_t timecnt = transitions_.size();
694 assert(timecnt != 0); // We always add a transition.
695
696 if (unix_time < transitions_[0].unix_time) {
697 return LocalTime(unix_time, transition_types_[default_transition_type_]);
698 }
699 if (unix_time >= transitions_[timecnt - 1].unix_time) {
700 // After the last transition. If we extended the transitions using
701 // future_spec_, shift back to a supported year using the 400-year
702 // cycle of calendaric equivalence and then compensate accordingly.
703 if (extended_) {
704 const std::int_fast64_t diff =
705 unix_time - transitions_[timecnt - 1].unix_time;
706 const cctz::year_t shift = diff / kSecsPer400Years + 1;
707 const auto d = sys_seconds(shift * kSecsPer400Years);
708 time_zone::absolute_lookup al = BreakTime(tp - d);
709 al.cs = YearShift(al.cs, shift * 400);
710 return al;
711 }
712 return LocalTime(unix_time, transitions_[timecnt - 1]);
713 }
714
715 const std::size_t hint = local_time_hint_.load(std::memory_order_relaxed);
716 if (0 < hint && hint < timecnt) {
717 if (transitions_[hint - 1].unix_time <= unix_time) {
718 if (unix_time < transitions_[hint].unix_time) {
719 return LocalTime(unix_time, transitions_[hint - 1]);
720 }
721 }
722 }
723
724 const Transition target = {unix_time, 0, civil_second(), civil_second()};
725 const Transition* begin = &transitions_[0];
726 const Transition* tr = std::upper_bound(begin, begin + timecnt, target,
727 Transition::ByUnixTime());
728 local_time_hint_.store(static_cast<std::size_t>(tr - begin),
729 std::memory_order_relaxed);
730 return LocalTime(unix_time, *--tr);
731}
732
733time_zone::civil_lookup TimeZoneInfo::MakeTime(const civil_second& cs) const {
734 const std::size_t timecnt = transitions_.size();
735 assert(timecnt != 0); // We always add a transition.
736
737 // Find the first transition after our target civil time.
738 const Transition* tr = nullptr;
739 const Transition* begin = &transitions_[0];
740 const Transition* end = begin + timecnt;
741 if (cs < begin->civil_sec) {
742 tr = begin;
743 } else if (cs >= transitions_[timecnt - 1].civil_sec) {
744 tr = end;
745 } else {
746 const std::size_t hint = time_local_hint_.load(std::memory_order_relaxed);
747 if (0 < hint && hint < timecnt) {
748 if (transitions_[hint - 1].civil_sec <= cs) {
749 if (cs < transitions_[hint].civil_sec) {
750 tr = begin + hint;
751 }
752 }
753 }
754 if (tr == nullptr) {
755 const Transition target = {0, 0, cs, civil_second()};
756 tr = std::upper_bound(begin, end, target, Transition::ByCivilTime());
757 time_local_hint_.store(static_cast<std::size_t>(tr - begin),
758 std::memory_order_relaxed);
759 }
760 }
761
762 if (tr == begin) {
763 if (tr->prev_civil_sec >= cs) {
764 // Before first transition, so use the default offset.
765 const TransitionType& tt(transition_types_[default_transition_type_]);
766 if (cs < tt.civil_min) return MakeUnique(time_point<sys_seconds>::min());
767 return MakeUnique(cs - (civil_second() + tt.utc_offset));
768 }
769 // tr->prev_civil_sec < cs < tr->civil_sec
770 return MakeSkipped(*tr, cs);
771 }
772
773 if (tr == end) {
774 if (cs > (--tr)->prev_civil_sec) {
775 // After the last transition. If we extended the transitions using
776 // future_spec_, shift back to a supported year using the 400-year
777 // cycle of calendaric equivalence and then compensate accordingly.
778 if (extended_ && cs.year() > last_year_) {
779 const cctz::year_t shift = (cs.year() - last_year_ - 1) / 400 + 1;
780 return TimeLocal(YearShift(cs, shift * -400), shift);
781 }
782 const TransitionType& tt(transition_types_[tr->type_index]);
783 if (cs > tt.civil_max) return MakeUnique(time_point<sys_seconds>::max());
784 return MakeUnique(tr->unix_time + (cs - tr->civil_sec));
785 }
786 // tr->civil_sec <= cs <= tr->prev_civil_sec
787 return MakeRepeated(*tr, cs);
788 }
789
790 if (tr->prev_civil_sec < cs) {
791 // tr->prev_civil_sec < cs < tr->civil_sec
792 return MakeSkipped(*tr, cs);
793 }
794
795 if (cs <= (--tr)->prev_civil_sec) {
796 // tr->civil_sec <= cs <= tr->prev_civil_sec
797 return MakeRepeated(*tr, cs);
798 }
799
800 // In between transitions.
801 return MakeUnique(tr->unix_time + (cs - tr->civil_sec));
802}
803
804std::string TimeZoneInfo::Description() const {
805 std::ostringstream oss;
806 // TODO: It would nice if the zoneinfo data included the zone name.
807 // TODO: It would nice if the zoneinfo data included the tzdb version.
808 oss << "#trans=" << transitions_.size();
809 oss << " #types=" << transition_types_.size();
810 oss << " spec='" << future_spec_ << "'";
811 return oss.str();
812}
813
814bool TimeZoneInfo::NextTransition(time_point<sys_seconds>* tp) const {
815 if (transitions_.empty()) return false;
816 const Transition* begin = &transitions_[0];
817 const Transition* end = begin + transitions_.size();
818 if (begin->unix_time <= -(1LL << 59)) {
819 // Do not report the BIG_BANG found in recent zoneinfo data as it is
820 // really a sentinel, not a transition. See third_party/tz/zic.c.
821 ++begin;
822 }
823 std::int_fast64_t unix_time = ToUnixSeconds(*tp);
824 const Transition target = { unix_time };
825 const Transition* tr = std::upper_bound(begin, end, target,
826 Transition::ByUnixTime());
827 if (tr != begin) { // skip no-op transitions
828 for (; tr != end; ++tr) {
829 if (!EquivTransitions(tr[-1].type_index, tr[0].type_index)) break;
830 }
831 }
832 // When tr == end we return false, ignoring future_spec_.
833 if (tr == end) return false;
834 *tp = FromUnixSeconds(tr->unix_time);
835 return true;
836}
837
838bool TimeZoneInfo::PrevTransition(time_point<sys_seconds>* tp) const {
839 if (transitions_.empty()) return false;
840 const Transition* begin = &transitions_[0];
841 const Transition* end = begin + transitions_.size();
842 if (begin->unix_time <= -(1LL << 59)) {
843 // Do not report the BIG_BANG found in recent zoneinfo data as it is
844 // really a sentinel, not a transition. See third_party/tz/zic.c.
845 ++begin;
846 }
847 std::int_fast64_t unix_time = ToUnixSeconds(*tp);
848 if (FromUnixSeconds(unix_time) != *tp) {
849 if (unix_time == std::numeric_limits<std::int_fast64_t>::max()) {
850 if (end == begin) return false; // Ignore future_spec_.
851 *tp = FromUnixSeconds((--end)->unix_time);
852 return true;
853 }
854 unix_time += 1; // ceils
855 }
856 const Transition target = { unix_time };
857 const Transition* tr = std::lower_bound(begin, end, target,
858 Transition::ByUnixTime());
859 if (tr != begin) { // skip no-op transitions
860 for (; tr - 1 != begin; --tr) {
861 if (!EquivTransitions(tr[-2].type_index, tr[-1].type_index)) break;
862 }
863 }
864 // When tr == end we return the "last" transition, ignoring future_spec_.
865 if (tr == begin) return false;
866 *tp = FromUnixSeconds((--tr)->unix_time);
867 return true;
868}
869
870} // namespace cctz
871