From patchwork Thu Apr 18 16:32:33 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 88676 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E0F42386F447 for ; Thu, 18 Apr 2024 16:34:08 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org 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 4C2BA384AB76 for ; Thu, 18 Apr 2024 16:33:28 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 4C2BA384AB76 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 4C2BA384AB76 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=1713458013; cv=none; b=aslBNp84vx6Rkr1e7KuiibJ26+xT9gKtib3fv7rzgt2cp7Xa6wM9N+9sONUJg43HGnjDvQezPTw98d/U8Nc6mObpkl6VnnbH1NL6ZDE/4HdhN+J7IQLHF8xeSVfXPpn17+rJ2LXefJB17ifnbMq6ew9lLJESE7Bexug6SLVIAyc= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1713458013; c=relaxed/simple; bh=BRofiBx7v30qXJHRz6Ss1G0SlY1um6y7ZpkXmEyb6rM=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=IdFHJzXsQOectE8yFD8lqWicTqNPoNDJgKcnoXDnrCsi7lHxR4ZdQb/GTHONwpC6j+QBR8RheWjOgEDd2LMstEMAo8U0EeTi0OcofnZ8kv+huHUs1xZfb/aAvbXH/6N0sNZF7nPua3kCTV+GB0YhFMO8NUzQj0oJT/r5XlWHkl0= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1713458008; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=WqSL7LLJX+n1AbY+3edNgtiaXWeeGm1R46vUQELC8yc=; b=VLJKBflNuFn71jPggUUjp40Yp6wi68LyHytLCtohYoeL0ue28u2aQcwUhu+mRJJ7fG685g B83nnohB97VWvjA5HgJn5L1YnjSCrDJy/J75fr9C0LiD4Tnubbis7X97aQpDU7alE3Qvm0 EQFQohxp1lG96HixwHQeH9QFhDQjv58= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-664-gvvBmHCfOq6awzpUe6DzYg-1; Thu, 18 Apr 2024 12:33:22 -0400 X-MC-Unique: gvvBmHCfOq6awzpUe6DzYg-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.rdu2.redhat.com [10.11.54.4]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id C60EF8ABE02; Thu, 18 Apr 2024 16:33:20 +0000 (UTC) Received: from localhost (unknown [10.42.28.238]) by smtp.corp.redhat.com (Postfix) with ESMTP id 80DF520296D2; Thu, 18 Apr 2024 16:33:20 +0000 (UTC) From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH] libstdc++: Support link chains in std::chrono::tzdb::locate_zone [PR114770] Date: Thu, 18 Apr 2024 17:32:33 +0100 Message-ID: <20240418163319.1279591-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.4 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-12.9 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 X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org This would fix the but, how do people feel about it this close to the gcc-14 release? 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 fully 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 to 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 link 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 fail 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/tzdb.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=2 and -fabi-version=18 auto search = [](const Vec& v, string_view name) { @@ -1610,13 +1610,62 @@ namespace std::chrono return ptr; }; + // Search zones first. if (auto tz = search(zones, tz_name)) return tz; + // Search links second. if (auto tz_l = search(links, tz_name)) - return search(zones, tz_l->target()); + { + // Handle the common case of a link that has a zone as the target. + if (auto tz = 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 loops, + // 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 times. + // 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 lookups, + // but that case should never happen with correct tzdata.zi, + // so there's no need to optimize cycle detection. + + const time_zone_link* tortoise = tz_l; + const time_zone_link* hare = search(links, tz_l->target()); + while (hare) + { + // Chains should be short, so first check if it ends here: + if (auto tz = search(zones, hare->target())) [[likely]] + return tz; + + // Otherwise follow the chain: + hare = search(links, hare->target()); + if (!hare) + break; + + // Again, first check if the chain ends at a zone here: + if (auto tz = search(zones, hare->target())) [[likely]] + return tz; + + // Follow the chain again: + hare = search(links, hare->target()); + + if (hare == tortoise) + { + string_view err = "std::chrono::tzdb: link cycle: "; + string str; + str.reserve(err.size() + tz_name.size()); + str += err; + str += tz_name; + __throw_runtime_error(str.c_str()); + } + // Plod along the chain one step: + tortoise = search(links, tortoise->target()); + } + } + + return nullptr; // not found } } // namespace @@ -1626,7 +1675,7 @@ namespace std::chrono { if (auto tz = do_locate_zone(zones, links, tz_name)) return tz; - string_view err = "tzdb: cannot locate zone: "; + string_view err = "std::chrono::tzdb: cannot locate zone: "; string str; str.reserve(err.size() + tz_name.size()); str += 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 = false; + +namespace __gnu_cxx +{ + const char* zoneinfo_dir_override() { + override_used = 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 = reload_tzdb(); + VERIFY( override_used ); // If this fails then XFAIL for the target. + VERIFY( db.version == "test_1" ); + + // Simple case of a link with a zone as its target. + VERIFY( locate_zone("Greenwich")->name() == "Etc/GMT" ); + // Chains of links, where the target may be another link. + VERIFY( locate_zone("G_M_T")->name() == "Etc/GMT" ); + VERIFY( locate_zone("L1")->name() == "A_Zone" ); + VERIFY( locate_zone("L2")->name() == "A_Zone" ); + VERIFY( locate_zone("L3")->name() == "A_Zone" ); + VERIFY( locate_zone("L4")->name() == "A_Zone" ); + VERIFY( locate_zone("L5")->name() == "A_Zone" ); + VERIFY( locate_zone("L6")->name() == "A_Zone" ); + VERIFY( locate_zone("L7")->name() == "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 below. + 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 = reload_tzdb(); + VERIFY( override_used ); // If this fails then XFAIL for the target. + VERIFY( db2.version == "test_2" ); + + // The standard requires locate_zone(name) to search for a zone first, + // so this finds the zone B_Zone, not the link that points to zone A_Zone. + VERIFY( locate_zone("B_Zone")->name() == "B_Zone" ); + // And libstdc++ does the same at every step when following chained links: + VERIFY( locate_zone("C_Link")->name() == "B_Zone" ); + VERIFY( locate_zone("D_Link")->name() == "B_Zone" ); + VERIFY( locate_zone("E_Link")->name() == "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 = reload_tzdb(); + VERIFY( db3.version == "test_3" ); + + // Lookup for valid links should still work even if other links are bad. + VERIFY( locate_zone("GoodLink")->name() == "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(); +}