[PATCH v3 4/5] libstdc++: Cascade wall-time saves in lazy expansion seeding [PR124853]
Jonathan Wakely
jwakely@redhat.com
Mon Jun 29 17:13:55 GMT 2026
On Fri, 26 Jun 2026 at 17:15 +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). The harness reports this as a sustained CEMT stretch where
harness?
>zic and libc agree on CET.
>
>To address above the finding algorithm, is now expanded to collect
>tree rule transitions around specified time t, while continuing to
"three"
>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.
"time"
>
>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 (cascadding 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_paris),
> * 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.
>
>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 optmized, by seraching the rules by name, from, and
"searching"
>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
> seprate functions, and invoke them.
"separate"
> (<unnamed>::find_active_rule): Modify algorithm to
> handle cascading saves.
> (<unnamed>::find_first_std): Simplified implementation
> benfiting from reordering of rules.
"benefiting" (or "benefitting" in British English, but definitely a
second 'e' in both American and British English :-)
> (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>
>---
>v3 takes a different approach for implementing find_active_rule,
>avoiding collecting all rule transitions. Expanded test cases to
>include a synthetic test with cascading negative save.
>
>Testing on x86_64-linux. std/time/time_zone* test passed already.
>OK for trunk when all test passes?
OK for trunk - the code is easier to follow *and* more correct,
thanks!
>Not sure regarding backport now, would preffer to finish the
>remaining patches, and see if there are any new regerssion when
>comparing with zic.
Makes sense - we can decide later.
>
> libstdc++-v3/src/c++20/tzdb.cc | 181 ++++++++++++------
> .../std/time/time_zone/wall_cascade.cc | 115 +++++++++++
> 2 files changed, 239 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..a044620cc8f 100644
>--- a/libstdc++-v3/src/c++20/tzdb.cc
>+++ b/libstdc++-v3/src/c++20/tzdb.cc
>@@ -684,6 +684,119 @@ 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));
>+ // Rule specifying start time as Wall time, should apply
>+ // running save accumulated by eariel rules. To handle
"earlier"
>+ // 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)
>+ {
>+ 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
>+ break; // rules are ordered by from in ascending other
>+
>+ seconds offset{}; // appropriate for at_time::Universal
>+ if (rule.when.indicator == at_time::Wall
>+ || rule.when.indicator == at_time::Standard)
>+ offset = std_offset;
>+
>+ // Time the rule takes effect this year:
>+ const sys_seconds rule_start = rule.start_time(y, offset);
>+
>+ // Times at which rule takes affect before (or equal) t,
>+ // and after t, respectivelly.
"respectively"
>+ sys_seconds start_before, start_after;
>+ if (rule_start <= t)
>+ {
>+ start_before = rule_start;
>+ start_after = rule.start_time(++y, offset);
>+ }
>+ else
>+ {
>+ start_after = rule_start;
>+ start_before = rule.start_time(--y, offset);
>+ }
>+
>+ 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 move what we considered next_tran to time
"moved"
>+ // 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 +985,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;
> }
>
>@@ -1752,7 +1812,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 +2432,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..1b937c6f248
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/std/time/time_zone/wall_cascade.cc
>@@ -0,0 +1,115 @@
>+// { 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_paris()
>+{
>+ // 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 );
>+}
>+
>+int
>+main()
>+{
>+ test_paris();
>+ test_negative();
>+}
>--
>2.54.0
>
>
More information about the Libstdc++
mailing list