1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// For information see https://libcxx.llvm.org/DesignDocs/TimeZone.html
10
11// TODO TZDB look at optimizations
12//
13// The current algorithm is correct but not efficient. For example, in a named
14// rule based continuation finding the next rule does quite a bit of work,
15// returns the next rule and "forgets" its state. This could be better.
16//
17// It would be possible to cache lookups. If a time for a zone is calculated its
18// sys_info could be kept and the next lookup could test whether the time is in
19// a "known" sys_info. The wording in the Standard hints at this slowness by
20// "suggesting" this could be implemented on the user's side.
21
22// TODO TZDB look at removing quirks
23//
24// The code has some special rules to adjust the timing at the continuation
25// switches. This works correctly, but some of the places feel odd. It would be
26// good to investigate this further and see whether all quirks are needed or
27// that there are better fixes.
28//
29// These quirks often use a 12h interval; this is the scan interval of zdump,
30// which implies there are no sys_info objects with a duration of less than 12h.
31
32// Work around https://gcc.gnu.org/bugzilla/show_bug.cgi?id=120502
33
34#include <__config>
35
36// TODO(LLVM 23): When upgrading to GCC 16 this can be removed
37#ifdef _LIBCPP_COMPILER_GCC
38# pragma GCC optimize("-O0")
39#endif
40
41#include <algorithm>
42#include <cctype>
43#include <chrono>
44#include <expected>
45#include <map>
46#include <numeric>
47#include <ranges>
48
49#include "include/tzdb/time_zone_private.h"
50#include "include/tzdb/tzdb_list_private.h"
51
52// TODO TZDB remove debug printing
53#ifdef PRINT
54# include <print>
55#endif
56
57_LIBCPP_BEGIN_NAMESPACE_STD
58_LIBCPP_BEGIN_EXPLICIT_ABI_ANNOTATIONS
59
60#ifdef PRINT
61template <>
62struct formatter<chrono::sys_info, char> {
63 template <class ParseContext>
64 constexpr typename ParseContext::iterator parse(ParseContext& ctx) {
65 return ctx.begin();
66 }
67
68 template <class FormatContext>
69 typename FormatContext::iterator format(const chrono::sys_info& info, FormatContext& ctx) const {
70 return std::format_to(
71 ctx.out(), "[{}, {}) {:%Q%q} {:%Q%q} {}", info.begin, info.end, info.offset, info.save, info.abbrev);
72 }
73};
74#endif
75
76namespace chrono {
77
78//===----------------------------------------------------------------------===//
79// Details
80//===----------------------------------------------------------------------===//
81
82struct __sys_info {
83 sys_info __info;
84 bool __can_merge; // Can the returned sys_info object be merged with
85};
86
87// Return type for helper function to get a sys_info.
88// - The expected result returns the "best" sys_info object. This object can be
89// before the requested time. Sometimes sys_info objects from different
90// continuations share their offset, save, and abbrev and these objects are
91// merged to one sys_info object. The __can_merge flag determines whether the
92// current result can be merged with the next result.
93// - The unexpected result means no sys_info object was found and the time is
94// the time to be used for the next search iteration.
95using __sys_info_result = expected<__sys_info, sys_seconds>;
96
97template <ranges::forward_range _Range,
98 class _Type,
99 class _Proj = identity,
100 indirect_strict_weak_order<const _Type*, projected<ranges::iterator_t<_Range>, _Proj>> _Comp = ranges::less>
101[[nodiscard]] static ranges::borrowed_iterator_t<_Range>
102__binary_find(_Range&& __r, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) {
103 auto __end = ranges::end(__r);
104 auto __ret = ranges::lower_bound(ranges::begin(__r), __end, __value, __comp, __proj);
105 if (__ret == __end)
106 return __end;
107
108 // When the value does not match the predicate it's equal and a valid result
109 // was found.
110 return !std::invoke(__comp, __value, std::invoke(__proj, *__ret)) ? __ret : __end;
111}
112
113// Format based on https://data.iana.org/time-zones/tz-how-to.html
114//
115// 1 a time zone abbreviation that is a string of three or more characters that
116// are either ASCII alphanumerics, "+", or "-"
117// 2 the string "%z", in which case the "%z" will be replaced by a numeric time
118// zone abbreviation
119// 3 a pair of time zone abbreviations separated by a slash ('/'), in which
120// case the first string is the abbreviation for the standard time name and
121// the second string is the abbreviation for the daylight saving time name
122// 4 a string containing "%s", in which case the "%s" will be replaced by the
123// text in the appropriate Rule's LETTER column, and the resulting string
124// should be a time zone abbreviation
125//
126// Rule 1 is not strictly validated since America/Barbados uses a two letter
127// abbreviation AT.
128[[nodiscard]] static string
129__format(const __tz::__continuation& __continuation, const string& __letters, seconds __save) {
130 bool __shift = false;
131 string __result;
132 for (char __c : __continuation.__format) {
133 if (__shift) {
134 switch (__c) {
135 case 's':
136 std::ranges::copy(__letters, std::back_inserter(x&: __result));
137 break;
138
139 case 'z': {
140 if (__continuation.__format.size() != 2)
141 std::__throw_runtime_error(
142 std::format(fmt: "corrupt tzdb FORMAT field: %z should be the entire contents, instead contains '{}'",
143 args: __continuation.__format)
144 .c_str());
145 chrono::hh_mm_ss __offset{__continuation.__stdoff + __save};
146 if (__offset.is_negative()) {
147 __result += '-';
148 __offset = chrono::hh_mm_ss{-(__continuation.__stdoff + __save)};
149 } else
150 __result += '+';
151
152 if (__offset.minutes() != 0min)
153 std::format_to(out_it: std::back_inserter(x&: __result), fmt: "{:%H%M}", args&: __offset);
154 else
155 std::format_to(out_it: std::back_inserter(x&: __result), fmt: "{:%H}", args&: __offset);
156 } break;
157
158 default:
159 std::__throw_runtime_error(
160 std::format(fmt: "corrupt tzdb FORMAT field: invalid sequence '%{}' found, expected %s or %z", args&: __c).c_str());
161 }
162 __shift = false;
163
164 } else if (__c == '/') {
165 if (__save != 0s)
166 __result.clear();
167 else
168 break;
169
170 } else if (__c == '%') {
171 __shift = true;
172 } else if (__c == '+' || __c == '-' || std::isalnum(__c)) {
173 __result.push_back(__c);
174 } else {
175 std::__throw_runtime_error(
176 std::format(
177 fmt: "corrupt tzdb FORMAT field: invalid character '{}' found, expected +, -, or an alphanumeric value", args&: __c)
178 .c_str());
179 }
180 }
181
182 if (__shift)
183 std::__throw_runtime_error("corrupt tzdb FORMAT field: input ended with the start of the escape sequence '%'");
184
185 if (__result.empty())
186 std::__throw_runtime_error("corrupt tzdb FORMAT field: result is empty");
187
188 return __result;
189}
190
191[[nodiscard]] static sys_seconds __to_sys_seconds(year_month_day __ymd, seconds __seconds) {
192 seconds __result = static_cast<sys_days>(__ymd).time_since_epoch() + __seconds;
193 return sys_seconds{__result};
194}
195
196[[nodiscard]] static seconds __at_to_sys_seconds(const __tz::__continuation& __continuation) {
197 switch (__continuation.__at.__clock) {
198 case __tz::__clock::__local:
199 return __continuation.__at.__time - __continuation.__stdoff -
200 std::visit(
201 visitor: [](const auto& __value) {
202 using _Tp = decay_t<decltype(__value)>;
203 if constexpr (same_as<_Tp, monostate>)
204 return chrono::seconds{0};
205 else if constexpr (same_as<_Tp, __tz::__save>)
206 return chrono::duration_cast<seconds>(__value.__time);
207 else if constexpr (same_as<_Tp, std::string>)
208 // For a named rule based continuation the SAVE depends on the RULE
209 // active at the end. This should be determined separately.
210 return chrono::seconds{0};
211 else
212 static_assert(false);
213 },
214 vs: __continuation.__rules);
215
216 case __tz::__clock::__universal:
217 return __continuation.__at.__time;
218
219 case __tz::__clock::__standard:
220 return __continuation.__at.__time - __continuation.__stdoff;
221 }
222 std::__libcpp_unreachable();
223}
224
225[[nodiscard]] static year_month_day __to_year_month_day(year __year, month __month, __tz::__on __on) {
226 return std::visit(
227 visitor: [&](const auto& __value) {
228 using _Tp = decay_t<decltype(__value)>;
229 if constexpr (same_as<_Tp, chrono::day>)
230 return year_month_day{__year, __month, __value};
231 else if constexpr (same_as<_Tp, weekday_last>)
232 return year_month_day{static_cast<sys_days>(year_month_weekday_last{__year, __month, __value})};
233 else if constexpr (same_as<_Tp, __tz::__constrained_weekday>)
234 return __value(__year, __month);
235 else
236 static_assert(false);
237 },
238 vs&: __on);
239}
240
241[[nodiscard]] static sys_seconds __until_to_sys_seconds(const __tz::__continuation& __continuation) {
242 // Does UNTIL contain the magic value for the last continuation?
243 if (__continuation.__year == chrono::year::min())
244 return sys_seconds::max();
245
246 year_month_day __ymd = chrono::__to_year_month_day(year: __continuation.__year, month: __continuation.__in, on: __continuation.__on);
247 return chrono::__to_sys_seconds(__ymd, seconds: chrono::__at_to_sys_seconds(__continuation));
248}
249
250// Holds the UNTIL time for a continuation with a named rule.
251//
252// Unlike continuations with an fixed SAVE named rules have a variable SAVE.
253// This means when the UNTIL uses the local wall time the actual UNTIL value can
254// only be determined when the SAVE is known. This class holds that abstraction.
255class __named_rule_until {
256public:
257 explicit __named_rule_until(const __tz::__continuation& __continuation)
258 : __until_{chrono::__until_to_sys_seconds(__continuation)},
259 __needs_adjustment_{
260 // The last continuation of a ZONE has no UNTIL which basically is
261 // until the end of _local_ time. This value is expressed by
262 // sys_seconds::max(). Subtracting the SAVE leaves large value.
263 // However SAVE can be negative, which would add a value to maximum
264 // leading to undefined behaviour. In practice this often results in
265 // an overflow to a very small value.
266 __until_ != sys_seconds::max() && __continuation.__at.__clock == __tz::__clock::__local} {}
267
268 // Gives the unadjusted until value, this is useful when the SAVE is not known
269 // at all.
270 sys_seconds __until() const noexcept { return __until_; }
271
272 bool __needs_adjustment() const noexcept { return __needs_adjustment_; }
273
274 // Returns the UNTIL adjusted for SAVE.
275 sys_seconds operator()(seconds __save) const noexcept { return __until_ - __needs_adjustment_ * __save; }
276
277private:
278 sys_seconds __until_;
279 bool __needs_adjustment_;
280};
281
282[[nodiscard]] static seconds __at_to_seconds(seconds __stdoff, const __tz::__rule& __rule) {
283 switch (__rule.__at.__clock) {
284 case __tz::__clock::__local:
285 // Local time and standard time behave the same. This is not
286 // correct. Local time needs to adjust for the current saved time.
287 // To know the saved time the rules need to be known and sorted.
288 // This needs a time so to avoid the chicken and egg adjust the
289 // saving of the local time later.
290 return __rule.__at.__time - __stdoff;
291
292 case __tz::__clock::__universal:
293 return __rule.__at.__time;
294
295 case __tz::__clock::__standard:
296 return __rule.__at.__time - __stdoff;
297 }
298 std::__libcpp_unreachable();
299}
300
301[[nodiscard]] static sys_seconds __from_to_sys_seconds(seconds __stdoff, const __tz::__rule& __rule, year __year) {
302 year_month_day __ymd = chrono::__to_year_month_day(__year, month: __rule.__in, on: __rule.__on);
303
304 seconds __at = chrono::__at_to_seconds(__stdoff, __rule);
305 return chrono::__to_sys_seconds(__ymd, seconds: __at);
306}
307
308[[nodiscard]] static sys_seconds __from_to_sys_seconds(seconds __stdoff, const __tz::__rule& __rule) {
309 return chrono::__from_to_sys_seconds(__stdoff, __rule, year: __rule.__from);
310}
311
312[[nodiscard]] static const vector<__tz::__rule>&
313__get_rules(const __tz::__rules_storage_type& __rules_db, const string& __rule_name) {
314 auto __result = chrono::__binary_find(r: __rules_db, value: __rule_name, comp: {}, proj: [](const auto& __p) { return __p.first; });
315 if (__result == std::end(c: __rules_db))
316 std::__throw_runtime_error(("corrupt tzdb: rule '" + __rule_name + " 'does not exist").c_str());
317
318 return __result->second;
319}
320
321// Returns the letters field for a time before the first rule.
322//
323// Per https://data.iana.org/time-zones/tz-how-to.html
324// One wrinkle, not fully explained in zic.8.txt, is what happens when switching
325// to a named rule. To what values should the SAVE and LETTER data be
326// initialized?
327//
328// 1 If at least one transition has happened, use the SAVE and LETTER data from
329// the most recent.
330// 2 If switching to a named rule before any transition has happened, assume
331// standard time (SAVE zero), and use the LETTER data from the earliest
332// transition with a SAVE of zero.
333//
334// This function implements case 2.
335[[nodiscard]] static string __letters_before_first_rule(const vector<__tz::__rule>& __rules) {
336 auto __letters =
337 __rules //
338 | views::filter([](const __tz::__rule& __rule) { return __rule.__save.__time == 0s; }) //
339 | views::transform([](const __tz::__rule& __rule) { return __rule.__letters; }) //
340 | views::take(1);
341
342 if (__letters.empty())
343 std::__throw_runtime_error("corrupt tzdb: rule has zero entries");
344
345 return __letters.front();
346}
347
348// Determines the information based on the continuation and the rules.
349//
350// There are several special cases to take into account
351//
352// === Entries before the first rule becomes active ===
353// Asia/Hong_Kong
354// 9 - JST 1945 N 18 2 // (1)
355// 8 HK HK%sT // (2)
356// R HK 1946 o - Ap 21 0 1 S // (3)
357// There (1) is active until Novemer 18th 1945 at 02:00, after this time
358// (2) becomes active. The first rule entry for HK (3) becomes active
359// from April 21st 1945 at 01:00. In the period between (2) is active.
360// This entry has an offset.
361// This entry has no save, letters, or dst flag. So in the period
362// after (1) and until (3) no rule entry is associated with the time.
363
364[[nodiscard]] static sys_info __get_sys_info_before_first_rule(
365 sys_seconds __begin,
366 sys_seconds __end,
367 const __tz::__continuation& __continuation,
368 const vector<__tz::__rule>& __rules) {
369 return sys_info{
370 .begin: __begin,
371 .end: __end,
372 .offset: __continuation.__stdoff,
373 .save: chrono::minutes(0),
374 .abbrev: chrono::__format(__continuation, letters: __letters_before_first_rule(__rules), save: 0s)};
375}
376
377// Returns the sys_info object for a time before the first rule.
378// When this first rule has a SAVE of 0s the sys_info for the time before the
379// first rule and for the first rule are identical and will be merged.
380[[nodiscard]] static sys_info __get_sys_info_before_first_rule(
381 sys_seconds __begin,
382 sys_seconds __rule_end, // The end used when SAVE != 0s
383 sys_seconds __next_end, // The end used when SAVE == 0s the times are merged
384 const __tz::__continuation& __continuation,
385 const vector<__tz::__rule>& __rules,
386 vector<__tz::__rule>::const_iterator __rule) {
387 if (__rule->__save.__time != 0s)
388 return __get_sys_info_before_first_rule(__begin, end: __rule_end, __continuation, __rules);
389
390 return sys_info{
391 .begin: __begin, .end: __next_end, .offset: __continuation.__stdoff, .save: 0min, .abbrev: chrono::__format(__continuation, letters: __rule->__letters, save: 0s)};
392}
393
394[[nodiscard]] static seconds __at_to_seconds(seconds __stdoff, seconds __save, const __tz::__rule& __rule) {
395 switch (__rule.__at.__clock) {
396 case __tz::__clock::__local:
397 return __rule.__at.__time - __stdoff - __save;
398
399 case __tz::__clock::__universal:
400 return __rule.__at.__time;
401
402 case __tz::__clock::__standard:
403 return __rule.__at.__time - __stdoff;
404 }
405 std::__libcpp_unreachable();
406}
407
408[[nodiscard]] static sys_seconds
409__rule_to_sys_seconds(seconds __stdoff, seconds __save, const __tz::__rule& __rule, year __year) {
410 year_month_day __ymd = chrono::__to_year_month_day(__year, month: __rule.__in, on: __rule.__on);
411
412 seconds __at = chrono::__at_to_seconds(__stdoff, __save, __rule);
413 return chrono::__to_sys_seconds(__ymd, seconds: __at);
414}
415
416// Returns the first rule after __time.
417// Note that a rule can be "active" in multiple years, this may result in an
418// infinite loop where the same rule is returned every time, use __current to
419// guard against that.
420//
421// When no next rule exists the returned time will be sys_seconds::max(). This
422// can happen in practice. For example,
423//
424// R So 1945 o - May 24 2 2 M
425// R So 1945 o - S 24 3 1 S
426// R So 1945 o - N 18 2s 0 -
427//
428// Has 3 rules that are all only active in 1945.
429[[nodiscard]] static pair<sys_seconds, vector<__tz::__rule>::const_iterator>
430__next_rule(sys_seconds __time,
431 seconds __stdoff,
432 seconds __save,
433 const vector<__tz::__rule>& __rules,
434 vector<__tz::__rule>::const_iterator __current) {
435 year __year = year_month_day{chrono::floor<days>(t: __time)}.year();
436
437 // Note it would probably be better to store the pairs in a vector and then
438 // use min() to get the smallest element
439 map<sys_seconds, vector<__tz::__rule>::const_iterator> __candidates;
440 // Note this evaluates all rules which is a waste of effort; when the entries
441 // are beyond the current year's "next year" (where "next year" is not always
442 // year + 1) the algorithm should end.
443 for (auto __it = __rules.begin(); __it != __rules.end(); ++__it) {
444 for (year __y = __it->__from; __y <= __it->__to; ++__y) {
445 // Adding the current entry for the current year may lead to infinite
446 // loops due to the SAVE adjustment. Skip these entries.
447 if (__y == __year && __it == __current)
448 continue;
449
450 sys_seconds __t = chrono::__rule_to_sys_seconds(__stdoff, __save, rule: *__it, year: __y);
451 if (__t <= __time)
452 continue;
453
454 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(!__candidates.contains(__t), "duplicated rule");
455 __candidates[__t] = __it;
456 break;
457 }
458 }
459
460 if (!__candidates.empty()) [[likely]] {
461 auto __it = __candidates.begin();
462
463 // When no rule is selected the time before the first rule and the first rule
464 // should not be merged.
465 if (__time == sys_seconds::min())
466 return *__it;
467
468 // There can be two constitutive rules that are the same. For example,
469 // Hong Kong
470 //
471 // R HK 1973 o - D 30 3:30 1 S (R1)
472 // R HK 1965 1976 - Ap Su>=16 3:30 1 S (R2)
473 //
474 // 1973-12-29 19:30:00 R1 becomes active.
475 // 1974-04-20 18:30:00 R2 becomes active.
476 // Both rules have a SAVE of 1 hour and LETTERS are S for both of them.
477 while (__it != __candidates.end()) {
478 if (__current->__save.__time != __it->second->__save.__time || __current->__letters != __it->second->__letters)
479 return *__it;
480
481 ++__it;
482 }
483 }
484
485 return {sys_seconds::max(), __rules.end()};
486}
487
488// Returns the first rule of a set of rules.
489// This is not always the first of the listed rules. For example
490// R Sa 2008 2009 - Mar Su>=8 0 0 -
491// R Sa 2007 2008 - O Su>=8 0 1 -
492// The transition in October 2007 happens before the transition in March 2008.
493[[nodiscard]] static vector<__tz::__rule>::const_iterator
494__first_rule(seconds __stdoff, const vector<__tz::__rule>& __rules) {
495 return chrono::__next_rule(time: sys_seconds::min(), __stdoff, save: 0s, __rules, current: __rules.end()).second;
496}
497
498[[nodiscard]] static __sys_info_result __get_sys_info_rule(
499 sys_seconds __time,
500 sys_seconds __continuation_begin,
501 const __tz::__continuation& __continuation,
502 const vector<__tz::__rule>& __rules) {
503 auto __rule = chrono::__first_rule(stdoff: __continuation.__stdoff, __rules);
504 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(__rule != __rules.end(), "the set of rules has no first rule");
505
506 // Avoid selecting a time before the start of the continuation
507 __time = std::max(a: __time, b: __continuation_begin);
508
509 sys_seconds __rule_begin = chrono::__from_to_sys_seconds(stdoff: __continuation.__stdoff, rule: *__rule);
510
511 // The time sought is very likely inside the current rule.
512 // When the continuation's UNTIL uses the local clock there are edge cases
513 // where this is not true.
514 //
515 // Start to walk the rules to find the proper one.
516 //
517 // For now we just walk all the rules TODO TZDB investigate whether a smarter
518 // algorithm would work.
519 auto __next = chrono::__next_rule(time: __rule_begin, stdoff: __continuation.__stdoff, save: __rule->__save.__time, __rules, current: __rule);
520
521 // Ignore small steps, this happens with America/Punta_Arenas for the
522 // transition
523 // -4:42:46 - SMT 1927 S
524 // -5 x -05/-04 1932 S
525 // ...
526 //
527 // R x 1927 1931 - S 1 0 1 -
528 // R x 1928 1932 - Ap 1 0 0 -
529 //
530 // America/Punta_Arenas Thu Sep 1 04:42:45 1927 UT = Thu Sep 1 00:42:45 1927 -04 isdst=1 gmtoff=-14400
531 // America/Punta_Arenas Sun Apr 1 03:59:59 1928 UT = Sat Mar 31 23:59:59 1928 -04 isdst=1 gmtoff=-14400
532 // America/Punta_Arenas Sun Apr 1 04:00:00 1928 UT = Sat Mar 31 23:00:00 1928 -05 isdst=0 gmtoff=-18000
533 //
534 // Without this there will be a transition
535 // [1927-09-01 04:42:45, 1927-09-01 05:00:00) -05:00:00 0min -05
536
537 if (sys_seconds __begin = __rule->__save.__time != 0s ? __rule_begin : __next.first; __time < __begin) {
538 if (__continuation_begin == sys_seconds::min() || __begin - __continuation_begin > 12h)
539 return __sys_info{__get_sys_info_before_first_rule(
540 begin: __continuation_begin, rule_end: __rule_begin, next_end: __next.first, __continuation, __rules, __rule),
541 false};
542
543 // Europe/Berlin
544 // 1 c CE%sT 1945 May 24 2 (C1)
545 // 1 So CE%sT 1946 (C2)
546 //
547 // R c 1944 1945 - Ap M>=1 2s 1 S (R1)
548 //
549 // R So 1945 o - May 24 2 2 M (R2)
550 //
551 // When C2 becomes active the time would be before the first rule R2,
552 // giving a 1 hour sys_info.
553 seconds __save = __rule->__save.__time;
554 __named_rule_until __continuation_end{__continuation};
555 sys_seconds __sys_info_end = std::min(a: __continuation_end(__save), b: __next.first);
556
557 return __sys_info{
558 sys_info{.begin: __continuation_begin,
559 .end: __sys_info_end,
560 .offset: __continuation.__stdoff + __save,
561 .save: chrono::duration_cast<minutes>(fd: __save),
562 .abbrev: chrono::__format(__continuation, letters: __rule->__letters, __save)},
563 __sys_info_end == __continuation_end(__save)};
564 }
565
566 // See above for America/Asuncion
567 if (__rule->__save.__time == 0s && __time < __next.first) {
568 return __sys_info{
569 sys_info{.begin: __continuation_begin,
570 .end: __next.first,
571 .offset: __continuation.__stdoff,
572 .save: 0min,
573 .abbrev: chrono::__format(__continuation, letters: __rule->__letters, save: 0s)},
574 false};
575 }
576
577 if (__rule->__save.__time != 0s) {
578 // another fix for America/Punta_Arenas when not at the start of the
579 // sys_info object.
580 seconds __save = __rule->__save.__time;
581 if (__continuation_begin >= __rule_begin - __save && __time < __next.first) {
582 return __sys_info{
583 sys_info{.begin: __continuation_begin,
584 .end: __next.first,
585 .offset: __continuation.__stdoff + __save,
586 .save: chrono::duration_cast<minutes>(fd: __save),
587 .abbrev: chrono::__format(__continuation, letters: __rule->__letters, __save)},
588 false};
589 }
590 }
591
592 __named_rule_until __continuation_end{__continuation};
593 while (__next.second != __rules.end()) {
594#ifdef PRINT
595 std::print(
596 stderr,
597 "Rule for {}: [{}, {}) off={} save={} duration={}\n",
598 __time,
599 __rule_begin,
600 __next.first,
601 __continuation.__stdoff,
602 __rule->__save.__time,
603 __next.first - __rule_begin);
604#endif
605
606 sys_seconds __end = __continuation_end(__rule->__save.__time);
607
608 sys_seconds __sys_info_begin = std::max(a: __continuation_begin, b: __rule_begin);
609 sys_seconds __sys_info_end = std::min(a: __end, b: __next.first);
610 seconds __diff = chrono::abs(d: __sys_info_end - __sys_info_begin);
611
612 if (__diff < 12h) {
613 // Z America/Argentina/Buenos_Aires -3:53:48 - LMT 1894 O 31
614 // -4:16:48 - CMT 1920 May
615 // -4 - -04 1930 D
616 // -4 A -04/-03 1969 O 5
617 // -3 A -03/-02 1999 O 3
618 // -4 A -04/-03 2000 Mar 3
619 // ...
620 //
621 // ...
622 // R A 1989 1992 - O Su>=15 0 1 -
623 // R A 1999 o - O Su>=1 0 1 -
624 // R A 2000 o - Mar 3 0 0 -
625 // R A 2007 o - D 30 0 1 -
626 // ...
627
628 // The 1999 switch uses the same rule, but with a different stdoff.
629 // R A 1999 o - O Su>=1 0 1 -
630 // stdoff -3 -> 1999-10-03 03:00:00
631 // stdoff -4 -> 1999-10-03 04:00:00
632 // This generates an invalid entry and this is evaluated as a transition.
633 // Looking at the zdump like output in libc++ this generates jumps in
634 // the UTC time.
635
636 __rule = __next.second;
637 __next = __next_rule(time: __next.first, stdoff: __continuation.__stdoff, save: __rule->__save.__time, __rules, current: __rule);
638 __end = __continuation_end(__rule->__save.__time);
639 __sys_info_end = std::min(a: __end, b: __next.first);
640 }
641
642 if ((__time >= __rule_begin && __time < __next.first) || __next.first >= __end) {
643 __sys_info_begin = std::max(a: __continuation_begin, b: __rule_begin);
644 __sys_info_end = std::min(a: __end, b: __next.first);
645
646 return __sys_info{
647 sys_info{.begin: __sys_info_begin,
648 .end: __sys_info_end,
649 .offset: __continuation.__stdoff + __rule->__save.__time,
650 .save: chrono::duration_cast<minutes>(fd: __rule->__save.__time),
651 .abbrev: chrono::__format(__continuation, letters: __rule->__letters, save: __rule->__save.__time)},
652 __sys_info_end == __end};
653 }
654
655 __rule_begin = __next.first;
656 __rule = __next.second;
657 __next = __next_rule(time: __rule_begin, stdoff: __continuation.__stdoff, save: __rule->__save.__time, __rules, current: __rule);
658 }
659
660 return __sys_info{
661 sys_info{.begin: std::max(a: __continuation_begin, b: __rule_begin),
662 .end: __continuation_end(__rule->__save.__time),
663 .offset: __continuation.__stdoff + __rule->__save.__time,
664 .save: chrono::duration_cast<minutes>(fd: __rule->__save.__time),
665 .abbrev: chrono::__format(__continuation, letters: __rule->__letters, save: __rule->__save.__time)},
666 true};
667}
668
669[[nodiscard]] static __sys_info_result __get_sys_info_basic(
670 sys_seconds __time, sys_seconds __continuation_begin, const __tz::__continuation& __continuation, seconds __save) {
671 sys_seconds __continuation_end = chrono::__until_to_sys_seconds(__continuation);
672 return __sys_info{
673 sys_info{.begin: __continuation_begin,
674 .end: __continuation_end,
675 .offset: __continuation.__stdoff + __save,
676 .save: chrono::duration_cast<minutes>(fd: __save),
677 .abbrev: chrono::__format(__continuation, letters: __continuation.__format, __save)},
678 true};
679}
680
681[[nodiscard]] static __sys_info_result
682__get_sys_info(sys_seconds __time,
683 sys_seconds __continuation_begin,
684 const __tz::__continuation& __continuation,
685 const __tz::__rules_storage_type& __rules_db) {
686 return std::visit(
687 visitor: [&](const auto& __value) {
688 using _Tp = decay_t<decltype(__value)>;
689 if constexpr (same_as<_Tp, std::string>)
690 return chrono::__get_sys_info_rule(
691 __time, __continuation_begin, __continuation, rules: __get_rules(__rules_db, __value));
692 else if constexpr (same_as<_Tp, monostate>)
693 return chrono::__get_sys_info_basic(__time, __continuation_begin, __continuation, save: chrono::seconds(0));
694 else if constexpr (same_as<_Tp, __tz::__save>)
695 return chrono::__get_sys_info_basic(__time, __continuation_begin, __continuation, save: __value.__time);
696 else
697 static_assert(false);
698 },
699 vs: __continuation.__rules);
700}
701
702// The transition from one continuation to the next continuation may result in
703// two constitutive continuations with the same "offset" information.
704// [time.zone.info.sys]/3
705// The begin and end data members indicate that, for the associated time_zone
706// and time_point, the offset and abbrev are in effect in the range
707// [begin, end). This information can be used to efficiently iterate the
708// transitions of a time_zone.
709//
710// Note that this does considers a change in the SAVE field not to be a
711// different sys_info, zdump does consider this different.
712// LWG XXXX The sys_info range should be affected by save
713// matches the behaviour of the Standard and zdump.
714//
715// Iff the "offsets" are the same '__current.__end' is replaced with
716// '__next.__end', which effectively merges the two objects in one object. The
717// function returns true if a merge occurred.
718[[nodiscard]] static bool __merge_continuation(sys_info& __current, const sys_info& __next) {
719 if (__current.end != __next.begin)
720 return false;
721
722 if (__current.offset != __next.offset || __current.abbrev != __next.abbrev || __current.save != __next.save)
723 return false;
724
725 __current.end = __next.end;
726 return true;
727}
728
729//===----------------------------------------------------------------------===//
730// Public API
731//===----------------------------------------------------------------------===//
732
733[[nodiscard]] _LIBCPP_EXPORTED_FROM_ABI time_zone time_zone::__create(unique_ptr<time_zone::__impl>&& __p) {
734 _LIBCPP_ASSERT_NON_NULL(__p != nullptr, "initialized time_zone without a valid pimpl object");
735 time_zone result;
736 result.__impl_ = std::move(__p);
737 return result;
738}
739
740_LIBCPP_EXPORTED_FROM_ABI time_zone::~time_zone() = default;
741
742[[nodiscard]] _LIBCPP_EXPORTED_FROM_ABI string_view time_zone::__name() const noexcept { return __impl_->__name(); }
743
744[[nodiscard]] _LIBCPP_AVAILABILITY_TZDB _LIBCPP_EXPORTED_FROM_ABI sys_info
745time_zone::__get_info(sys_seconds __time) const {
746 optional<sys_info> __result;
747 bool __valid_result = false; // true iff __result.has_value() is true and
748 // __result.begin <= __time < __result.end is true.
749 bool __can_merge = false;
750 sys_seconds __continuation_begin = sys_seconds::min();
751 // Iterates over the Zone entry and its continuations. Internally the Zone
752 // entry is split in a Zone information and the first continuation. The last
753 // continuation has no UNTIL field. This means the loop should always find a
754 // continuation.
755 //
756 // For more information on background of zone information please consult the
757 // following information
758 // [zic manual](https://www.man7.org/linux/man-pages/man8/zic.8.html)
759 // [tz source info](https://data.iana.org/time-zones/tz-how-to.html)
760 // On POSIX systems the zdump tool can be useful:
761 // zdump -v Asia/Hong_Kong
762 // Gives all transitions in the Hong Kong time zone.
763 //
764 // During iteration the result for the current continuation is returned. If
765 // no continuation is applicable it will return the end time as "error". When
766 // two continuations are contiguous and contain the "same" information these
767 // ranges are merged as one range.
768 // The merging requires keeping any result that occurs before __time,
769 // likewise when a valid result is found the algorithm needs to test the next
770 // continuation to see whether it can be merged. For example, Africa/Ceuta
771 // Continuations
772 // 0 s WE%sT 1929 (C1)
773 // 0 - WET 1967 (C2)
774 // 0 Sp WE%sT 1984 Mar 16 (C3)
775 //
776 // Rules
777 // R s 1926 1929 - O Sa>=1 24s 0 - (R1)
778 //
779 // R Sp 1967 o - Jun 3 12 1 S (R2)
780 //
781 // The rule R1 is the last rule used in C1. The rule R2 is the first rule in
782 // C3. Since R2 is the first rule this means when a continuation uses this
783 // rule its value prior to R2 will be SAVE 0 LETTERS of the first entry with a
784 // SAVE of 0, in this case WET.
785 // This gives the following changes in the information.
786 // 1928-10-07 00:00:00 C1 R1 becomes active: offset 0 save 0 abbrev WET
787 // 1929-01-01 00:00:00 C2 becomes active: offset 0 save 0 abbrev WET
788 // 1967-01-01 00:00:00 C3 becomes active: offset 0 save 0 abbrev WET
789 // 1967-06-03 12:00:00 C3 R2 becomes active: offset 0 save 1 abbrev WEST
790 //
791 // The first 3 entries are contiguous and contain the same information, this
792 // means the period [1928-10-07 00:00:00, 1967-06-03 12:00:00) should be
793 // returned in one sys_info object.
794
795 const auto& __continuations = __impl_->__continuations();
796 const __tz::__rules_storage_type& __rules_db = __impl_->__rules_db();
797 for (auto __it = __continuations.begin(); __it != __continuations.end(); ++__it) {
798 const auto& __continuation = *__it;
799 __sys_info_result __sys_info = chrono::__get_sys_info(__time, __continuation_begin, __continuation, __rules_db);
800
801 if (__sys_info) {
802 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
803 __sys_info->__info.begin < __sys_info->__info.end, "invalid sys_info range");
804
805 // Filters out dummy entries
806 // Z America/Argentina/Buenos_Aires -3:53:48 - LMT 1894 O 31
807 // ...
808 // -4 A -04/-03 2000 Mar 3 (C1)
809 // -3 A -03/-02 (C2)
810 //
811 // ...
812 // R A 2000 o - Mar 3 0 0 -
813 // R A 2007 o - D 30 0 1 -
814 // ...
815 //
816 // This results in an entry
817 // [2000-03-03 03:00:00, 2000-03-03 04:00:00) -10800s 60min -03
818 // for [C1 & R1, C1, R2) which due to the end of the continuation is an
819 // one hour "sys_info". Instead the entry should be ignored and replaced
820 // by [C2 & R1, C2 & R2) which is the proper range
821 // "[2000-03-03 03:00:00, 2007-12-30 03:00:00) -02:00:00 60min -02
822
823 if (std::holds_alternative<string>(v: __continuation.__rules) && __sys_info->__can_merge &&
824 __sys_info->__info.begin + 12h > __sys_info->__info.end) {
825 __continuation_begin = __sys_info->__info.begin;
826 continue;
827 }
828
829 if (!__result) {
830 // First entry found, always keep it.
831 __result = __sys_info->__info;
832
833 __valid_result = __time >= __result->begin && __time < __result->end;
834 __can_merge = __sys_info->__can_merge;
835 } else if (__can_merge && chrono::__merge_continuation(current&: *__result, next: __sys_info->__info)) {
836 // The results are merged, update the result state. This may
837 // "overwrite" a valid sys_info object with another valid sys_info
838 // object.
839 __valid_result = __time >= __result->begin && __time < __result->end;
840 __can_merge = __sys_info->__can_merge;
841 } else {
842 // Here things get interesting:
843 // For example, America/Argentina/San_Luis
844 //
845 // -3 A -03/-02 2008 Ja 21 (C1)
846 // -4 Sa -04/-03 2009 O 11 (C2)
847 //
848 // R A 2007 o - D 30 0 1 - (R1)
849 //
850 // R Sa 2007 2008 - O Su>=8 0 1 - (R2)
851 //
852 // Based on C1 & R1 the end time of C1 is 2008-01-21 03:00:00
853 // Based on C2 & R2 the end time of C1 is 2008-01-21 02:00:00
854 // In this case the earlier time is the real time of the transition.
855 // However the algorithm used gives 2008-01-21 03:00:00.
856 //
857 // So we need to calculate the previous UNTIL in the current context and
858 // see whether it's earlier.
859
860 // The results could not be merged.
861 // - When we have a valid result that result is the final result.
862 // - Otherwise the result we had is before __time and the result we got
863 // is at a later time (possibly valid). This result is always better
864 // than the previous result.
865 if (__valid_result) {
866 return *__result;
867 } else {
868 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
869 __it != __continuations.begin(), "the first rule should always seed the result");
870 const auto& __last = *(__it - 1);
871 if (std::holds_alternative<string>(v: __last.__rules)) {
872 // Europe/Berlin
873 // 1 c CE%sT 1945 May 24 2 (C1)
874 // 1 So CE%sT 1946 (C2)
875 //
876 // R c 1944 1945 - Ap M>=1 2s 1 S (R1)
877 //
878 // R So 1945 o - May 24 2 2 M (R2)
879 //
880 // When C2 becomes active the time would be before the first rule R2,
881 // giving a 1 hour sys_info. This is not valid and the results need
882 // merging.
883
884 if (__result->end != __sys_info->__info.begin) {
885 // When the UTC gap between the rules is due to the change of
886 // offsets adjust the new time to remove the gap.
887 sys_seconds __end = __result->end - __result->offset;
888 sys_seconds __begin = __sys_info->__info.begin - __sys_info->__info.offset;
889 if (__end == __begin) {
890 __sys_info->__info.begin = __result->end;
891 }
892 }
893 }
894
895 __result = __sys_info->__info;
896 __valid_result = __time >= __result->begin && __time < __result->end;
897 __can_merge = __sys_info->__can_merge;
898 }
899 }
900 __continuation_begin = __result->end;
901 } else {
902 __continuation_begin = __sys_info.error();
903 }
904 }
905 if (__valid_result)
906 return *__result;
907
908 std::__throw_runtime_error("tzdb: corrupt db");
909}
910
911// Is the "__local_time" present in "__first" and "__second". If so the
912// local_info has an ambiguous result.
913[[nodiscard]] static bool
914__is_ambiguous(local_seconds __local_time, const sys_info& __first, const sys_info& __second) {
915 std::chrono::local_seconds __end_first{__first.end.time_since_epoch() + __first.offset};
916 std::chrono::local_seconds __begin_second{__second.begin.time_since_epoch() + __second.offset};
917
918 return __local_time < __end_first && __local_time >= __begin_second;
919}
920
921// Determines the result of the "__local_time". This expects the object
922// "__first" to be earlier in time than "__second".
923[[nodiscard]] static local_info
924__get_info(local_seconds __local_time, const sys_info& __first, const sys_info& __second) {
925 std::chrono::local_seconds __end_first{__first.end.time_since_epoch() + __first.offset};
926 std::chrono::local_seconds __begin_second{__second.begin.time_since_epoch() + __second.offset};
927
928 if (__local_time < __end_first) {
929 if (__local_time >= __begin_second)
930 // |--------|
931 // |------|
932 // ^
933 return {.result: local_info::ambiguous, .first: __first, .second: __second};
934
935 // |--------|
936 // |------|
937 // ^
938 return {.result: local_info::unique, .first: __first, .second: sys_info{}};
939 }
940
941 if (__local_time < __begin_second)
942 // |--------|
943 // |------|
944 // ^
945 return {.result: local_info::nonexistent, .first: __first, .second: __second};
946
947 // |--------|
948 // |------|
949 // ^
950 return {.result: local_info::unique, .first: __second, .second: sys_info{}};
951}
952
953[[nodiscard]] _LIBCPP_AVAILABILITY_TZDB _LIBCPP_EXPORTED_FROM_ABI local_info
954time_zone::__get_info(local_seconds __local_time) const {
955 seconds __local_seconds = __local_time.time_since_epoch();
956
957 /* An example of a typical year with a DST switch displayed in local time.
958 *
959 * At the first of April the time goes forward one hour. This means the
960 * time marked with ~~ is not a valid local time. This is represented by the
961 * nonexistent value in local_info.result.
962 *
963 * At the first of November the time goes backward one hour. This means the
964 * time marked with ^^ happens twice. This is represented by the ambiguous
965 * value in local_info.result.
966 *
967 * 2020.11.01 2021.04.01 2021.11.01
968 * offset +05 offset +05 offset +05
969 * save 0s save 1h save 0s
970 * |------------//----------|
971 * |---------//--------------|
972 * |-------------
973 * ~~ ^^
974 *
975 * These shifts can happen due to changes in the current time zone for a
976 * location. For example, Indian/Kerguelen switched only once. In 1950 from an
977 * offset of 0 hours to an offset of +05 hours.
978 *
979 * During all these shifts the UTC time will not have gaps.
980 */
981
982 // The code needs to determine the system time for the local time. There is no
983 // information available. Assume the offset between system time and local time
984 // is 0s. This gives an initial estimate.
985 sys_seconds __guess{__local_seconds};
986 sys_info __info = __get_info(time: __guess);
987
988 // At this point the offset can be used to determine an estimate for the local
989 // time. Before doing that, determine the offset and validate whether the
990 // local time is the range [chrono::local_seconds::min(),
991 // chrono::local_seconds::max()).
992 if (__local_seconds < 0s && __info.offset > 0s)
993 if (__local_seconds - chrono::local_seconds::min().time_since_epoch() < __info.offset)
994 return {.result: -1, .first: __info, .second: {}};
995
996 if (__local_seconds > 0s && __info.offset < 0s)
997 if (chrono::local_seconds::max().time_since_epoch() - __local_seconds < -__info.offset)
998 return {.result: -2, .first: __info, .second: {}};
999
1000 // Based on the information found in the sys_info, the local time can be
1001 // converted to a system time. This resulting time can be in the following
1002 // locations of the sys_info:
1003 //
1004 // |---------//--------------|
1005 // 1 2.1 2.2 2.3 3
1006 //
1007 // 1. The estimate is before the returned sys_info object.
1008 // The result is either non-existent or unique in the previous sys_info.
1009 // 2. The estimate is in the sys_info object
1010 // - If the sys_info begin is not sys_seconds::min(), then it might be at
1011 // 2.1 and could be ambiguous with the previous or unique.
1012 // - If sys_info end is not sys_seconds::max(), then it might be at 2.3
1013 // and could be ambiguous with the next or unique.
1014 // - Else it is at 2.2 and always unique. This case happens when a
1015 // time zone has no transitions. For example, UTC or GMT+1.
1016 // 3. The estimate is after the returned sys_info object.
1017 // The result is either non-existent or unique in the next sys_info.
1018 //
1019 // There is no specification where the "middle" starts. Similar issues can
1020 // happen when sys_info objects are "short", then "unique in the next" could
1021 // become "ambiguous in the next and the one following". Theoretically there
1022 // is the option of the following time-line
1023 //
1024 // |------------|
1025 // |----|
1026 // |-----------------|
1027 //
1028 // However the local_info object only has 2 sys_info objects, so this option
1029 // is not tested.
1030
1031 sys_seconds __sys_time{__local_seconds - __info.offset};
1032 if (__sys_time < __info.begin)
1033 // Case 1 before __info
1034 return chrono::__get_info(__local_time, first: __get_info(time: __info.begin - 1s), second: __info);
1035
1036 if (__sys_time >= __info.end)
1037 // Case 3 after __info
1038 return chrono::__get_info(__local_time, first: __info, second: __get_info(time: __info.end));
1039
1040 // Case 2 in __info
1041 if (__info.begin != sys_seconds::min()) {
1042 // Case 2.1 Not at the beginning, when not ambiguous the result should test
1043 // case 2.3.
1044 sys_info __prev = __get_info(time: __info.begin - 1s);
1045 if (__is_ambiguous(__local_time, first: __prev, second: __info))
1046 return {.result: local_info::ambiguous, .first: __prev, .second: __info};
1047 }
1048
1049 if (__info.end == sys_seconds::max())
1050 // At the end so it's case 2.2
1051 return {.result: local_info::unique, .first: __info, .second: sys_info{}};
1052
1053 // This tests case 2.2 or case 2.3.
1054 return chrono::__get_info(__local_time, first: __info, second: __get_info(time: __info.end));
1055}
1056
1057} // namespace chrono
1058
1059_LIBCPP_END_EXPLICIT_ABI_ANNOTATIONS
1060_LIBCPP_END_NAMESPACE_STD
1061