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