[PATCH v2 4/5] libstdc++: Cascade wall-time saves in lazy expansion seeding [PR124853]
Tomasz Kaminski
tkaminsk@redhat.com
Tue May 12 09:00:11 GMT 2026
On Mon, Apr 27, 2026 at 1:56 AM Álvaro Begué <alvaro.begue@gmail.com> 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
> zic and libc agree on CET.
>
> Replace the per-rule isolated lookup with a chronological cascade
> walker (the same shape as find_pre_until_rule from the previous
> PR 116110 commit, but with a fixed boundary `t = info.begin + 1s`
> instead of iterative-shrink semantics). All (rule, year) pairs are
> collected over [min(rule.from), year(t)+1], sorted by an approximate
> fire time, and walked in order while a running save value is
> maintained. Each Wall-time rule's actual fire time is computed
> relative to the cascaded save state, and rules whose actual fire
> time is < t apply their save and become candidates for the active
> rule. The +1 year extension catches rules whose wall at_time falls
> in early January or late December but whose UT firing crosses a
> year boundary due to a large stdoff or save (Pacific/Auckland's
> 1946 Jan 1 rule, in stdoff=12h, fires at 1945-12-31 11:30 UT).
>
> The fallback "earliest STD rule" logic is preserved for the case
> where no rule has fired yet, but is moved to its own branch for
> clarity.
>
> libstdc++-v3/ChangeLog:
>
> PR libstdc++/124853
> * src/c++20/tzdb.cc (time_zone::_M_get_sys_info):
> Replace the per-rule isolated active-rule search with a
> chronological cascade walker that maintains a running save
> and interprets Wall-time rules' at_time relative to it.
> Extend the calendar window by one year on each side to catch
> rules whose UT firing crosses a year boundary. Move the
> "earliest STD rule" fallback to its own branch.
> * testsuite/std/time/time_zone/wall_cascade.cc: New test.
>
> Signed-off-by: Álvaro Begué <alvaro.begue@gmail.com>
> ---
> libstdc++-v3/src/c++20/tzdb.cc | 142 +++++++++++-------
> .../std/time/time_zone/wall_cascade.cc | 70 +++++++++
> 2 files changed, 158 insertions(+), 54 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 648b9f85a..4de77e6b1 100644
> --- a/libstdc++-v3/src/c++20/tzdb.cc
> +++ b/libstdc++-v3/src/c++20/tzdb.cc
> @@ -695,19 +695,81 @@ namespace std::chrono
> #endif
> };
>
> - // Find the Rule whose save value is in force at the wall-time UNTIL
> - // of a Zone line, given that `wall_minus_stdoff` is the line's UNTIL
> - // with STDOFF subtracted and `stdoff` is the line's standard offset.
> + // Find the Rule whose effect was last in force at time `t`, given
> + // that `stdoff` is the standard offset of the enclosing zone line.
> + // Returns nullptr if no rule fired strictly before t.
> //
> // Walks (rule, year) pairs chronologically, maintaining a running
> // save value used to interpret subsequent Wall-indicator rules.
> - // The boundary `wall_minus_stdoff - running_save` shrinks as save
> - // accumulates, so a rule firing AT the boundary is treated as
> - // belonging to the next zone line.
> //
> // The calendar window extends by one year on each side to catch
> // rules whose wall at_time crosses a year boundary in UT due to a
> // large stdoff or save.
> + template<typename _RuleRange>
> + const Rule*
> + find_active_rule(const _RuleRange& rules, sys_seconds t, seconds
> stdoff)
>
The duplication here is extremely excessive, could you look into merging
these two
functions somehow, if not at least extracting parts of them.
My suggestion would be to accept seconds t, bool is_local. And then if
is_local
is true, compute the boundary value by t - stdoff - running save in the
loop,
and just t otherwise.
+ {
> + if (rules.empty())
> + return nullptr;
> +
> + const year last_year
> + = year_month_day{chrono::floor<days>(t)}.year() + years(1);
> + year first_year = year::max();
> + for (const auto& r : rules)
> + if (r.from < first_year)
> + first_year = r.from;
> + if (first_year > last_year)
> + return nullptr;
> +
> + struct Pending
> + {
> + const Rule* rule;
> + year y;
> + sys_seconds approx_when;
> + };
> + vector<Pending> pending;
> + pending.reserve(64);
> + for (year y = first_year; y <= last_year; ++y)
> + for (const auto& r : rules)
> + {
> + if (y < r.from || y > r.to)
> + continue;
> + seconds approx_off{};
> + if (r.when.indicator == at_time::Wall
> + || r.when.indicator == at_time::Standard)
> + approx_off = stdoff;
> + pending.push_back({&r, y, r.start_time(y, approx_off)});
> + }
> + std::sort(pending.begin(), pending.end(),
> + [](const Pending& a, const Pending& b) {
> + return a.approx_when < b.approx_when;
> + });
> +
> + seconds running_save{};
> + const Rule* last_fired = nullptr;
> + for (const auto& p : pending)
> + {
> + seconds offset{};
> + if (p.rule->when.indicator == at_time::Wall)
> + offset = stdoff + running_save;
> + else if (p.rule->when.indicator == at_time::Standard)
> + offset = stdoff;
> + sys_seconds fire = p.rule->start_time(p.y, offset);
> + if (fire >= t)
> + continue;
> + last_fired = p.rule;
> + running_save = p.rule->save;
> + }
> + return last_fired;
> + }
> +
> + // Find the Rule whose save value is in force at the wall-time UNTIL
> + // of a Zone line, given that `wall_minus_stdoff` is the line's UNTIL
> + // with STDOFF subtracted and `stdoff` is the line's standard offset.
> + //
> + // Like find_active_rule but `wall_minus_stdoff - running_save`
> + // shrinks as save accumulates, so a rule firing AT the boundary is
> + // treated as belonging to the next zone line.
> template<typename _RuleRange>
> const Rule*
> find_pre_until_rule(const _RuleRange& rules,
>
> @@ -960,19 +1022,28 @@ namespace std::chrono
> // info.begin + 1s makes the strict `rule_start < t` search
> // inclusive of a rule that fires at exactly info.begin.
> 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)
> + // SAVE and LETTERS values. See find_active_rule for the search
> + // semantics.
> + const Rule* active_rule = find_active_rule(rules, t, ri.offset());
> +
> + if (active_rule)
>
I would replace that with:
if (const Rule* active_rule = find_active_rule(rules, t, ri.offset()))
> + {
> + info.offset = ri.offset() + active_rule->save;
> + info.save = chrono::duration_cast<minutes>(active_rule->save);
> + letters = active_rule->letters;
> + }
> + else
> {
> - if (rule.save == minutes(0))
> + // No rule applies before info.begin; fall back to the LETTERS
> + // of the earliest STD rule, since the period before the first
> + // DST transition is conventionally standard time.
> + const Rule* first_std = nullptr;
> + for (const auto& rule : rules)
> {
> + if (rule.save != minutes(0))
> + continue;
> if (!first_std)
> first_std = &rule;
> else if (rule.from < first_std->from)
> @@ -984,46 +1055,9 @@ namespace std::chrono
> 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)
> - {
> - info.offset = ri.offset() + active_rule->save;
> - info.save = chrono::duration_cast<minutes>(active_rule->save);
> - letters = active_rule->letters;
> + if (first_std)
> + letters = first_std->letters;
> }
> - else if (first_std)
> - letters = first_std->letters;
> }
>
> const Rule* curr_rule = nullptr;
> 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 000000000..46e4e5346
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/time/time_zone/wall_cascade.cc
> @@ -0,0 +1,70 @@
> +// { 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 "./";
> + }
> +}
> +
> +int
> +main()
> +{
> + using namespace std::chrono;
> +
> + // 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 );
>
Add comment // If this fails then XFAIL for the target. here.
> + 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 );
> +}
> --
> 2.34.1
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260512/938fd29a/attachment-0001.htm>
More information about the Libstdc++
mailing list