From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id CF35D3849ACF for ; Fri, 19 Apr 2024 09:08:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org CF35D3849ACF Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org CF35D3849ACF Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1713517702; cv=none; b=K6nIQBuZLGxUt0trV0+821sciobGUgCyofFsX2X8TPBz1Gqj6XGmkRz1GBrS2n+jikSqxyd54aHx37vwo83NA4Rww5vYkMY2uQQ3PZDaE6YHf/cUlKcbcxoijPJay16LFWX3Z5SHdc7sPzTiR68Nr+pF5/UnJVQhAL+zuXIUCPQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1713517702; c=relaxed/simple; bh=WSGWqtwOflhyZEqlH94x3bFBlCMCcsDI5WJamZuPNQs=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=S5Sr5Wvnp/vpVOBbhfY+X6URxGAvi0hXA/GoN1npM+ell9ZyWENQDsc96Z4Geozx1L8Hk/F3ZAtkIZjA9botBhKOGJtAC/MXrcci5vE1k7AtBUHnb+1wwl7gzoXyuE7B03hBnjJp1jwlxwa8I42OE+lVGaUHAY3bd29FV7QIDuQ= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1713517699; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=F8/WyL4rTYk6g50BAuwO1HXMxW8N7J75Ta/q8O2I2VM=; b=DT8dONkOCpBAEcWTl6vzI5aH4UBuJUAHQp/AgXIAVVF5PHlAZRs1JficnCzCzHyeJmYLj+ 4lXuvk5LTE89eCvodAokuZ+8lzOaxZeuh26pft5lhVTTmYI2n28oR2LfyI3DQYsiKjeh8c O4bMgW95uAEwvC/cH7Qt9F1BcTeIMbw= Received: from mail-yb1-f200.google.com (mail-yb1-f200.google.com [209.85.219.200]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-232-mPPOf2zOPRGzRQBCEBnyHQ-1; Fri, 19 Apr 2024 05:08:18 -0400 X-MC-Unique: mPPOf2zOPRGzRQBCEBnyHQ-1 Received: by mail-yb1-f200.google.com with SMTP id 3f1490d57ef6-dc693399655so3729882276.1 for ; Fri, 19 Apr 2024 02:08:18 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1713517697; x=1714122497; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=F8/WyL4rTYk6g50BAuwO1HXMxW8N7J75Ta/q8O2I2VM=; b=ZQOHZ5QeXmBKQKie8MJbXuxqrsyqNFE4xqNVRFHP3Md0sKUSPcX+9MPDu/eR/RbMZh mTUBQ3MUvAaaw/h4Eft78fxpY2dp5ZlMiffCL1LASLzEnCh4C4TbfA0zlXN1o+DOe827 nl+8B09V9Awz5kpvjBUukH8SreabH8zsCZ7E16fqFkpck3pNMRRnaQah8IW6HhMT8O9t jZysL0lFfUpriH8n99q+LpA4aItLKP/fm22WEQK1+uNd1Z6Y4y6xNWkCEOYv/Nw1+tp4 E3ks/aT3LPeNO4bV1SeLs4ciyXU1v0SVYUcHmmE86yXEwNL4db0DxyCCwCcVW5PAayI1 qFSw== X-Gm-Message-State: AOJu0YzoU1UDsRfYPrUuBssXMwRFH7mVOl0+KhPyEoFzc5YjRJOOKL4B 7mdNcfrro+oZKn40Bry1RPrMcyPd08tVLYBlh25ZiJxl7su+z4ZRys4bFI68K6zy8LVYodYe2LJ JY6v8IvLnIjYOJ7jHPmlG+BL3eSzjhHbcyaxlmDF/aP6zHf4WXnO/atZKjxaqq/ElN8soP+dCH+ ynNzre+hdyt9ktTqHA0IuVI04klWc= X-Received: by 2002:a25:aca8:0:b0:de4:5d8d:859f with SMTP id x40-20020a25aca8000000b00de45d8d859fmr1187688ybi.56.1713517697386; Fri, 19 Apr 2024 02:08:17 -0700 (PDT) X-Google-Smtp-Source: AGHT+IGsvKAnw8y/uTdrjxZAw7iO/qSDuBtScHpWX0raRYN+Gt/IsVf8jp0L+rluqwfSNwaGSFfrlNJtmyrwmLVZ8Ps= X-Received: by 2002:a25:aca8:0:b0:de4:5d8d:859f with SMTP id x40-20020a25aca8000000b00de45d8d859fmr1187666ybi.56.1713517696901; Fri, 19 Apr 2024 02:08:16 -0700 (PDT) MIME-Version: 1.0 References: <20240418163319.1279591-1-jwakely@redhat.com> In-Reply-To: From: Jonathan Wakely Date: Fri, 19 Apr 2024 10:08:00 +0100 Message-ID: Subject: Re: [PATCH] libstdc++: Support link chains in std::chrono::tzdb::locate_zone [PR114770] To: Richard Biener Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-15.4 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Fri, 19 Apr 2024 at 07:14, Richard Biener w= rote: > > On Thu, Apr 18, 2024 at 6:34=E2=80=AFPM Jonathan Wakely wrote: > > > > This would fix the but, how do people feel about it this close to the > > gcc-14 release? > > Guess we'll have to fix it anyway, so why not now ... Yeah, I don't think Debian is going to stop using this feature, and it might get used more widely in future (it's currently part of the "vanguard" format for tzdata, but might move to "main" one day and then all distros would have chained links). So it needs to be backported to gcc-13 too. > (what could go wrong..) Well the risk is that my new code doesn't correctly detect cycles, and so could go into an infinite loop when trying to follow chained links. The current code on trunk will just fail to find a time_zone and throw an exception, which is not ideal, but predictable and easily understood. Attempting to handle chained links adds complexity. I think my new code is correct so that it won't get stuck in a loop, and there are tests which should cover it sufficiently. And for correctly tzdata.zi there will never be cycles anyway, so even if I messed the code up, it shouldn't matter unless the application provides a custom tzdata.zi with invalid links. So I guess I'll push it, and backport to gcc-13 soon. > > Richard. > > > Tested x86_64-linux. > > > > -- >8 -- > > > > Since 2022 the TZif format defined in the zic(8) man page has said that > > links can refer to other links, rather than only referring to a zone. > > This isn't supported by the C++20 spec, which assumes that the target() > > for a chrono::time_zone_link always names a chrono::time_zone, not > > another chrono::time_zone_link. > > > > This hasn't been a problem until now, because there are no entries in > > the tzdata file that chain links together. However, Debian Sid has > > changed the target of the Asia/Chungking link from the Asia/Shanghai > > zone to the Asia/Chongqing link, creating a link chain. The libstdc++ > > code is unable to handle this, so chrono::locate_zone("Asia/Chungking") > > will fail with the tzdata.zi file from Debian Sid. > > > > It seems likely that the C++ spec will need a change to allow link > > chains, so that the original structure of the IANA database can be full= y > > represented by chrono::tzdb. The alternative would be for chrono::tzdb > > to flatten all chains when loading the data, so that a link's target is > > always a zone, but this means throwing away information present in the > > tzdata.zi input file. > > > > In anticipation of a change to the spec, this commit adds support for > > chained links to libstdc++. When a name is found to be a link, we try t= o > > find its target in the list of zones as before, but now if the target > > isn't the name of a zone we don't fail. Instead we look for another lin= k > > with that name, and keep doing that until we reach the end of the chain > > of links, and then look up the last target as a zone. > > > > This new logic would get stuck in a loop if the tzdata.zi file is buggy > > and defines a link chain that contains a cycle, e.g. two links that > > refer to each other. To deal with that unlikely case, we use the > > tortoise and hare algorithm to detect cycles in link chains, and throw > > an exception if we detect a cycle. Cycles in links should never happen, > > and it is expected that link chains will be short (if they occur at all= ) > > and so the code is optimized for short chains without cycles. Longer > > chains (four or more links) and cycles will do more work, but won't fai= l > > to resolve a chain or get stuck in a loop. > > > > libstdc++-v3/ChangeLog: > > > > PR libstdc++/114770 > > * src/c++20/tzdb.cc (do_locate_zone): Support links that have > > another link as their target. > > * testsuite/std/time/tzdb/links.cc: New test. > > --- > > libstdc++-v3/src/c++20/tzdb.cc | 57 ++++- > > libstdc++-v3/testsuite/std/time/tzdb/links.cc | 215 ++++++++++++++++++ > > 2 files changed, 268 insertions(+), 4 deletions(-) > > create mode 100644 libstdc++-v3/testsuite/std/time/tzdb/links.cc > > > > diff --git a/libstdc++-v3/src/c++20/tzdb.cc b/libstdc++-v3/src/c++20/tz= db.cc > > index 639d1c440ba..c7c7cc9deee 100644 > > --- a/libstdc++-v3/src/c++20/tzdb.cc > > +++ b/libstdc++-v3/src/c++20/tzdb.cc > > @@ -1599,7 +1599,7 @@ namespace std::chrono > > const time_zone* > > do_locate_zone(const vector& zones, > > const vector& links, > > - string_view tz_name) noexcept > > + string_view tz_name) > > { > > // Lambda mangling changed between -fabi-version=3D2 and -fabi-v= ersion=3D18 > > auto search =3D [](const Vec& v, string_view name) { > > @@ -1610,13 +1610,62 @@ namespace std::chrono > > return ptr; > > }; > > > > + // Search zones first. > > if (auto tz =3D search(zones, tz_name)) > > return tz; > > > > + // Search links second. > > if (auto tz_l =3D search(links, tz_name)) > > - return search(zones, tz_l->target()); > > + { > > + // Handle the common case of a link that has a zone as the ta= rget. > > + if (auto tz =3D search(zones, tz_l->target())) [[likely]] > > + return tz; > > > > - return nullptr; > > + // Either tz_l->target() doesn't exist, or we have a chain of= links. > > + // Use Floyd's cycle-finding algorithm to avoid infinite loop= s, > > + // at the cost of extra lookups. In the common case we expect= a > > + // chain of links to be short so the loop won't run many time= s. > > + // In particular, the duplicate lookups to move the tortoise > > + // never happen unless the chain has four or more links. > > + // When a chain contains a cycle we do multiple duplicate loo= kups, > > + // but that case should never happen with correct tzdata.zi, > > + // so there's no need to optimize cycle detection. > > + > > + const time_zone_link* tortoise =3D tz_l; > > + const time_zone_link* hare =3D search(links, tz_l->target()); > > + while (hare) > > + { > > + // Chains should be short, so first check if it ends here= : > > + if (auto tz =3D search(zones, hare->target())) [[likely]] > > + return tz; > > + > > + // Otherwise follow the chain: > > + hare =3D search(links, hare->target()); > > + if (!hare) > > + break; > > + > > + // Again, first check if the chain ends at a zone here: > > + if (auto tz =3D search(zones, hare->target())) [[likely]] > > + return tz; > > + > > + // Follow the chain again: > > + hare =3D search(links, hare->target()); > > + > > + if (hare =3D=3D tortoise) > > + { > > + string_view err =3D "std::chrono::tzdb: link cycle: "= ; > > + string str; > > + str.reserve(err.size() + tz_name.size()); > > + str +=3D err; > > + str +=3D tz_name; > > + __throw_runtime_error(str.c_str()); > > + } > > + // Plod along the chain one step: > > + tortoise =3D search(links, tortoise->target()); > > + } > > + } > > + > > + return nullptr; // not found > > } > > } // namespace > > > > @@ -1626,7 +1675,7 @@ namespace std::chrono > > { > > if (auto tz =3D do_locate_zone(zones, links, tz_name)) > > return tz; > > - string_view err =3D "tzdb: cannot locate zone: "; > > + string_view err =3D "std::chrono::tzdb: cannot locate zone: "; > > string str; > > str.reserve(err.size() + tz_name.size()); > > str +=3D err; > > diff --git a/libstdc++-v3/testsuite/std/time/tzdb/links.cc b/libstdc++-= v3/testsuite/std/time/tzdb/links.cc > > new file mode 100644 > > index 00000000000..0ba214846c6 > > --- /dev/null > > +++ b/libstdc++-v3/testsuite/std/time/tzdb/links.cc > > @@ -0,0 +1,215 @@ > > +// { 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* } } > > + > > +#include > > +#include > > +#include > > + > > +static bool override_used =3D false; > > + > > +namespace __gnu_cxx > > +{ > > + const char* zoneinfo_dir_override() { > > + override_used =3D true; > > + return "./"; > > + } > > +} > > + > > +using namespace std::chrono; > > + > > +void > > +test_link_chains() > > +{ > > + std::ofstream("tzdata.zi") << R"(# version test_1 > > +Link Greenwich G_M_T > > +Link Etc/GMT Greenwich > > +Zone Etc/GMT 0 - GMT > > +Zone A_Zone 1 - ZON > > +Link A_Zone L1 > > +Link L1 L2 > > +Link L2 L3 > > +Link L3 L4 > > +Link L4 L5 > > +Link L5 L6 > > +Link L3 L7 > > +)"; > > + > > + const auto& db =3D reload_tzdb(); > > + VERIFY( override_used ); // If this fails then XFAIL for the target. > > + VERIFY( db.version =3D=3D "test_1" ); > > + > > + // Simple case of a link with a zone as its target. > > + VERIFY( locate_zone("Greenwich")->name() =3D=3D "Etc/GMT" ); > > + // Chains of links, where the target may be another link. > > + VERIFY( locate_zone("G_M_T")->name() =3D=3D "Etc/GMT" ); > > + VERIFY( locate_zone("L1")->name() =3D=3D "A_Zone" ); > > + VERIFY( locate_zone("L2")->name() =3D=3D "A_Zone" ); > > + VERIFY( locate_zone("L3")->name() =3D=3D "A_Zone" ); > > + VERIFY( locate_zone("L4")->name() =3D=3D "A_Zone" ); > > + VERIFY( locate_zone("L5")->name() =3D=3D "A_Zone" ); > > + VERIFY( locate_zone("L6")->name() =3D=3D "A_Zone" ); > > + VERIFY( locate_zone("L7")->name() =3D=3D "A_Zone" ); > > +} > > + > > +void > > +test_bad_links() > > +{ > > + // The zic(8) man page says > > + // > the behavior is unspecified if multiple zone or link lines > > + // > define the same name" > > + // For libstdc++ the expected behaviour is described and tested belo= w. > > + std::ofstream("tzdata.zi") << R"(# version test_2 > > +Zone A_Zone 1 - ZA > > +Zone B_Zone 2 - ZB > > +Link A_Zone B_Zone > > +Link B_Zone C_Link > > +Link C_Link D_Link > > +Link D_Link E_Link > > +)"; > > + > > + const auto& db2 =3D reload_tzdb(); > > + VERIFY( override_used ); // If this fails then XFAIL for the target. > > + VERIFY( db2.version =3D=3D "test_2" ); > > + > > + // The standard requires locate_zone(name) to search for a zone firs= t, > > + // so this finds the zone B_Zone, not the link that points to zone A= _Zone. > > + VERIFY( locate_zone("B_Zone")->name() =3D=3D "B_Zone" ); > > + // And libstdc++ does the same at every step when following chained = links: > > + VERIFY( locate_zone("C_Link")->name() =3D=3D "B_Zone" ); > > + VERIFY( locate_zone("D_Link")->name() =3D=3D "B_Zone" ); > > + VERIFY( locate_zone("E_Link")->name() =3D=3D "B_Zone" ); > > + > > + // The zic(8) man page says > > + // > the behavior is unspecified if a chain of one or more links > > + // > does not terminate in a Zone name. > > + // For libstdc++ we throw std::runtime_error if locate_zone finds an > > + // unterminated chain, including the case of a chain that includes a= cycle. > > + std::ofstream("tzdata.zi") << R"(# version test_3 > > +Zone A_Zone 1 - ZON > > +Link A_Zone GoodLink > > +Link No_Zone BadLink > > +Link LinkSelf LinkSelf > > +Link LinkSelf Link1 > > +Link Link1 Link2 > > +Link Cycle2_A Cycle2_B > > +Link Cycle2_B Cycle2_A > > +Link Cycle3_A Cycle3_B > > +Link Cycle3_B Cycle3_C > > +Link Cycle3_C Cycle3_A > > +Link Cycle3_C Cycle3_D > > +Link Cycle4_A Cycle4_B > > +Link Cycle4_B Cycle4_C > > +Link Cycle4_C Cycle4_D > > +Link Cycle4_D Cycle4_A > > +)"; > > + > > + const auto& db3 =3D reload_tzdb(); > > + VERIFY( db3.version =3D=3D "test_3" ); > > + > > + // Lookup for valid links should still work even if other links are = bad. > > + VERIFY( locate_zone("GoodLink")->name() =3D=3D "A_Zone" ); > > + > > +#if __cpp_exceptions > > + try { > > + locate_zone("BadLink"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("cannot locate zone: BadLink") ); > > + } > > + > > + // LinkSelf forms a link cycle with itself. > > + try { > > + locate_zone("LinkSelf"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("link cycle: LinkSelf") ); > > + } > > + > > + // Any chain that leads to LinkSelf reaches a cycle. > > + try { > > + locate_zone("Link1"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("link cycle: Link1") ); > > + } > > + > > + try { > > + locate_zone("Link2"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("link cycle: Link2") ); > > + } > > + > > + // Cycle2_A and Cycle2_B form a cycle of length two. > > + try { > > + locate_zone("Cycle2_A"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("link cycle: Cycle2_A") ); > > + } > > + > > + try { > > + locate_zone("Cycle2_B"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("link cycle: Cycle2_B") ); > > + } > > + > > + // Cycle3_A, Cycle3_B and Cycle3_C form a cycle of length three. > > + try { > > + locate_zone("Cycle3_A"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("link cycle: Cycle3_A") ); > > + } > > + > > + try { > > + locate_zone("Cycle3_B"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("link cycle: Cycle3_B") ); > > + } > > + > > + try { > > + locate_zone("Cycle3_C"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("link cycle: Cycle3_C") ); > > + } > > + > > + // Cycle3_D isn't part of the cycle, but it leads to it. > > + try { > > + locate_zone("Cycle3_D"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("link cycle: Cycle3_D") ); > > + } > > + > > + // Cycle4_* links form a cycle of length four. > > + try { > > + locate_zone("Cycle4_A"); > > + VERIFY( false ); > > + } catch (const std::runtime_error& e) { > > + std::string_view what(e.what()); > > + VERIFY( what.ends_with("link cycle: Cycle4_A") ); > > + } > > +#endif > > +} > > + > > +int main() > > +{ > > + test_link_chains(); > > + test_bad_links(); > > +} > > -- > > 2.44.0 > > >