From patchwork Wed Jul 8 09:57:24 2026 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Tomasz_Kami=C5=84ski?= X-Patchwork-Id: 138726 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from vm01.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C5CF94BA2E1F for ; Wed, 8 Jul 2026 10:10:18 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org C5CF94BA2E1F Authentication-Results: sourceware.org; dkim=pass (1024-bit key, unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=OpEzR92t 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.129.124]) by sourceware.org (Postfix) with ESMTP id 57A394BA543C for ; Wed, 8 Jul 2026 10:09:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 57A394BA543C Authentication-Results: sourceware.org; dmarc=pass (p=quarantine 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 57A394BA543C Authentication-Results: sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1783505377; cv=none; b=gxypTJY3ghlSawaIgaNEl9LIeW5m79FKpOmWrVk8PSAjlngC6rj/y9JZ8E9qU56O9ZGRF1ZmxRurF59Z4R4OpDjq3TShuEEHvia/zK6sFotdm7FbXDLGjMt6PPRZV10XyZLZr+fVFmNiJLzCC5tfVFTndByldv0WGIfsWBgdtJg= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1783505377; c=relaxed/simple; bh=qWPs+8LFBBMpFSdLoUCfqh2OFdDzbCy231NkRWgD1jk=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=mahzyxxHM3xLUynMdjlXeWUYBVEHxtAJji1AACeO7qlOuDBT5bAE4WK0wPUCwiCl/kGTt0xUU9V7LtBPVz0wFtfZ+XeUWXFHtpYXPXSIyIRjEh/xT34r6+ifovHMXkUsRPpk6RkKOkqXsASyPIbDwfBHi8Mju+Fq9CxNh4fHE18= ARC-Authentication-Results: i=1; sourceware.org; dkim=pass (1024-bit key, unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=OpEzR92t DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 57A394BA543C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1783505377; 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=5faHwB44RpOvZOtA/bbZr1GMC6v+83OhtK5vrMfWpy0=; b=OpEzR92tUNu3Wz6X41Phx3HrZxL93NJgRD0zpMrQ8LvDHizF1BsfrofYNiczP0DXiGSZXS 1GXR5U2l92gVfWoSVrJmtlI1mOUrk481E2FFmDmZ5aLblCSCj3/3JBJaMYEeObCAWQKMUh Ud10PWBi3u2t0Ulor4QgYznhWKgktIw= Received: from mx-prod-mc-08.mail-002.prod.us-west-2.aws.redhat.com (ec2-35-165-154-97.us-west-2.compute.amazonaws.com [35.165.154.97]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-661-1-LKTRWGP7-EZSWM-xwo8A-1; Wed, 08 Jul 2026 06:09:35 -0400 X-MC-Unique: 1-LKTRWGP7-EZSWM-xwo8A-1 X-Mimecast-MFC-AGG-ID: 1-LKTRWGP7-EZSWM-xwo8A_1783505374 Received: from mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com [10.30.177.93]) (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 mx-prod-mc-08.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTPS id A443B1800D92; Wed, 8 Jul 2026 10:09:34 +0000 (UTC) Received: from localhost (unknown [10.44.34.94]) by mx-prod-int-06.mail-002.prod.us-west-2.aws.redhat.com (Postfix) with ESMTP id 0AD031800480; Wed, 8 Jul 2026 10:09:33 +0000 (UTC) From: =?utf-8?q?Tomasz_Kami=C5=84ski?= To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH] libstdc++: Assert that produced layout_stride::mapping is unique. Date: Wed, 8 Jul 2026 11:57:24 +0200 Message-ID: <20260708100932.424948-1-tkaminsk@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.30.177.93 X-Mimecast-Spam-Score: 0 X-Mimecast-MFC-PROC-ID: 6HQ5DnA4fqk_DPRbPTByQZiHb8WrM6N_5IjPSLP3NZw_1783505374 X-Mimecast-Originator: redhat.com content-type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-12.3 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_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_PASS, SPF_NONE, TXREP shortcircuit=no autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on 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 add an assertions checking if the combination of strides and extents passed to layout_stride::mapping is unique. To avoid excessive performance impact, in non-debug mode only checks that are are O(rank) (i.e. similar cost as operator()) are performed. To achieve that, for the ranks greater or equal, we perform two separate checks: * required_span_size() > mdspan::__size(_M_extents) - this is required by not sufficient condition, that is O(rank) and is always performed. * building an permutation using insertion-sort based algorithm, this is O(rank^2) and is performed only in debug modes. The check for non-zero stride values (performed for all non-zero ranks) is done only if the size of the multidimensional index space is not empty. This follows the resolution of LWG4603, and provides consistent behavior for constructing layout_stride mapping from layout_left/right directly or from strides extracted from it. libstdc++-v3/ChangeLog: * include/std/mdspan (layout_stride::mapping::_M_check_unique): Define. (layout_stride::mapping(const extents_type&, span<....>): Add __glibcxx_assert on _M_check_unique. * testsuite/23_containers/mdspan/layouts/stride_neg.cc: Test for the new added assertions. * testsuite/23_containers/mdspan/layouts/stride_unique.cc: Test verifying no assertions for unique subset of above. --- v2 properly detects an stride sequence that is non-unique, but when assigned to different extents will produce unique layout. This is done, by keeping the relation of stride with the corresponding extents, by permuting the indicies (producing P vector from wording). Changed the __popmin to use insertion sort, that should be optimal for resonable ranks (max few dozens) and expanded the test cases. Added separate stride_unique.cc test file, that checks that no-assertions is triggered from them. For other test, it was still passing if the error was emmitted for line without "dg-error" - I assume this is because them being produced from some source line. The test still fails if error is expected, but not produced. Tested on x86_64-linux locally. *mdspan* test passed with all standard modes and _GLIBCXX_DEBUG. OK for trunk? libstdc++-v3/include/std/mdspan | 73 ++++++++++++++++++- .../mdspan/layouts/stride_neg.cc | 72 +++++++++++++++++- .../mdspan/layouts/stride_unique.cc | 42 +++++++++++ 3 files changed, 183 insertions(+), 4 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_unique.cc diff --git a/libstdc++-v3/include/std/mdspan b/libstdc++-v3/include/std/mdspan index 23304e71b9d..02db9f71d55 100644 --- a/libstdc++-v3/include/std/mdspan +++ b/libstdc++-v3/include/std/mdspan @@ -1893,6 +1893,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION for (size_t __i = 0; __i < extents_type::rank(); ++__i) _M_strides[__i] = __mdspan::__index_type_cast(as_const(__strides[__i])); + + __glibcxx_assert(_M_check_unique()); } template @@ -2027,6 +2029,75 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } private: + using _Strides = typename __array_traits::_Type; + + constexpr bool + _M_check_unique() const + { + constexpr size_t __rank = extents_type::rank(); + if constexpr (__rank == 0) + return true; + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 4603. `layout_stride` should accept zero strides for empty `extents` + else if (__mdspan::__empty(_M_extents)) + return true; + else if constexpr (__rank == 1) + return _M_strides[0] > 0; + else if (__mdspan::__contains_zero(_M_strides)) + return false; + else if constexpr (__rank == 2) + return (_M_strides[1] >= _M_strides[0] * _M_extents.extent(0)) + || (_M_strides[0] >= _M_strides[1] * _M_extents.extent(1)); + else + { + // This is necessary, but not sufficient condition for uniquness. + // It requires computation in range of call of operator(), so check + // if first, also in non-debug mode. + if (required_span_size() < __mdspan::__size(_M_extents)) + return false; + + // Checking if pertmuation of strides exists is O(rank^2) so enabled + // only in debug mode. +#ifdef _GLIBCXX_DEBUG + size_t __perm[__rank]; + for (size_t __i = 0; __i < __rank; ++__i) + __perm[__i] = __i; + + auto __popmin = [&](size_t __from) + { + size_t __min = __perm[__rank - 1]; + for (size_t __i = __rank - 1; __i > __from; --__i) + { + const size_t __cur = __perm[__i - 1]; + const auto __res = _M_strides[__cur] <=> _M_strides[__min]; + // Equal strides are allowed only for extent one, so apply it first. + if (__res < 0 || (__res == 0 && _M_extents.extent(__cur) == 1)) + { + __perm[__i] = __min; + __min = __cur; + } + else + __perm[__i] = __cur; + } + __perm[__from] = __min; + return __min; + }; + + // We use eager insertion-sort based algorithm to permute the __perm. + size_t __prev = __popmin(0); + for (size_t __i = 1; __i < __rank; ++__i) + { + const size_t __next = __popmin(__i); + if (_M_strides[__next] < _M_strides[__prev] * _M_extents.extent(__prev)) + return false; + __prev = __next; + } +#endif + return true; + } + } + #if __glibcxx_submdspan template requires (extents_type::rank() == sizeof...(_Slices)) @@ -2047,8 +2118,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } #endif - using _Strides = typename __array_traits::_Type; [[no_unique_address]] extents_type _M_extents; [[no_unique_address]] _Strides _M_strides; }; diff --git a/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc index 153560bc82f..80f8902176c 100644 --- a/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc +++ b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_neg.cc @@ -1,7 +1,5 @@ // { dg-do compile { target c++23 } } #include - -#include "../layout_traits.h" #include constexpr size_t dyn = std::dynamic_extent; @@ -27,5 +25,75 @@ test_stride_negative() } static_assert(test_stride_negative()); // { dg-error "expansion of" } + +using std::array; +template + using mapping = std::layout_stride::mapping>; + +constexpr auto m0 = mapping<0>(array{}, array{}); + +// Zero strides allowed for empty mappings +constexpr auto m00 = mapping<1>(array{0}, array{0}); +constexpr auto m01 = mapping<2>(array{0, 1}, array{3, 0}); +constexpr auto m02 = mapping<2>(array{0, 1}, array{0, 0}); +constexpr auto m03 = mapping<3>(array{0, 1, 2}, array{3, 0, 0}); +constexpr auto m04 = mapping<3>(array{0, 1, 2}, array{3, 3, 0}); +constexpr auto m05 = mapping<4>(array{0, 1, 2, 3}, array{5, 3, 0, 2}); + +// Otherwise leads to non-unique mappings. +constexpr auto m06 = mapping<1>(array{1}, array{0}); // { dg-error "expansion of" } +constexpr auto m07 = mapping<2>(array{1, 2}, array{3, 0}); // { dg-error "expansion of" } +constexpr auto m08 = mapping<3>(array{1, 2, 3}, array{3, 3, 0}); // { dg-error "expansion of" } +constexpr auto m09 = mapping<4>(array{1, 2, 3, 5}, array{5, 3, 0, 2}); // { dg-error "expansion of" } + +// required_span_size is smaller size of multidimensional index space +constexpr auto m10 = mapping<2>(array{3, 4}, array{2, 3}); // { dg-error "expansion of" } +constexpr auto m11 = mapping<2>(array{3, 4}, array{1, 2}); // { dg-error "expansion of" } +constexpr auto m12 = mapping<3>(array{3, 4, 5}, array{1, 3, 11}); // { dg-error "expansion of" } +constexpr auto m13 = mapping<3>(array{3, 4, 5}, array{1, 2, 12}); // { dg-error "expansion of" } +constexpr auto m14 = mapping<4>(array{3, 4, 5, 6}, array{1, 3, 12, 50}); // { dg-error "expansion of" } +constexpr auto m15 = mapping<4>(array{3, 4, 5, 6}, array{1, 3, 11, 60}); // { dg-error "expansion of" } +constexpr auto m16 = mapping<4>(array{3, 4, 5, 6}, array{1, 2, 12, 60}); // { dg-error "expansion of" } + +// Passes required_span_size check (smaller and bigger stride), detected only in debug mode +constexpr auto m17 = mapping<3>(array{3, 4, 5}, array{1, 2, 25}); // { dg-error "expansion of" "" { target debug_mode } } +constexpr auto m18 = mapping<3>(array{3, 4, 5}, array{1, 5, 12}); // { dg-error "expansion of" "" { target debug_mode } } +constexpr auto m19 = mapping<4>(array{3, 4, 5, 6}, array{1, 2, 12, 100}); // { dg-error "expansion of" "" { target debug_mode } } +constexpr auto m20 = mapping<4>(array{3, 4, 5, 6}, array{1, 5, 12, 60}); // { dg-error "expansion of" "" { target debug_mode } } + +// Equal indicies allowed if extents are 1 +constexpr auto m21 = mapping<2>(array{5, 1}, array{1, 1}); +constexpr auto m22 = mapping<3>(array{1, 5, 1}, array{1, 1, 1}); +constexpr auto m23 = mapping<4>(array{1, 1, 5, 1}, array{1, 1, 1, 1}); +constexpr auto m24 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 3, 3, 45}); +constexpr auto m25 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 3, 10, 45}); +constexpr auto m26 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10, 3, 45}); +constexpr auto m27 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10, 10, 45}); + +// Only some permutations are valid, invalid permutations detected only in debug mode. + +// Unique if stride 3 corresponds to extent 3 +constexpr auto m28 = mapping<2>(array{3, 4}, array{3, 10}); +constexpr auto m29 = mapping<2>(array{3, 4}, array{10, 3}); // { dg-error "expansion of" "" { target debug_mode } } +constexpr auto m30 = mapping<2>(array{4, 3}, array{10, 3}); +constexpr auto m31 = mapping<2>(array{4, 3}, array{3, 10}); // { dg-error "expansion of" "" { target debug_mode } } + +// Unique if stride 11 corresponds to extent 3, as 11 * 3 < 35, and 2 * 5 < 11 +constexpr auto m32 = mapping<3>(array{3, 4, 5}, array{11, 2, 35}); +constexpr auto m33 = mapping<3>(array{3, 4, 5}, array{11, 35, 2}); +constexpr auto m34 = mapping<3>(array{3, 4, 5}, array{2, 11, 35}); // { dg-error "expansion of" "" { target debug_mode } } +constexpr auto m35 = mapping<3>(array{3, 4, 5}, array{35, 2, 11}); // { dg-error "expansion of" "" { target debug_mode } } +constexpr auto m36 = mapping<3>(array{5, 4, 3}, array{2, 35, 11}); +constexpr auto m37 = mapping<3>(array{5, 4, 3}, array{2, 11, 35}); // { dg-error "expansion of" "" { target debug_mode } } +constexpr auto m38 = mapping<3>(array{5, 3, 4}, array{35, 11, 2}); +constexpr auto m39 = mapping<3>(array{3, 5, 4}, array{35, 2, 11}); // { dg-error "expansion of" "" { target debug_mode } } + +// Unique for stride -> extent mapping: 3 * 5 < 16, 15 * 4 < 65, 65 * 3 < 200 +constexpr auto m40 = mapping<4>(array{3, 4, 5, 6}, array{65, 16, 3, 200}); +constexpr auto m41 = mapping<4>(array{3, 4, 5, 6}, array{3, 16, 65, 200}); // { dg-error "expansion of" "" { target debug_mode } } +constexpr auto m42 = mapping<4>(array{3, 4, 5, 6}, array{200, 65, 3, 16}); // { dg-error "expansion of" "" { target debug_mode } } +constexpr auto m43 = mapping<4>(array{5, 3, 6, 4}, array{3, 65, 200, 16}); +constexpr auto m44 = mapping<4>(array{5, 3, 6, 4}, array{3, 16, 200, 65}); // { dg-error "expansion of" "" { target debug_mode } } + // { dg-prune-output "non-constant condition for static assertion" } // { dg-prune-output "__glibcxx_assert_fail()" } diff --git a/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_unique.cc b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_unique.cc new file mode 100644 index 00000000000..767e5f2fedf --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/mdspan/layouts/stride_unique.cc @@ -0,0 +1,42 @@ +// { dg-do compile { target c++23 } } +#include + +constexpr size_t dyn = std::dynamic_extent; + +using std::array; +template + using mapping = std::layout_stride::mapping>; + +constexpr auto m0 = mapping<0>(array{}, array{}); + +// Zero strides allowed for empty mappings +constexpr auto m00 = mapping<1>(array{0}, array{0}); +constexpr auto m01 = mapping<2>(array{0, 1}, array{3, 0}); +constexpr auto m02 = mapping<2>(array{0, 1}, array{0, 0}); +constexpr auto m03 = mapping<3>(array{0, 1, 2}, array{3, 0, 0}); +constexpr auto m04 = mapping<3>(array{0, 1, 2}, array{3, 3, 0}); +constexpr auto m05 = mapping<4>(array{0, 1, 2, 3}, array{5, 3, 0, 2}); + +// Equal indicies allowed if extents are 1 +constexpr auto m21 = mapping<2>(array{5, 1}, array{1, 1}); +constexpr auto m22 = mapping<3>(array{1, 5, 1}, array{1, 1, 1}); +constexpr auto m23 = mapping<4>(array{1, 1, 5, 1}, array{1, 1, 1, 1}); +constexpr auto m24 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 3, 3, 45}); +constexpr auto m25 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 3, 10, 45}); +constexpr auto m26 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10, 3, 45}); +constexpr auto m27 = mapping<5>(array{3, 4, 1, 1, 5}, array{3, 10, 10, 10, 45}); + +// Unique if stride 3 corresponds to extent 3 +constexpr auto m28 = mapping<2>(array{3, 4}, array{3, 10}); +constexpr auto m30 = mapping<2>(array{4, 3}, array{10, 3}); + +// Unique if stride 11 corresponds to extent 3, as 11 * 3 < 35, and 2 * 5 < 11 +constexpr auto m32 = mapping<3>(array{3, 4, 5}, array{11, 2, 35}); +constexpr auto m33 = mapping<3>(array{3, 4, 5}, array{11, 35, 2}); +constexpr auto m36 = mapping<3>(array{5, 4, 3}, array{2, 35, 11}); +constexpr auto m38 = mapping<3>(array{5, 3, 4}, array{35, 11, 2}); + +// Unique for stride -> extent mapping: 3 * 5 < 16, 15 * 4 < 65, 65 * 3 < 200 +constexpr auto m40 = mapping<4>(array{3, 4, 5, 6}, array{65, 16, 3, 200}); +constexpr auto m43 = mapping<4>(array{5, 3, 6, 4}, array{3, 65, 200, 16}); +