| //===----------------------------------------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| // For information see https://libcxx.llvm.org/DesignDocs/TimeZone.html |
| |
| // TODO TZDB look at optimizations |
| // |
| // The current algorithm is correct but not efficient. For example, in a named |
| // rule based continuation finding the next rule does quite a bit of work, |
| // returns the next rule and "forgets" its state. This could be better. |
| // |
| // It would be possible to cache lookups. If a time for a zone is calculated its |
| // sys_info could be kept and the next lookup could test whether the time is in |
| // a "known" sys_info. The wording in the Standard hints at this slowness by |
| // "suggesting" this could be implemented on the user's side. |
| |
| // TODO TZDB look at removing quirks |
| // |
| // The code has some special rules to adjust the timing at the continuation |
| // switches. This works correctly, but some of the places feel odd. It would be |
| // good to investigate this further and see whether all quirks are needed or |
| // that there are better fixes. |
| // |
| // These quirks often use a 12h interval; this is the scan interval of zdump, |
| // which implies there are no sys_info objects with a duration of less than 12h. |
| |
| #include <algorithm> |
| #include <cctype> |
| #include <chrono> |
| #include <expected> |
| #include <map> |
| #include <numeric> |
| #include <ranges> |
| |
| #include "include/tzdb/time_zone_private.h" |
| #include "include/tzdb/tzdb_list_private.h" |
| |
| // TODO TZDB remove debug printing |
| #ifdef PRINT |
| # include <print> |
| #endif |
| |
| _LIBCPP_BEGIN_NAMESPACE_STD |
| |
| #ifdef PRINT |
| template <> |
| struct formatter<chrono::sys_info, char> { |
| template <class ParseContext> |
| constexpr typename ParseContext::iterator parse(ParseContext& ctx) { |
| return ctx.begin(); |
| } |
| |
| template <class FormatContext> |
| typename FormatContext::iterator format(const chrono::sys_info& info, FormatContext& ctx) const { |
| return std::format_to( |
| ctx.out(), "[{}, {}) {:%Q%q} {:%Q%q} {}", info.begin, info.end, info.offset, info.save, info.abbrev); |
| } |
| }; |
| #endif |
| |
| namespace chrono { |
| |
| //===----------------------------------------------------------------------===// |
| // Details |
| //===----------------------------------------------------------------------===// |
| |
| struct __sys_info { |
| sys_info __info; |
| bool __can_merge; // Can the returned sys_info object be merged with |
| }; |
| |
| // Return type for helper function to get a sys_info. |
| // - The expected result returns the "best" sys_info object. This object can be |
| // before the requested time. Sometimes sys_info objects from different |
| // continuations share their offset, save, and abbrev and these objects are |
| // merged to one sys_info object. The __can_merge flag determines whether the |
| // current result can be merged with the next result. |
| // - The unexpected result means no sys_info object was found and the time is |
| // the time to be used for the next search iteration. |
| using __sys_info_result = expected<__sys_info, sys_seconds>; |
| |
| template <ranges::forward_range _Range, |
| class _Type, |
| class _Proj = identity, |
| indirect_strict_weak_order<const _Type*, projected<ranges::iterator_t<_Range>, _Proj>> _Comp = ranges::less> |
| [[nodiscard]] static ranges::borrowed_iterator_t<_Range> |
| __binary_find(_Range&& __r, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) { |
| auto __end = ranges::end(__r); |
| auto __ret = ranges::lower_bound(ranges::begin(__r), __end, __value, __comp, __proj); |
| if (__ret == __end) |
| return __end; |
| |
| // When the value does not match the predicate it's equal and a valid result |
| // was found. |
| return !std::invoke(__comp, __value, std::invoke(__proj, *__ret)) ? __ret : __end; |
| } |
| |
| // Format based on https://data.iana.org/time-zones/tz-how-to.html |
| // |
| // 1 a time zone abbreviation that is a string of three or more characters that |
| // are either ASCII alphanumerics, "+", or "-" |
| // 2 the string "%z", in which case the "%z" will be replaced by a numeric time |
| // zone abbreviation |
| // 3 a pair of time zone abbreviations separated by a slash ('/'), in which |
| // case the first string is the abbreviation for the standard time name and |
| // the second string is the abbreviation for the daylight saving time name |
| // 4 a string containing "%s", in which case the "%s" will be replaced by the |
| // text in the appropriate Rule's LETTER column, and the resulting string |
| // should be a time zone abbreviation |
| // |
| // Rule 1 is not strictly validated since America/Barbados uses a two letter |
| // abbreviation AT. |
| [[nodiscard]] static string |
| __format(const __tz::__continuation& __continuation, const string& __letters, seconds __save) { |
| bool __shift = false; |
| string __result; |
| for (char __c : __continuation.__format) { |
| if (__shift) { |
| switch (__c) { |
| case 's': |
| std::ranges::copy(__letters, std::back_inserter(__result)); |
| break; |
| |
| case 'z': { |
| if (__continuation.__format.size() != 2) |
| std::__throw_runtime_error( |
| std::format("corrupt tzdb FORMAT field: %z should be the entire contents, instead contains '{}'", |
| __continuation.__format) |
| .c_str()); |
| chrono::hh_mm_ss __offset{__continuation.__stdoff + __save}; |
| if (__offset.is_negative()) { |
| __result += '-'; |
| __offset = chrono::hh_mm_ss{-(__continuation.__stdoff + __save)}; |
| } else |
| __result += '+'; |
| |
| if (__offset.minutes() != 0min) |
| std::format_to(std::back_inserter(__result), "{:%H%M}", __offset); |
| else |
| std::format_to(std::back_inserter(__result), "{:%H}", __offset); |
| } break; |
| |
| default: |
| std::__throw_runtime_error( |
| std::format("corrupt tzdb FORMAT field: invalid sequence '%{}' found, expected %s or %z", __c).c_str()); |
| } |
| __shift = false; |
| |
| } else if (__c == '/') { |
| if (__save != 0s) |
| __result.clear(); |
| else |
| break; |
| |
| } else if (__c == '%') { |
| __shift = true; |
| } else if (__c == '+' || __c == '-' || std::isalnum(__c)) { |
| __result.push_back(__c); |
| } else { |
| std::__throw_runtime_error( |
| std::format( |
| "corrupt tzdb FORMAT field: invalid character '{}' found, expected +, -, or an alphanumeric value", __c) |
| .c_str()); |
| } |
| } |
| |
| if (__shift) |
| std::__throw_runtime_error("corrupt tzdb FORMAT field: input ended with the start of the escape sequence '%'"); |
| |
| if (__result.empty()) |
| std::__throw_runtime_error("corrupt tzdb FORMAT field: result is empty"); |
| |
| return __result; |
| } |
| |
| [[nodiscard]] static sys_seconds __to_sys_seconds(year_month_day __ymd, seconds __seconds) { |
| seconds __result = static_cast<sys_days>(__ymd).time_since_epoch() + __seconds; |
| return sys_seconds{__result}; |
| } |
| |
| [[nodiscard]] static seconds __at_to_sys_seconds(const __tz::__continuation& __continuation) { |
| switch (__continuation.__at.__clock) { |
| case __tz::__clock::__local: |
| return __continuation.__at.__time - __continuation.__stdoff - |
| std::visit( |
| [](const auto& __value) { |
| using _Tp = decay_t<decltype(__value)>; |
| if constexpr (same_as<_Tp, monostate>) |
| return chrono::seconds{0}; |
| else if constexpr (same_as<_Tp, __tz::__save>) |
| return chrono::duration_cast<seconds>(__value.__time); |
| else if constexpr (same_as<_Tp, std::string>) |
| // For a named rule based continuation the SAVE depends on the RULE |
| // active at the end. This should be determined separately. |
| return chrono::seconds{0}; |
| else |
| static_assert(sizeof(_Tp) == 0); // TODO TZDB static_assert(false); after droping clang-16 support |
| |
| std::__libcpp_unreachable(); |
| }, |
| __continuation.__rules); |
| |
| case __tz::__clock::__universal: |
| return __continuation.__at.__time; |
| |
| case __tz::__clock::__standard: |
| return __continuation.__at.__time - __continuation.__stdoff; |
| } |
| std::__libcpp_unreachable(); |
| } |
| |
| [[nodiscard]] static year_month_day __to_year_month_day(year __year, month __month, __tz::__on __on) { |
| return std::visit( |
| [&](const auto& __value) { |
| using _Tp = decay_t<decltype(__value)>; |
| if constexpr (same_as<_Tp, chrono::day>) |
| return year_month_day{__year, __month, __value}; |
| else if constexpr (same_as<_Tp, weekday_last>) |
| return year_month_day{static_cast<sys_days>(year_month_weekday_last{__year, __month, __value})}; |
| else if constexpr (same_as<_Tp, __tz::__constrained_weekday>) |
| return __value(__year, __month); |
| else |
| static_assert(sizeof(_Tp) == 0); // TODO TZDB static_assert(false); after droping clang-16 support |
| |
| std::__libcpp_unreachable(); |
| }, |
| __on); |
| } |
| |
| [[nodiscard]] static sys_seconds __until_to_sys_seconds(const __tz::__continuation& __continuation) { |
| // Does UNTIL contain the magic value for the last continuation? |
| if (__continuation.__year == chrono::year::min()) |
| return sys_seconds::max(); |
| |
| year_month_day __ymd = chrono::__to_year_month_day(__continuation.__year, __continuation.__in, __continuation.__on); |
| return chrono::__to_sys_seconds(__ymd, chrono::__at_to_sys_seconds(__continuation)); |
| } |
| |
| // Holds the UNTIL time for a continuation with a named rule. |
| // |
| // Unlike continuations with an fixed SAVE named rules have a variable SAVE. |
| // This means when the UNTIL uses the local wall time the actual UNTIL value can |
| // only be determined when the SAVE is known. This class holds that abstraction. |
| class __named_rule_until { |
| public: |
| explicit __named_rule_until(const __tz::__continuation& __continuation) |
| : __until_{chrono::__until_to_sys_seconds(__continuation)}, |
| __needs_adjustment_{ |
| // The last continuation of a ZONE has no UNTIL which basically is |
| // until the end of _local_ time. This value is expressed by |
| // sys_seconds::max(). Subtracting the SAVE leaves large value. |
| // However SAVE can be negative, which would add a value to maximum |
| // leading to undefined behaviour. In practice this often results in |
| // an overflow to a very small value. |
| __until_ != sys_seconds::max() && __continuation.__at.__clock == __tz::__clock::__local} {} |
| |
| // Gives the unadjusted until value, this is useful when the SAVE is not known |
| // at all. |
| sys_seconds __until() const noexcept { return __until_; } |
| |
| bool __needs_adjustment() const noexcept { return __needs_adjustment_; } |
| |
| // Returns the UNTIL adjusted for SAVE. |
| sys_seconds operator()(seconds __save) const noexcept { return __until_ - __needs_adjustment_ * __save; } |
| |
| private: |
| sys_seconds __until_; |
| bool __needs_adjustment_; |
| }; |
| |
| [[nodiscard]] static seconds __at_to_seconds(seconds __stdoff, const __tz::__rule& __rule) { |
| switch (__rule.__at.__clock) { |
| case __tz::__clock::__local: |
| // Local time and standard time behave the same. This is not |
| // correct. Local time needs to adjust for the current saved time. |
| // To know the saved time the rules need to be known and sorted. |
| // This needs a time so to avoid the chicken and egg adjust the |
| // saving of the local time later. |
| return __rule.__at.__time - __stdoff; |
| |
| case __tz::__clock::__universal: |
| return __rule.__at.__time; |
| |
| case __tz::__clock::__standard: |
| return __rule.__at.__time - __stdoff; |
| } |
| std::__libcpp_unreachable(); |
| } |
| |
| [[nodiscard]] static sys_seconds __from_to_sys_seconds(seconds __stdoff, const __tz::__rule& __rule, year __year) { |
| year_month_day __ymd = chrono::__to_year_month_day(__year, __rule.__in, __rule.__on); |
| |
| seconds __at = chrono::__at_to_seconds(__stdoff, __rule); |
| return chrono::__to_sys_seconds(__ymd, __at); |
| } |
| |
| [[nodiscard]] static sys_seconds __from_to_sys_seconds(seconds __stdoff, const __tz::__rule& __rule) { |
| return chrono::__from_to_sys_seconds(__stdoff, __rule, __rule.__from); |
| } |
| |
| [[nodiscard]] static const vector<__tz::__rule>& |
| __get_rules(const __tz::__rules_storage_type& __rules_db, const string& __rule_name) { |
| auto __result = chrono::__binary_find(__rules_db, __rule_name, {}, [](const auto& __p) { return __p.first; }); |
| if (__result == std::end(__rules_db)) |
| std::__throw_runtime_error(("corrupt tzdb: rule '" + __rule_name + " 'does not exist").c_str()); |
| |
| return __result->second; |
| } |
| |
| // Returns the letters field for a time before the first rule. |
| // |
| // Per https://data.iana.org/time-zones/tz-how-to.html |
| // One wrinkle, not fully explained in zic.8.txt, is what happens when switching |
| // to a named rule. To what values should the SAVE and LETTER data be |
| // initialized? |
| // |
| // 1 If at least one transition has happened, use the SAVE and LETTER data from |
| // the most recent. |
| // 2 If switching to a named rule before any transition has happened, assume |
| // standard time (SAVE zero), and use the LETTER data from the earliest |
| // transition with a SAVE of zero. |
| // |
| // This function implements case 2. |
| [[nodiscard]] static string __letters_before_first_rule(const vector<__tz::__rule>& __rules) { |
| auto __letters = |
| __rules // |
| | views::filter([](const __tz::__rule& __rule) { return __rule.__save.__time == 0s; }) // |
| | views::transform([](const __tz::__rule& __rule) { return __rule.__letters; }) // |
| | views::take(1); |
| |
| if (__letters.empty()) |
| std::__throw_runtime_error("corrupt tzdb: rule has zero entries"); |
| |
| return __letters.front(); |
| } |
| |
| // Determines the information based on the continuation and the rules. |
| // |
| // There are several special cases to take into account |
| // |
| // === Entries before the first rule becomes active === |
| // Asia/Hong_Kong |
| // 9 - JST 1945 N 18 2 // (1) |
| // 8 HK HK%sT // (2) |
| // R HK 1946 o - Ap 21 0 1 S // (3) |
| // There (1) is active until Novemer 18th 1945 at 02:00, after this time |
| // (2) becomes active. The first rule entry for HK (3) becomes active |
| // from April 21st 1945 at 01:00. In the period between (2) is active. |
| // This entry has an offset. |
| // This entry has no save, letters, or dst flag. So in the period |
| // after (1) and until (3) no rule entry is associated with the time. |
| |
| [[nodiscard]] static sys_info __get_sys_info_before_first_rule( |
| sys_seconds __begin, |
| sys_seconds __end, |
| const __tz::__continuation& __continuation, |
| const vector<__tz::__rule>& __rules) { |
| return sys_info{ |
| __begin, |
| __end, |
| __continuation.__stdoff, |
| chrono::minutes(0), |
| chrono::__format(__continuation, __letters_before_first_rule(__rules), 0s)}; |
| } |
| |
| // Returns the sys_info object for a time before the first rule. |
| // When this first rule has a SAVE of 0s the sys_info for the time before the |
| // first rule and for the first rule are identical and will be merged. |
| [[nodiscard]] static sys_info __get_sys_info_before_first_rule( |
| sys_seconds __begin, |
| sys_seconds __rule_end, // The end used when SAVE != 0s |
| sys_seconds __next_end, // The end used when SAVE == 0s the times are merged |
| const __tz::__continuation& __continuation, |
| const vector<__tz::__rule>& __rules, |
| vector<__tz::__rule>::const_iterator __rule) { |
| if (__rule->__save.__time != 0s) |
| return __get_sys_info_before_first_rule(__begin, __rule_end, __continuation, __rules); |
| |
| return sys_info{ |
| __begin, __next_end, __continuation.__stdoff, 0min, chrono::__format(__continuation, __rule->__letters, 0s)}; |
| } |
| |
| [[nodiscard]] static seconds __at_to_seconds(seconds __stdoff, seconds __save, const __tz::__rule& __rule) { |
| switch (__rule.__at.__clock) { |
| case __tz::__clock::__local: |
| return __rule.__at.__time - __stdoff - __save; |
| |
| case __tz::__clock::__universal: |
| return __rule.__at.__time; |
| |
| case __tz::__clock::__standard: |
| return __rule.__at.__time - __stdoff; |
| } |
| std::__libcpp_unreachable(); |
| } |
| |
| [[nodiscard]] static sys_seconds |
| __rule_to_sys_seconds(seconds __stdoff, seconds __save, const __tz::__rule& __rule, year __year) { |
| year_month_day __ymd = chrono::__to_year_month_day(__year, __rule.__in, __rule.__on); |
| |
| seconds __at = chrono::__at_to_seconds(__stdoff, __save, __rule); |
| return chrono::__to_sys_seconds(__ymd, __at); |
| } |
| |
| // Returns the first rule after __time. |
| // Note that a rule can be "active" in multiple years, this may result in an |
| // infinite loop where the same rule is returned every time, use __current to |
| // guard against that. |
| // |
| // When no next rule exists the returned time will be sys_seconds::max(). This |
| // can happen in practice. For example, |
| // |
| // R So 1945 o - May 24 2 2 M |
| // R So 1945 o - S 24 3 1 S |
| // R So 1945 o - N 18 2s 0 - |
| // |
| // Has 3 rules that are all only active in 1945. |
| [[nodiscard]] static pair<sys_seconds, vector<__tz::__rule>::const_iterator> |
| __next_rule(sys_seconds __time, |
| seconds __stdoff, |
| seconds __save, |
| const vector<__tz::__rule>& __rules, |
| vector<__tz::__rule>::const_iterator __current) { |
| year __year = year_month_day{chrono::floor<days>(__time)}.year(); |
| |
| // Note it would probably be better to store the pairs in a vector and then |
| // use min() to get the smallest element |
| map<sys_seconds, vector<__tz::__rule>::const_iterator> __candidates; |
| // Note this evaluates all rules which is a waste of effort; when the entries |
| // are beyond the current year's "next year" (where "next year" is not always |
| // year + 1) the algorithm should end. |
| for (auto __it = __rules.begin(); __it != __rules.end(); ++__it) { |
| for (year __y = __it->__from; __y <= __it->__to; ++__y) { |
| // Adding the current entry for the current year may lead to infinite |
| // loops due to the SAVE adjustment. Skip these entries. |
| if (__y == __year && __it == __current) |
| continue; |
| |
| sys_seconds __t = chrono::__rule_to_sys_seconds(__stdoff, __save, *__it, __y); |
| if (__t <= __time) |
| continue; |
| |
| _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(!__candidates.contains(__t), "duplicated rule"); |
| __candidates[__t] = __it; |
| break; |
| } |
| } |
| |
| if (!__candidates.empty()) [[likely]] { |
| auto __it = __candidates.begin(); |
| |
| // When no rule is selected the time before the first rule and the first rule |
| // should not be merged. |
| if (__time == sys_seconds::min()) |
| return *__it; |
| |
| // There can be two constitutive rules that are the same. For example, |
| // Hong Kong |
| // |
| // R HK 1973 o - D 30 3:30 1 S (R1) |
| // R HK 1965 1976 - Ap Su>=16 3:30 1 S (R2) |
| // |
| // 1973-12-29 19:30:00 R1 becomes active. |
| // 1974-04-20 18:30:00 R2 becomes active. |
| // Both rules have a SAVE of 1 hour and LETTERS are S for both of them. |
| while (__it != __candidates.end()) { |
| if (__current->__save.__time != __it->second->__save.__time || __current->__letters != __it->second->__letters) |
| return *__it; |
| |
| ++__it; |
| } |
| } |
| |
| return {sys_seconds::max(), __rules.end()}; |
| } |
| |
| // Returns the first rule of a set of rules. |
| // This is not always the first of the listed rules. For example |
| // R Sa 2008 2009 - Mar Su>=8 0 0 - |
| // R Sa 2007 2008 - O Su>=8 0 1 - |
| // The transition in October 2007 happens before the transition in March 2008. |
| [[nodiscard]] static vector<__tz::__rule>::const_iterator |
| __first_rule(seconds __stdoff, const vector<__tz::__rule>& __rules) { |
| return chrono::__next_rule(sys_seconds::min(), __stdoff, 0s, __rules, __rules.end()).second; |
| } |
| |
| [[nodiscard]] static __sys_info_result __get_sys_info_rule( |
| sys_seconds __time, |
| sys_seconds __continuation_begin, |
| const __tz::__continuation& __continuation, |
| const vector<__tz::__rule>& __rules) { |
| auto __rule = chrono::__first_rule(__continuation.__stdoff, __rules); |
| _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(__rule != __rules.end(), "the set of rules has no first rule"); |
| |
| // Avoid selecting a time before the start of the continuation |
| __time = std::max(__time, __continuation_begin); |
| |
| sys_seconds __rule_begin = chrono::__from_to_sys_seconds(__continuation.__stdoff, *__rule); |
| |
| // The time sought is very likely inside the current rule. |
| // When the continuation's UNTIL uses the local clock there are edge cases |
| // where this is not true. |
| // |
| // Start to walk the rules to find the proper one. |
| // |
| // For now we just walk all the rules TODO TZDB investigate whether a smarter |
| // algorithm would work. |
| auto __next = chrono::__next_rule(__rule_begin, __continuation.__stdoff, __rule->__save.__time, __rules, __rule); |
| |
| // Ignore small steps, this happens with America/Punta_Arenas for the |
| // transition |
| // -4:42:46 - SMT 1927 S |
| // -5 x -05/-04 1932 S |
| // ... |
| // |
| // R x 1927 1931 - S 1 0 1 - |
| // R x 1928 1932 - Ap 1 0 0 - |
| // |
| // America/Punta_Arenas Thu Sep 1 04:42:45 1927 UT = Thu Sep 1 00:42:45 1927 -04 isdst=1 gmtoff=-14400 |
| // America/Punta_Arenas Sun Apr 1 03:59:59 1928 UT = Sat Mar 31 23:59:59 1928 -04 isdst=1 gmtoff=-14400 |
| // America/Punta_Arenas Sun Apr 1 04:00:00 1928 UT = Sat Mar 31 23:00:00 1928 -05 isdst=0 gmtoff=-18000 |
| // |
| // Without this there will be a transition |
| // [1927-09-01 04:42:45, 1927-09-01 05:00:00) -05:00:00 0min -05 |
| |
| if (sys_seconds __begin = __rule->__save.__time != 0s ? __rule_begin : __next.first; __time < __begin) { |
| if (__continuation_begin == sys_seconds::min() || __begin - __continuation_begin > 12h) |
| return __sys_info{__get_sys_info_before_first_rule( |
| __continuation_begin, __rule_begin, __next.first, __continuation, __rules, __rule), |
| false}; |
| |
| // Europe/Berlin |
| // 1 c CE%sT 1945 May 24 2 (C1) |
| // 1 So CE%sT 1946 (C2) |
| // |
| // R c 1944 1945 - Ap M>=1 2s 1 S (R1) |
| // |
| // R So 1945 o - May 24 2 2 M (R2) |
| // |
| // When C2 becomes active the time would be before the first rule R2, |
| // giving a 1 hour sys_info. |
| seconds __save = __rule->__save.__time; |
| __named_rule_until __continuation_end{__continuation}; |
| sys_seconds __sys_info_end = std::min(__continuation_end(__save), __next.first); |
| |
| return __sys_info{ |
| sys_info{__continuation_begin, |
| __sys_info_end, |
| __continuation.__stdoff + __save, |
| chrono::duration_cast<minutes>(__save), |
| chrono::__format(__continuation, __rule->__letters, __save)}, |
| __sys_info_end == __continuation_end(__save)}; |
| } |
| |
| // See above for America/Asuncion |
| if (__rule->__save.__time == 0s && __time < __next.first) { |
| return __sys_info{ |
| sys_info{__continuation_begin, |
| __next.first, |
| __continuation.__stdoff, |
| 0min, |
| chrono::__format(__continuation, __rule->__letters, 0s)}, |
| false}; |
| } |
| |
| if (__rule->__save.__time != 0s) { |
| // another fix for America/Punta_Arenas when not at the start of the |
| // sys_info object. |
| seconds __save = __rule->__save.__time; |
| if (__continuation_begin >= __rule_begin - __save && __time < __next.first) { |
| return __sys_info{ |
| sys_info{__continuation_begin, |
| __next.first, |
| __continuation.__stdoff + __save, |
| chrono::duration_cast<minutes>(__save), |
| chrono::__format(__continuation, __rule->__letters, __save)}, |
| false}; |
| } |
| } |
| |
| __named_rule_until __continuation_end{__continuation}; |
| while (__next.second != __rules.end()) { |
| #ifdef PRINT |
| std::print( |
| stderr, |
| "Rule for {}: [{}, {}) off={} save={} duration={}\n", |
| __time, |
| __rule_begin, |
| __next.first, |
| __continuation.__stdoff, |
| __rule->__save.__time, |
| __next.first - __rule_begin); |
| #endif |
| |
| sys_seconds __end = __continuation_end(__rule->__save.__time); |
| |
| sys_seconds __sys_info_begin = std::max(__continuation_begin, __rule_begin); |
| sys_seconds __sys_info_end = std::min(__end, __next.first); |
| seconds __diff = chrono::abs(__sys_info_end - __sys_info_begin); |
| |
| if (__diff < 12h) { |
| // Z America/Argentina/Buenos_Aires -3:53:48 - LMT 1894 O 31 |
| // -4:16:48 - CMT 1920 May |
| // -4 - -04 1930 D |
| // -4 A -04/-03 1969 O 5 |
| // -3 A -03/-02 1999 O 3 |
| // -4 A -04/-03 2000 Mar 3 |
| // ... |
| // |
| // ... |
| // R A 1989 1992 - O Su>=15 0 1 - |
| // R A 1999 o - O Su>=1 0 1 - |
| // R A 2000 o - Mar 3 0 0 - |
| // R A 2007 o - D 30 0 1 - |
| // ... |
| |
| // The 1999 switch uses the same rule, but with a different stdoff. |
| // R A 1999 o - O Su>=1 0 1 - |
| // stdoff -3 -> 1999-10-03 03:00:00 |
| // stdoff -4 -> 1999-10-03 04:00:00 |
| // This generates an invalid entry and this is evaluated as a transition. |
| // Looking at the zdump like output in libc++ this generates jumps in |
| // the UTC time. |
| |
| __rule = __next.second; |
| __next = __next_rule(__next.first, __continuation.__stdoff, __rule->__save.__time, __rules, __rule); |
| __end = __continuation_end(__rule->__save.__time); |
| __sys_info_end = std::min(__end, __next.first); |
| } |
| |
| if ((__time >= __rule_begin && __time < __next.first) || __next.first >= __end) { |
| __sys_info_begin = std::max(__continuation_begin, __rule_begin); |
| __sys_info_end = std::min(__end, __next.first); |
| |
| return __sys_info{ |
| sys_info{__sys_info_begin, |
| __sys_info_end, |
| __continuation.__stdoff + __rule->__save.__time, |
| chrono::duration_cast<minutes>(__rule->__save.__time), |
| chrono::__format(__continuation, __rule->__letters, __rule->__save.__time)}, |
| __sys_info_end == __end}; |
| } |
| |
| __rule_begin = __next.first; |
| __rule = __next.second; |
| __next = __next_rule(__rule_begin, __continuation.__stdoff, __rule->__save.__time, __rules, __rule); |
| } |
| |
| return __sys_info{ |
| sys_info{std::max(__continuation_begin, __rule_begin), |
| __continuation_end(__rule->__save.__time), |
| __continuation.__stdoff + __rule->__save.__time, |
| chrono::duration_cast<minutes>(__rule->__save.__time), |
| chrono::__format(__continuation, __rule->__letters, __rule->__save.__time)}, |
| true}; |
| } |
| |
| [[nodiscard]] static __sys_info_result __get_sys_info_basic( |
| sys_seconds __time, sys_seconds __continuation_begin, const __tz::__continuation& __continuation, seconds __save) { |
| sys_seconds __continuation_end = chrono::__until_to_sys_seconds(__continuation); |
| return __sys_info{ |
| sys_info{__continuation_begin, |
| __continuation_end, |
| __continuation.__stdoff + __save, |
| chrono::duration_cast<minutes>(__save), |
| __continuation.__format}, |
| true}; |
| } |
| |
| [[nodiscard]] static __sys_info_result |
| __get_sys_info(sys_seconds __time, |
| sys_seconds __continuation_begin, |
| const __tz::__continuation& __continuation, |
| const __tz::__rules_storage_type& __rules_db) { |
| return std::visit( |
| [&](const auto& __value) { |
| using _Tp = decay_t<decltype(__value)>; |
| if constexpr (same_as<_Tp, std::string>) |
| return chrono::__get_sys_info_rule( |
| __time, __continuation_begin, __continuation, __get_rules(__rules_db, __value)); |
| else if constexpr (same_as<_Tp, monostate>) |
| return chrono::__get_sys_info_basic(__time, __continuation_begin, __continuation, chrono::seconds(0)); |
| else if constexpr (same_as<_Tp, __tz::__save>) |
| return chrono::__get_sys_info_basic(__time, __continuation_begin, __continuation, __value.__time); |
| else |
| static_assert(sizeof(_Tp) == 0); // TODO TZDB static_assert(false); after droping clang-16 support |
| |
| std::__libcpp_unreachable(); |
| }, |
| __continuation.__rules); |
| } |
| |
| // The transition from one continuation to the next continuation may result in |
| // two constitutive continuations with the same "offset" information. |
| // [time.zone.info.sys]/3 |
| // The begin and end data members indicate that, for the associated time_zone |
| // and time_point, the offset and abbrev are in effect in the range |
| // [begin, end). This information can be used to efficiently iterate the |
| // transitions of a time_zone. |
| // |
| // Note that this does considers a change in the SAVE field not to be a |
| // different sys_info, zdump does consider this different. |
| // LWG XXXX The sys_info range should be affected by save |
| // matches the behaviour of the Standard and zdump. |
| // |
| // Iff the "offsets" are the same '__current.__end' is replaced with |
| // '__next.__end', which effectively merges the two objects in one object. The |
| // function returns true if a merge occurred. |
| [[nodiscard]] bool __merge_continuation(sys_info& __current, const sys_info& __next) { |
| if (__current.end != __next.begin) |
| return false; |
| |
| if (__current.offset != __next.offset || __current.abbrev != __next.abbrev || __current.save != __next.save) |
| return false; |
| |
| __current.end = __next.end; |
| return true; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Public API |
| //===----------------------------------------------------------------------===// |
| |
| [[nodiscard]] _LIBCPP_EXPORTED_FROM_ABI time_zone time_zone::__create(unique_ptr<time_zone::__impl>&& __p) { |
| _LIBCPP_ASSERT_NON_NULL(__p != nullptr, "initialized time_zone without a valid pimpl object"); |
| time_zone result; |
| result.__impl_ = std::move(__p); |
| return result; |
| } |
| |
| _LIBCPP_EXPORTED_FROM_ABI time_zone::~time_zone() = default; |
| |
| [[nodiscard]] _LIBCPP_EXPORTED_FROM_ABI string_view time_zone::__name() const noexcept { return __impl_->__name(); } |
| |
| [[nodiscard]] _LIBCPP_AVAILABILITY_TZDB _LIBCPP_EXPORTED_FROM_ABI sys_info |
| time_zone::__get_info(sys_seconds __time) const { |
| optional<sys_info> __result; |
| bool __valid_result = false; // true iff __result.has_value() is true and |
| // __result.begin <= __time < __result.end is true. |
| bool __can_merge = false; |
| sys_seconds __continuation_begin = sys_seconds::min(); |
| // Iterates over the Zone entry and its continuations. Internally the Zone |
| // entry is split in a Zone information and the first continuation. The last |
| // continuation has no UNTIL field. This means the loop should always find a |
| // continuation. |
| // |
| // For more information on background of zone information please consult the |
| // following information |
| // [zic manual](https://www.man7.org/linux/man-pages/man8/zic.8.html) |
| // [tz source info](https://data.iana.org/time-zones/tz-how-to.html) |
| // On POSIX systems the zdump tool can be useful: |
| // zdump -v Asia/Hong_Kong |
| // Gives all transitions in the Hong Kong time zone. |
| // |
| // During iteration the result for the current continuation is returned. If |
| // no continuation is applicable it will return the end time as "error". When |
| // two continuations are contiguous and contain the "same" information these |
| // ranges are merged as one range. |
| // The merging requires keeping any result that occurs before __time, |
| // likewise when a valid result is found the algorithm needs to test the next |
| // continuation to see whether it can be merged. For example, Africa/Ceuta |
| // Continuations |
| // 0 s WE%sT 1929 (C1) |
| // 0 - WET 1967 (C2) |
| // 0 Sp WE%sT 1984 Mar 16 (C3) |
| // |
| // Rules |
| // R s 1926 1929 - O Sa>=1 24s 0 - (R1) |
| // |
| // R Sp 1967 o - Jun 3 12 1 S (R2) |
| // |
| // The rule R1 is the last rule used in C1. The rule R2 is the first rule in |
| // C3. Since R2 is the first rule this means when a continuation uses this |
| // rule its value prior to R2 will be SAVE 0 LETTERS of the first entry with a |
| // SAVE of 0, in this case WET. |
| // This gives the following changes in the information. |
| // 1928-10-07 00:00:00 C1 R1 becomes active: offset 0 save 0 abbrev WET |
| // 1929-01-01 00:00:00 C2 becomes active: offset 0 save 0 abbrev WET |
| // 1967-01-01 00:00:00 C3 becomes active: offset 0 save 0 abbrev WET |
| // 1967-06-03 12:00:00 C3 R2 becomes active: offset 0 save 1 abbrev WEST |
| // |
| // The first 3 entries are contiguous and contain the same information, this |
| // means the period [1928-10-07 00:00:00, 1967-06-03 12:00:00) should be |
| // returned in one sys_info object. |
| |
| const auto& __continuations = __impl_->__continuations(); |
| const __tz::__rules_storage_type& __rules_db = __impl_->__rules_db(); |
| for (auto __it = __continuations.begin(); __it != __continuations.end(); ++__it) { |
| const auto& __continuation = *__it; |
| __sys_info_result __sys_info = chrono::__get_sys_info(__time, __continuation_begin, __continuation, __rules_db); |
| |
| if (__sys_info) { |
| _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN( |
| __sys_info->__info.begin < __sys_info->__info.end, "invalid sys_info range"); |
| |
| // Filters out dummy entries |
| // Z America/Argentina/Buenos_Aires -3:53:48 - LMT 1894 O 31 |
| // ... |
| // -4 A -04/-03 2000 Mar 3 (C1) |
| // -3 A -03/-02 (C2) |
| // |
| // ... |
| // R A 2000 o - Mar 3 0 0 - |
| // R A 2007 o - D 30 0 1 - |
| // ... |
| // |
| // This results in an entry |
| // [2000-03-03 03:00:00, 2000-03-03 04:00:00) -10800s 60min -03 |
| // for [C1 & R1, C1, R2) which due to the end of the continuation is an |
| // one hour "sys_info". Instead the entry should be ignored and replaced |
| // by [C2 & R1, C2 & R2) which is the proper range |
| // "[2000-03-03 03:00:00, 2007-12-30 03:00:00) -02:00:00 60min -02 |
| |
| if (std::holds_alternative<string>(__continuation.__rules) && __sys_info->__can_merge && |
| __sys_info->__info.begin + 12h > __sys_info->__info.end) { |
| __continuation_begin = __sys_info->__info.begin; |
| continue; |
| } |
| |
| if (!__result) { |
| // First entry found, always keep it. |
| __result = __sys_info->__info; |
| |
| __valid_result = __time >= __result->begin && __time < __result->end; |
| __can_merge = __sys_info->__can_merge; |
| } else if (__can_merge && chrono::__merge_continuation(*__result, __sys_info->__info)) { |
| // The results are merged, update the result state. This may |
| // "overwrite" a valid sys_info object with another valid sys_info |
| // object. |
| __valid_result = __time >= __result->begin && __time < __result->end; |
| __can_merge = __sys_info->__can_merge; |
| } else { |
| // Here things get interesting: |
| // For example, America/Argentina/San_Luis |
| // |
| // -3 A -03/-02 2008 Ja 21 (C1) |
| // -4 Sa -04/-03 2009 O 11 (C2) |
| // |
| // R A 2007 o - D 30 0 1 - (R1) |
| // |
| // R Sa 2007 2008 - O Su>=8 0 1 - (R2) |
| // |
| // Based on C1 & R1 the end time of C1 is 2008-01-21 03:00:00 |
| // Based on C2 & R2 the end time of C1 is 2008-01-21 02:00:00 |
| // In this case the earlier time is the real time of the transition. |
| // However the algorithm used gives 2008-01-21 03:00:00. |
| // |
| // So we need to calculate the previous UNTIL in the current context and |
| // see whether it's earlier. |
| |
| // The results could not be merged. |
| // - When we have a valid result that result is the final result. |
| // - Otherwise the result we had is before __time and the result we got |
| // is at a later time (possibly valid). This result is always better |
| // than the previous result. |
| if (__valid_result) { |
| return *__result; |
| } else { |
| _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN( |
| __it != __continuations.begin(), "the first rule should always seed the result"); |
| const auto& __last = *(__it - 1); |
| if (std::holds_alternative<string>(__last.__rules)) { |
| // Europe/Berlin |
| // 1 c CE%sT 1945 May 24 2 (C1) |
| // 1 So CE%sT 1946 (C2) |
| // |
| // R c 1944 1945 - Ap M>=1 2s 1 S (R1) |
| // |
| // R So 1945 o - May 24 2 2 M (R2) |
| // |
| // When C2 becomes active the time would be before the first rule R2, |
| // giving a 1 hour sys_info. This is not valid and the results need |
| // merging. |
| |
| if (__result->end != __sys_info->__info.begin) { |
| // When the UTC gap between the rules is due to the change of |
| // offsets adjust the new time to remove the gap. |
| sys_seconds __end = __result->end - __result->offset; |
| sys_seconds __begin = __sys_info->__info.begin - __sys_info->__info.offset; |
| if (__end == __begin) { |
| __sys_info->__info.begin = __result->end; |
| } |
| } |
| } |
| |
| __result = __sys_info->__info; |
| __valid_result = __time >= __result->begin && __time < __result->end; |
| __can_merge = __sys_info->__can_merge; |
| } |
| } |
| __continuation_begin = __result->end; |
| } else { |
| __continuation_begin = __sys_info.error(); |
| } |
| } |
| if (__valid_result) |
| return *__result; |
| |
| std::__throw_runtime_error("tzdb: corrupt db"); |
| } |
| |
| // Is the "__local_time" present in "__first" and "__second". If so the |
| // local_info has an ambiguous result. |
| [[nodiscard]] static bool |
| __is_ambiguous(local_seconds __local_time, const sys_info& __first, const sys_info& __second) { |
| std::chrono::local_seconds __end_first{__first.end.time_since_epoch() + __first.offset}; |
| std::chrono::local_seconds __begin_second{__second.begin.time_since_epoch() + __second.offset}; |
| |
| return __local_time < __end_first && __local_time >= __begin_second; |
| } |
| |
| // Determines the result of the "__local_time". This expects the object |
| // "__first" to be earlier in time than "__second". |
| [[nodiscard]] static local_info |
| __get_info(local_seconds __local_time, const sys_info& __first, const sys_info& __second) { |
| std::chrono::local_seconds __end_first{__first.end.time_since_epoch() + __first.offset}; |
| std::chrono::local_seconds __begin_second{__second.begin.time_since_epoch() + __second.offset}; |
| |
| if (__local_time < __end_first) { |
| if (__local_time >= __begin_second) |
| // |--------| |
| // |------| |
| // ^ |
| return {local_info::ambiguous, __first, __second}; |
| |
| // |--------| |
| // |------| |
| // ^ |
| return {local_info::unique, __first, sys_info{}}; |
| } |
| |
| if (__local_time < __begin_second) |
| // |--------| |
| // |------| |
| // ^ |
| return {local_info::nonexistent, __first, __second}; |
| |
| // |--------| |
| // |------| |
| // ^ |
| return {local_info::unique, __second, sys_info{}}; |
| } |
| |
| [[nodiscard]] _LIBCPP_AVAILABILITY_TZDB _LIBCPP_EXPORTED_FROM_ABI local_info |
| time_zone::__get_info(local_seconds __local_time) const { |
| seconds __local_seconds = __local_time.time_since_epoch(); |
| |
| /* An example of a typical year with a DST switch displayed in local time. |
| * |
| * At the first of April the time goes forward one hour. This means the |
| * time marked with ~~ is not a valid local time. This is represented by the |
| * nonexistent value in local_info.result. |
| * |
| * At the first of November the time goes backward one hour. This means the |
| * time marked with ^^ happens twice. This is represented by the ambiguous |
| * value in local_info.result. |
| * |
| * 2020.11.01 2021.04.01 2021.11.01 |
| * offset +05 offset +05 offset +05 |
| * save 0s save 1h save 0s |
| * |------------//----------| |
| * |---------//--------------| |
| * |------------- |
| * ~~ ^^ |
| * |
| * These shifts can happen due to changes in the current time zone for a |
| * location. For example, Indian/Kerguelen switched only once. In 1950 from an |
| * offset of 0 hours to an offset of +05 hours. |
| * |
| * During all these shifts the UTC time will not have gaps. |
| */ |
| |
| // The code needs to determine the system time for the local time. There is no |
| // information available. Assume the offset between system time and local time |
| // is 0s. This gives an initial estimate. |
| sys_seconds __guess{__local_seconds}; |
| sys_info __info = __get_info(__guess); |
| |
| // At this point the offset can be used to determine an estimate for the local |
| // time. Before doing that, determine the offset and validate whether the |
| // local time is the range [chrono::local_seconds::min(), |
| // chrono::local_seconds::max()). |
| if (__local_seconds < 0s && __info.offset > 0s) |
| if (__local_seconds - chrono::local_seconds::min().time_since_epoch() < __info.offset) |
| return {-1, __info, {}}; |
| |
| if (__local_seconds > 0s && __info.offset < 0s) |
| if (chrono::local_seconds::max().time_since_epoch() - __local_seconds < -__info.offset) |
| return {-2, __info, {}}; |
| |
| // Based on the information found in the sys_info, the local time can be |
| // converted to a system time. This resulting time can be in the following |
| // locations of the sys_info: |
| // |
| // |---------//--------------| |
| // 1 2.1 2.2 2.3 3 |
| // |
| // 1. The estimate is before the returned sys_info object. |
| // The result is either non-existent or unique in the previous sys_info. |
| // 2. The estimate is in the sys_info object |
| // - If the sys_info begin is not sys_seconds::min(), then it might be at |
| // 2.1 and could be ambiguous with the previous or unique. |
| // - If sys_info end is not sys_seconds::max(), then it might be at 2.3 |
| // and could be ambiguous with the next or unique. |
| // - Else it is at 2.2 and always unique. This case happens when a |
| // time zone has no transitions. For example, UTC or GMT+1. |
| // 3. The estimate is after the returned sys_info object. |
| // The result is either non-existent or unique in the next sys_info. |
| // |
| // There is no specification where the "middle" starts. Similar issues can |
| // happen when sys_info objects are "short", then "unique in the next" could |
| // become "ambiguous in the next and the one following". Theoretically there |
| // is the option of the following time-line |
| // |
| // |------------| |
| // |----| |
| // |-----------------| |
| // |
| // However the local_info object only has 2 sys_info objects, so this option |
| // is not tested. |
| |
| sys_seconds __sys_time{__local_seconds - __info.offset}; |
| if (__sys_time < __info.begin) |
| // Case 1 before __info |
| return chrono::__get_info(__local_time, __get_info(__info.begin - 1s), __info); |
| |
| if (__sys_time >= __info.end) |
| // Case 3 after __info |
| return chrono::__get_info(__local_time, __info, __get_info(__info.end)); |
| |
| // Case 2 in __info |
| if (__info.begin != sys_seconds::min()) { |
| // Case 2.1 Not at the beginning, when not ambiguous the result should test |
| // case 2.3. |
| sys_info __prev = __get_info(__info.begin - 1s); |
| if (__is_ambiguous(__local_time, __prev, __info)) |
| return {local_info::ambiguous, __prev, __info}; |
| } |
| |
| if (__info.end == sys_seconds::max()) |
| // At the end so it's case 2.2 |
| return {local_info::unique, __info, sys_info{}}; |
| |
| // This tests case 2.2 or case 2.3. |
| return chrono::__get_info(__local_time, __info, __get_info(__info.end)); |
| } |
| |
| } // namespace chrono |
| |
| _LIBCPP_END_NAMESPACE_STD |
