[PATCH v2 4/5] libstdc++: Cascade wall-time saves in lazy expansion seeding [PR124853]
Tomasz Kaminski
tkaminsk@redhat.com
Fri May 15 10:55:37 GMT 2026
On Tue, May 12, 2026 at 11:00 AM Tomasz Kaminski <tkaminsk@redhat.com>
wrote:
>
>
> 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 possible I would like this patch to be the first in the new series
(patch 1/2
are already merged). It is much simpler, and seems independent.
>
> + {
>> + 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/20260515/ab7f970a/attachment-0001.htm>
More information about the Libstdc++
mailing list