[PATCH v4 4/5] libstdc++: Cascade wall-time saves in lazy expansion seeding [PR124853]
Jonathan Wakely
jwakely@redhat.com
Wed Jul 1 12:12:35 GMT 2026
On Tue, 30 Jun 2026 at 09:57 +0200, Tomasz Kamiński wrote:
>When _M_get_sys_info seeds a Zone line by looking up the active rule
>just before info.begin, the previous code interpreted each rule in
>isolation against ri.offset() (the line's standard offset alone),
>ignoring the running save accumulated by earlier rules in the same
>year. For most zones this gives the right answer because the search
>only matters when no rule has fired yet, but for zones whose rule
>set has wall-time rules whose effective firing time depends on a
>prior rule's save it produces wrong answers.
>
>Canonical case: Europe/Paris around 1945. France's rules
>
> R Fr 1945 o - Apr 2 2 2 M
> R Fr 1945 o - Sep 16 3 0 -
>
>both use plain wall time. In Paris's stdoff=1 frame, the September
>rule's at_time of 03:00 wall translates to UT Sep 16 02:00 if no
>prior save is applied, but to UT Sep 16 00:00 once the running save
>of 2h from the April rule is taken into account. When seeding a
>sys_info whose info.begin falls between those two values, the simple
>search picks the April rule (save=2 → CEMT, total offset 3h) when
>the correct answer is the September rule (save=0 → CET, total offset
>1h). libstdc++ reports this as a sustained CEMT stretch where zic
>and libc agree on CET.
>
>To address above the finding algorithm, is now expanded to collect
>three rule transitions around specified time t, while continuing to
>ignore the save.
>* curr_tran: transition happening before or at time t,
>* prev_tran: transition preceding above transition,
>* next_tran: transition happening after tiem t.
>
>This collects sufficient information to adjust the start_time (if
>Wall time is used) for curr_tran (save of prev_tran) and next_tran
>(save of curr_tran). Assuming that applying save value does not
>change order of transition (cascading save would be ill-defined
>otherwise), after the adjustment the actual active rule is:
> * next_tran.rule: if the adjustment pushed next_tran.when to
> time before or at t, which happen for positive save (see
> test_positive),
> * prev_tran.rule: if adjustment pushed curr_tran.when to time
> after time t, which happens for negative save (see test_negative),
> * curr_tran.rule.
>
>For the time at the start (Jan/1) or end of the year (December/31),
>for each rule, in addition to transition in year of t, we check
>transitions in previous or next year respectively (years in range
>[first_year, last_year]). This handle rules whose firing (specified
>in local time) crosses a year boundary due to a large stdoff or save.
>One example is Pacific/Auckland's 1946 Jan 1 rule, in stdoff=12h,
>fires at 1945-12-31 11:30 UT, see test_next_year.
>
>The fallback "earliest STD rule" logic is preserved for the case
>where no rule has fired yet, but is extracted to separate function.
>This lookup is optimized, by searching the rules by name, from, and
>save in that order, grouping std rules in given year together.
>
> PR libstdc++/124853
>
>libstdc++-v3/ChangeLog:
>
> * src/c++20/tzdb.cc
> (time_zone::_M_get_sys_info): Extract code blocks to
> separate functions, and invoke them.
> (<unnamed>::find_active_rule): Modify algorithm to
> handle cascading saves.
> (<unnamed>::find_first_std): Simplified implementation
> benefiting from reordering of rules.
> (chrono::reload_tzdb): Sort rules by name, from and save.
> * testsuite/std/time/time_zone/wall_cascade.cc: New test.
>
>Co-authored-by: Álvaro Begué <alvaro.begue@gmail.com>
>Signed-off-by: Tomasz Kamiński <tkaminsk@redhat.com>
>Signed-off-by: Álvaro Begué <alvaro.begue@gmail.com>
>---
>v4 restores the expansion of the year range to previous/next year
>from Álvaro v2 versions. It also adds a test for situations when
>expansion is necessary (based on Pacific/Auckland). This version
>is more targeted, and only expands the range for Dec/31 and Jan/1.
>We do not check local time (t - stdoff) date, as save may still
>move the date to previous/next year.
>
>Futhermore:
>* we record last transition for the rules that no longer applies,
> as one happening before (see test_eariel)
>* fixes typos in commit message and comments pointed out in review
>
>Tested on x86_64-linux. OK for trunk?
OK with some comment tweaks noted below
> libstdc++-v3/src/c++20/tzdb.cc | 209 +++++++++++-----
> .../std/time/time_zone/wall_cascade.cc | 233 ++++++++++++++++++
> 2 files changed, 385 insertions(+), 57 deletions(-)
> create mode 100644 libstdc++-v3/testsuite/std/time/time_zone/wall_cascade.cc
>
>diff --git a/libstdc++-v3/src/c++20/tzdb.cc b/libstdc++-v3/src/c++20/tzdb.cc
>index 5793155b6d8..1d1c5c287e8 100644
>--- a/libstdc++-v3/src/c++20/tzdb.cc
>+++ b/libstdc++-v3/src/c++20/tzdb.cc
>@@ -684,6 +684,146 @@ namespace std::chrono
> }
> #endif
> };
>+
>+ const Rule*
>+ find_active_rule(span<const Rule> rules, sys_seconds t, seconds std_offset)
>+ {
>+ struct Transition {
>+ const Rule* rule;
>+ sys_seconds when;
>+ };
>+
>+ const year_month_day date(chrono::floor<days>(t));
>+ // Expand the search window for the time near end of
Let's change this to
"... for a time near the end of the year which can be pushed ..."
>+ // the year that can be pushed to next/previous year
>+ // by offset. This assumes that total offset is never
I think these comments in this new function would be more clear if the
fields like 'offset' and 'from' were quoted (like I just did).
>+ // greater than 24h.
>+ year first_year = date.year(), last_year = date.year();
>+ if (std_offset.count() > 0)
>+ if (date.month() == December && date.day() == day(31))
>+ ++last_year;
>+ if (std_offset.count() < 0)
>+ if (date.month() == January && date.day() == day(1))
>+ --first_year;
>+
>+ // Rule specifying start time as Wall time, should apply
>+ // running save accumulated by earlier rules. To handle
Quotes around 'save'
>+ // that we firstly collect transitions surrounding specified
>+ // time t, ignoring the save:
>+ // * curr_tran - rule active directly before or at t,
>+ // * prev_tran - rule transition before curr_tran
>+ // * next_tran - rule transition directly after t
>+ Transition prev_tran{nullptr, sys_seconds::min()};
>+ Transition curr_tran{nullptr, sys_seconds::min()};
>+ Transition next_tran{nullptr, sys_seconds::max()};
>+ for (const auto& rule : rules)
>+ {
>+ if (last_year < rule.from) // Rule doesn't apply yet at time t.
>+ break; // Rules are ordered by from in ascending order.
Quotes around 'from'
>+
>+ seconds offset{}; // appropriate for at_time::Universal
>+ if (rule.when.indicator == at_time::Wall
>+ || rule.when.indicator == at_time::Standard)
>+ offset = std_offset;
>+
>+ // Times at which rule takes affect before (or equal) t,
>+ // and after t, respectively.
>+ sys_seconds start_before = sys_seconds::min();
>+ sys_seconds start_after = sys_seconds::max();
>+ auto for_year = [&](year y)
>+ {
>+ // Time the rule takes effect on year y:
>+ const sys_seconds rule_start = rule.start_time(y, offset);
>+ if (rule_start <= t)
>+ {
>+ start_before = rule_start;
>+ if (y == last_year && rule.to > y)
>+ start_after = rule.start_time(++y, offset);
>+ }
>+ else
>+ {
>+ start_after = rule_start;
>+ if (y == first_year && rule.from < y)
>+ start_before = rule.start_time(--y, offset);
>+ }
>+ };
>+
>+ if (first_year > rule.to)
>+ // Rule no longer applies at time t, record last transition
>+ start_before = rule.start_time(rule.to, offset);
>+ else if (first_year == last_year)
>+ for_year(first_year);
>+ else
>+ {
>+ // Local time may of t may be in prev/next year.
>+ if (first_year >= rule.from)
>+ for_year(first_year);
>+ if (last_year <= rule.to)
>+ for_year(last_year);
>+ }
>+
>+ if (curr_tran.when < start_before)
>+ {
>+ prev_tran = curr_tran;
>+ curr_tran = {&rule, start_before};
>+ }
>+ else if (prev_tran.when < start_before)
>+ prev_tran = {&rule, start_before};
>+
>+ if (start_after < next_tran.when)
>+ next_tran = {&rule, start_after};
>+ }
>+
>+ // No rule was active at the time of t, running save
>+ // cannot change this output, as we have no save to apply.
>+ if (!curr_tran.rule)
>+ return nullptr;
>+
>+ auto cascade_save = [](const Rule* from, Transition& to)
>+ {
>+ if (!from || from->save == seconds(0))
>+ return false;
>+ if (!to.rule || to.rule->when.indicator != at_time::Wall)
>+ return false;
>+ to.when -= from->save;
>+ return true;
>+ };
>+
>+ if (cascade_save(curr_tran.rule, next_tran))
>+ // Running save moved what we considered next_tran to time
>+ // before or at t, in that case next_tran is active rule.
>+ if (next_tran.when <= t)
>+ return next_tran.rule;
>+
>+ if (cascade_save(prev_tran.rule, curr_tran))
>+ // Running save moved what we consider curr_tran to
>+ // time after t, in that case prev_tran is active rule.
>+ if (curr_tran.when > t)
>+ return prev_tran.rule;
>+
>+ return curr_tran.rule;
>+ }
>+
>+ const Rule*
>+ find_first_std(span<const Rule> rules)
>+ {
>+ auto is_std = [](const Rule& rule) { return !rule.save.count(); };
>+ // Rules with same name are sorted by year and then save in ascending order.
>+ auto it = ranges::find_if(rules, is_std);
>+ if (it == rules.end())
>+ return nullptr;
>+
>+ const Rule* first = &*it;
>+ const year y = first->from;
>+ for (const Rule& next : span<const Rule>(++it, rules.end()))
>+ {
>+ if (!is_std(next) || next.from > y)
>+ break;
>+ if (next.start_time(y, {}) < first->start_time(y, {}))
>+ first = &next;
>+ }
>+ return first;
>+ }
> } // namespace
> #endif // TZDB_DISABLED
>
>@@ -872,70 +1012,17 @@ namespace std::chrono
>
> if (letters.empty())
> {
>- sys_seconds t = info.begin - seconds(1);
>- const year_month_day date(chrono::floor<days>(t));
>-
> // Try to find a Rule active before this time, to get initial
> // SAVE and LETTERS values. There may not be a Rule for the period
> // before the first DST transition, so find the earliest DST->STD
> // transition and use the LETTERS from that.
>- const Rule* active_rule = nullptr;
>- sys_seconds active_rule_start = sys_seconds::min();
>- const Rule* first_std = nullptr;
>- for (const auto& rule : rules)
>- {
>- if (rule.save == minutes(0))
>- {
>- if (!first_std)
>- first_std = &rule;
>- else if (rule.from < first_std->from)
>- first_std = &rule;
>- else if (rule.from == first_std->from)
>- {
>- if (rule.start_time(rule.from, {})
>- < first_std->start_time(first_std->from, {}))
>- first_std = &rule;
>- }
>- }
>-
>- year y = date.year();
>-
>- if (y > rule.to) // rule no longer applies at time t
>- continue;
>- if (y < rule.from) // rule doesn't apply yet at time t
>- continue;
>-
>- sys_seconds rule_start;
>-
>- seconds offset{}; // appropriate for at_time::Universal
>- if (rule.when.indicator == at_time::Wall)
>- offset = info.offset;
>- else if (rule.when.indicator == at_time::Standard)
>- offset = ri.offset();
>-
>- // Time the rule takes effect this year:
>- rule_start = rule.start_time(y, offset);
>-
>- if (rule_start >= t && rule.from < y)
>- {
>- // Try this rule in the previous year.
>- rule_start = rule.start_time(--y, offset);
>- }
>-
>- if (active_rule_start < rule_start && rule_start < t)
>- {
>- active_rule_start = rule_start;
>- active_rule = &rule;
>- }
>- }
>-
>- if (active_rule)
>+ if (const Rule* active_rule = find_active_rule(rules, info.begin - seconds(1), ri.offset()))
> {
> info.offset = ri.offset() + active_rule->save;
> info.save = chrono::duration_cast<minutes>(active_rule->save);
> letters = active_rule->letters;
> }
>- else if (first_std)
>+ else if (const Rule* first_std = find_first_std(rules))
> letters = first_std->letters;
> }
>
>@@ -947,6 +1034,7 @@ namespace std::chrono
> const year_month_day date(chrono::floor<days>(t));
> const Rule* next_rule = nullptr;
>
>+
Unnecessary change?
> // Check every rule to find the next transition after t.
> for (const auto& rule : rules)
> {
>@@ -1752,7 +1840,14 @@ namespace
>
> ranges::sort(node->db.zones, {}, &time_zone::name);
> ranges::sort(node->db.links, {}, &time_zone_link::name);
>- ranges::stable_sort(node->rules, {}, &Rule::name);
>+ ranges::sort(node->rules, [](const Rule& lhs, const Rule& rhs)
>+ {
>+ if (auto result = lhs.name <=> rhs.name; result != 0)
>+ return result < 0;
>+ if (auto result = lhs.from <=> rhs.from; result != 0)
>+ return result < 0;
>+ return lhs.save < rhs.save;
>+ });
>
> return Node::_S_replace_head(std::move(head), std::move(node));
> #else
>@@ -2365,7 +2460,7 @@ namespace
> {
> if (c = in.get(); c == '<' || c == '>')
> if (in.get() == '=')
>- if (unsigned d; (in >> d) && (d <= 31)) [[likely]]
>+ if (unsigned d; (in >> d) && (d <= 31)) [[likely]]
> {
> on.kind = c == '<' ? LessEq : GreaterEq;
> on.day_of_week = w.wd.c_encoding();
>diff --git a/libstdc++-v3/testsuite/std/time/time_zone/wall_cascade.cc b/libstdc++-v3/testsuite/std/time/time_zone/wall_cascade.cc
>new file mode 100644
>index 00000000000..e06673f08ac
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/std/time/time_zone/wall_cascade.cc
>@@ -0,0 +1,233 @@
>+// { dg-do run { target c++20 } }
>+// { dg-require-effective-target tzdb }
>+// { dg-require-effective-target cxx11_abi }
>+// { dg-xfail-run-if "no weak override on AIX" { powerpc-ibm-aix* } }
>+
>+// Wall-time rules in the same rule set whose effective firing time
>+// depends on a prior rule's save (Europe/Paris 1945):
>+// 1945 Apr 2 02:00 wall save=2 M
>+// 1945 Sep 16 03:00 wall save=0 -
>+// In the (stdoff=1, save=2) frame the September rule fires at
>+// Sep 16 00:00 UT, not Sep 16 02:00 UT.
>+
>+#include <chrono>
>+#include <fstream>
>+#include <testsuite_hooks.h>
>+
>+static bool override_used = false;
>+
>+namespace __gnu_cxx
>+{
>+ const char* zoneinfo_dir_override() {
>+ override_used = true;
>+ return "./";
>+ }
>+}
>+
>+using namespace std::chrono;
>+
>+void
>+test_positive()
>+{
>+ // Line 1 ends at "1945 Sep 16 1u" (Universal time, no save shenanigans),
>+ // so info.begin for line 2 is exactly 1945-09-16 01:00 UT.
>+ //
>+ // Two-line zone whose second line begins at 1945 Sep 16 01:00 UT,
>+ // between the cascaded firing time (Sep 16 00:00 UT) and the
>+ // non-cascaded firing time (Sep 16 02:00 UT) of the September rule.
>+ // The seeding must pick the September rule (save=0, CET) at info.begin.
>+ std::ofstream("tzdata.zi") << R"(# version test_wall_cascade
>+R Fr 1945 o - Apr 2 2 2 M
>+R Fr 1945 o - Sep 16 3 0 -
>+Z Test/Paris 0 - X 1945 Sep 16 1u
>+ 1 Fr CE%sT
>+)";
>+
>+ const auto& db = reload_tzdb();
>+ VERIFY( override_used ); // If this fails then XFAIL for the target.
>+ VERIFY( db.version == "test_wall_cascade" );
>+
>+ auto* tz = locate_zone("Test/Paris");
>+
>+ // Line 2 begins at exactly 1945-09-16 01:00 UT. Sample one second
>+ // after the boundary, well inside line 2's first sys_info.
>+ auto info = tz->get_info(sys_seconds{
>+ sys_days(1945y/September/16) + 1h + 1s});
>+ VERIFY( info.offset == 1h );
>+ VERIFY( info.save == 0min );
>+ VERIFY( info.abbrev == "CET" );
>+
>+ // The boundary instant itself is in the new line.
>+ auto at_boundary
>+ = tz->get_info(sys_seconds{sys_days(1945y/September/16) + 1h});
>+ VERIFY( at_boundary.offset == 1h );
>+ VERIFY( at_boundary.save == 0min );
>+
>+ // Sample later still in line 2 (winter): unchanged.
>+ auto winter = tz->get_info(sys_days(1945y/December/1));
>+ VERIFY( winter.offset == 1h );
>+ VERIFY( winter.save == 0min );
>+}
>+
>+void
>+test_negative()
>+{
>+ // This is synthetic version of above example, with negative
>+ // running save.
>+ //
>+ // Two-line zone whose second line begins at 1945 Sep 16 01:00 UT,
>+ // at the cascaded firing time (Sep 16 01:00 UT), but after
>+ // non-cascaded firing time (Sep 16 00:00 UT) of the September rule.
>+ // The seeding must pick the April rule (save=-2, CEST) at info.begin.
>+ std::ofstream("tzdata.zi") << R"(# version test_negative_cascade
>+R Fr 1945 o - Apr 2 2 -2 M
>+R Fr 1945 o - Sep 16 0 0 -
>+Z Test/Negative 0 - X 1945 Sep 16 1u
>+ 1 Fr CE%sT
>+)";
>+
>+ const auto& db = reload_tzdb();
>+ VERIFY( override_used ); // If this fails then XFAIL for the target.
>+ VERIFY( db.version == "test_negative_cascade" );
>+
>+ auto* tz = locate_zone("Test/Negative");
>+
>+ // Line 2 begins at exactly 1945-09-16 01:00 UT, sample
>+ // one second after.
>+ auto info = tz->get_info(sys_seconds{
>+ sys_days(1945y/September/16) + 1h + 1s});
>+ VERIFY( info.offset == -1h );
>+ VERIFY( info.save == -2h );
>+ VERIFY( info.abbrev == "CEMT" );
>+
>+ // The boundary instant.
>+ auto at_boundary
>+ = tz->get_info(sys_seconds{sys_days(1945y/September/16) + 1h});
>+ VERIFY( at_boundary.offset == -1h );
>+ VERIFY( at_boundary.save == -2h );
>+}
>+
>+void
>+test_next_year()
>+{
>+ // The NZ 1946 rule triggers at 1946 Jan 1 00:00:00
>+ // local time, which correspond to 1946 Dec 13 12:00:00 UT.
>+ std::ofstream("tzdata.zi") << R"(# version test_next_year
>+R NZ 1934 1940 - Ap lastSu 2 0 M
>+R NZ 1934 1940 - S lastSu 2 0:30 S
>+R NZ 1946 o - Ja 1 0 0 S
>+Z Pacific/Auckland 11:39:4 - LMT 1868 N 2
>+11:30 NZ NZ%sT 1946
>+12 NZ NZ%sT
>+Z Pacific/AucklandUT 11:39:4 - LMT 1868 N 2
>+11:30 NZ NZ%sT 1945 Dec 31 13u
>+12 NZ NZ%sT
>+)";
>+
>+ const auto& db = reload_tzdb();
>+ VERIFY( override_used ); // If this fails then XFAIL for the target.
>+ VERIFY( db.version == "test_next_year" );
>+
>+ // Pacific/Auckland requires both PR124854 and PR116110 to work
>+ // correctly. TODO test it once implemented.
>+ // The UT version uses 1945-12-31 13:00:00 UT after
>+ // the rule application change.
>+ auto* utz = locate_zone("Pacific/AucklandUT");
>+
>+ // Before the change
>+ auto before_utboundary
>+ = utz->get_info(sys_seconds{sys_days(1945y/December/31) + 11h});
>+ VERIFY( before_utboundary.offset == 12h );
>+ VERIFY( before_utboundary.save == 30min );
>+ VERIFY( before_utboundary.abbrev == "NZST" );
>+
>+ auto at_utboundary
>+ = utz->get_info(sys_seconds{sys_days(1945y/December/31) + 13h});
>+ VERIFY( at_utboundary.offset == 12h );
>+ VERIFY( at_utboundary.save == 0h );
>+ VERIFY( at_utboundary.abbrev == "NZST" );
>+
>+ auto after_utboundary
>+ = utz->get_info(sys_seconds{sys_days(1945y/December/31) + 14h});
>+ VERIFY( after_utboundary.offset == 12h );
>+ VERIFY( after_utboundary.save == 0h );
>+ VERIFY( after_utboundary.abbrev == "NZST" );
>+}
>+
>+void
>+test_prev_year()
>+{
>+ // The syntetic version of above, where the local
>+ // time for rule is moved to previous year.
>+ // The NZ 1946 rule triggers at 1946 Dec 31 22:00:00
>+ // local time, which correspond to 1947 Jan 1 10:00:00 UT.
>+ std::ofstream("tzdata.zi") << R"(# version test_prev_year
>+R PY 1934 1940 - Ap lastSu 2 0 M
>+R PY 1934 1940 - S lastSu 2 0:30 S
>+R PY 1946 o - D 31 22 0 S
>+Z Test/PrevYear -11:39:4 - LMT 1868 N 2
>+-12:30 PY PY%sT 1947 Jan 1 11u
>+-12 PY PY%sT
>+)";
>+
>+ const auto& db = reload_tzdb();
>+ VERIFY( override_used ); // If this fails then XFAIL for the target.
>+ VERIFY( db.version == "test_prev_year" );
>+
>+ // The UT version uses 1945-12-31 13:00:00 UT after
>+ // the rule application change.
>+ auto* tz = locate_zone("Test/PrevYear");
>+
>+ // Before the change
>+ auto before_boundary
>+ = tz->get_info(sys_seconds{sys_days(1947y/January/1) + 9h});
>+ VERIFY( before_boundary.offset == -12h );
>+ VERIFY( before_boundary.save == 30min );
>+ VERIFY( before_boundary.abbrev == "PYST" );
>+
>+ auto at_boundary
>+ = tz->get_info(sys_seconds{sys_days(1947y/January/1) + 11h});
>+ VERIFY( at_boundary.offset == -12h );
>+ VERIFY( at_boundary.save == 0h );
>+ VERIFY( at_boundary.abbrev == "PYST" );
>+
>+ auto after_boundary
>+ = tz->get_info(sys_seconds{sys_days(1947y/January/1) + 12h});
>+ VERIFY( after_boundary.offset == -12h );
>+ VERIFY( after_boundary.save == 0h );
>+ VERIFY( after_boundary.abbrev == "PYST" );
>+}
>+
>+void
>+test_eariel_year()
>+{
>+ // Syntethic example where PY 1941 rule is still running.
>+ std::ofstream("tzdata.zi") << R"(# version test_eariel_year
>+R EY 1934 1941 - Ap lastSu 2 0 M
>+R EY 1934 1940 - S lastSu 2 0:30 S
>+Z Test/EarielYear 11:39:4 - LMT 1868 N 2
>+11:30 EY EY%sT 1943 Jan 1 12u
>+12 EY EY%sT
>+ )";
>+
>+ const auto& db = reload_tzdb();
>+ VERIFY( override_used ); // If this fails then XFAIL for the target.
>+ VERIFY( db.version == "test_eariel_year" );
>+
>+ auto* utz = locate_zone("Test/EarielYear");
>+ auto at_boundary
>+ = utz->get_info(sys_seconds{sys_days(1943y/January/1) + 12h});
>+ VERIFY( at_boundary.offset == 12h );
>+ VERIFY( at_boundary.save == 0min );
>+ VERIFY( at_boundary.abbrev == "EYMT" );
>+}
>+
>+int
>+main()
>+{
>+ test_positive();
>+ test_negative();
>+ test_next_year();
>+ test_prev_year();
>+ test_eariel_year();
>+}
>--
>2.54.0
>
>
More information about the Libstdc++
mailing list