https://github.com/cor3ntin updated https://github.com/llvm/llvm-project/pull/225025
>From 3fb306ffb42c724135d7017fe9f5c564662f2c41 Mon Sep 17 00:00:00 2001 From: Corentin Jabot <[email protected]> Date: Mon, 21 Sep 2026 10:00:11 +0200 Subject: [PATCH 1/2] [Clang] Implement `__builtin_sort_pack` This is a rework of #152118. Like `__builtin_dedup_pack`, `__builtin_sort_pack` is a builtin that operate a pack->pack trasform, sorting the pack. This is useful to implement some libraries like std::exec, which rely on sorted variants types etc to establish equivalence. Fixes #154966 --- .../clangd/unittests/FindTargetTests.cpp | 6 + clang/docs/LanguageExtensions.md | 31 +++- clang/docs/ReleaseNotes.md | 3 + clang/include/clang/Basic/BuiltinTemplates.td | 4 + clang/lib/AST/DeclTemplate.cpp | 8 +- clang/lib/Sema/SemaTemplate.cpp | 33 ++++ .../test/Import/builtin-template/Inputs/S.cpp | 6 + clang/test/Import/builtin-template/test.cpp | 11 +- clang/test/PCH/dedup_types.cpp | 8 + .../test/SemaTemplate/sort-types-builtin.cpp | 161 ++++++++++++++++++ 10 files changed, 268 insertions(+), 3 deletions(-) create mode 100644 clang/test/SemaTemplate/sort-types-builtin.cpp diff --git a/clang-tools-extra/clangd/unittests/FindTargetTests.cpp b/clang-tools-extra/clangd/unittests/FindTargetTests.cpp index 87febfef753a1..0c0ef1262141f 100644 --- a/clang-tools-extra/clangd/unittests/FindTargetTests.cpp +++ b/clang-tools-extra/clangd/unittests/FindTargetTests.cpp @@ -843,6 +843,12 @@ TEST_F(TargetDeclTest, BuiltinTemplates) { using dedup_types = Templ<[[__builtin_dedup_pack]]<Types...>...>; )cpp"; EXPECT_DECLS("TemplateSpecializationTypeLoc", ); + + Code = R"cpp( + template <template <class...> class Templ, class... Types> + using sort_types = Templ<[[__builtin_sort_pack]]<Types...>...>; + )cpp"; + EXPECT_DECLS("TemplateSpecializationTypeLoc", ); } TEST_F(TargetDeclTest, MemberOfTemplate) { diff --git a/clang/docs/LanguageExtensions.md b/clang/docs/LanguageExtensions.md index bd47b18da2481..cba40dc186d65 100644 --- a/clang/docs/LanguageExtensions.md +++ b/clang/docs/LanguageExtensions.md @@ -1888,6 +1888,35 @@ using MyTypeList = TypeList<__builtin_dedup_pack<int, double, int, char, double, - The resulting pack is currently only supported for expansion in template argument lists and base specifiers. - This builtin cannot be assigned to a template template parameter. +### \_\_builtin_sort_pack + +```c++ +template <class... Ts> +using __builtin_sort_pack = ...; +``` + +This alias takes a template parameter pack `Ts` and produces a new unexpanded pack containing the same types +sorted by [`__builtin_type_order`](#builtin-type-order). + +The resulting pack can be expanded in contexts like template argument lists or base specifiers. + +**Example of Use**: + +```c++ +template <typename...> struct TypeList; + +// Combined with `__builtin_dedup_pack` to canonicalize a type list. +template <typename ...ExtraTypes> +using MyTypeList = TypeList< + __builtin_sort_pack<__builtin_dedup_pack<int, double, ExtraTypes...>...>...>; +``` + +**Limitations**: + +- This builtin can only be used inside a template. +- The resulting pack is currently only supported for expansion in template argument lists and base specifiers. +- This builtin cannot be assigned to a template template parameter. + ## Type Trait Primitives Type trait primitives are special builtin constant expressions that can be used @@ -2056,7 +2085,7 @@ The following type trait primitives are supported by Clang. Those traits marked - `__builtin_lt_synthesizes_from_spaceship`, `__builtin_gt_synthesizes_from_spaceship`, `__builtin_le_synthesizes_from_spaceship`, `__builtin_ge_synthesizes_from_spaceship` (Clang): These builtins can be used to determine whether the corresponding operator is synthesized from a spaceship operator. -- `__builtin_type_order` (C++): Returns `std::strong_ordering::less` if `T` precedes `U` in an +- <span id="builtin-type-order"></span>`__builtin_type_order` (C++): Returns `std::strong_ordering::less` if `T` precedes `U` in an implementation-defined total ordering of all types, `std::strong_ordering::greater` if `U` precedes `T`, and `std::strong_ordering::equal` if they are the same type. diff --git a/clang/docs/ReleaseNotes.md b/clang/docs/ReleaseNotes.md index a1f24a8caedae..3c22f9ba61193 100644 --- a/clang/docs/ReleaseNotes.md +++ b/clang/docs/ReleaseNotes.md @@ -247,6 +247,9 @@ features cannot lower the translation-unit ABI level; - Added support for the `__builtin_strlcat` and `__builtin_strlcpy` builtins. +- Added `__builtin_sort_pack` to sort a pack of types using the same + order as `__builtin_type_order`. + ### New Compiler Flags - New option `-fdefined-pointer-subtraction` added to preserve stable semantics diff --git a/clang/include/clang/Basic/BuiltinTemplates.td b/clang/include/clang/Basic/BuiltinTemplates.td index 504405acbdc78..2f4d0e53fdbd8 100644 --- a/clang/include/clang/Basic/BuiltinTemplates.td +++ b/clang/include/clang/Basic/BuiltinTemplates.td @@ -66,3 +66,7 @@ def __hlsl_spirv_type : HLSLBuiltinTemplate< // template <class ...Args> def __builtin_dedup_pack : CPlusPlusBuiltinTemplate<[Class<"Args", /*is_variadic=*/1>]>; + +// template <class ...Args> +def __builtin_sort_pack + : CPlusPlusBuiltinTemplate<[Class<"Args", /*is_variadic=*/1>]>; diff --git a/clang/lib/AST/DeclTemplate.cpp b/clang/lib/AST/DeclTemplate.cpp index 64cb49b0aa53e..00712c46b2a94 100644 --- a/clang/lib/AST/DeclTemplate.cpp +++ b/clang/lib/AST/DeclTemplate.cpp @@ -1631,7 +1631,13 @@ BuiltinTemplateDecl::BuiltinTemplateDecl(const ASTContext &C, DeclContext *DC, BTK(BTK) {} bool BuiltinTemplateDecl::isPackProducingBuiltinTemplate() const { - return getBuiltinTemplateKind() == clang::BTK__builtin_dedup_pack; + switch (getBuiltinTemplateKind()) { + case BTK__builtin_dedup_pack: + case BTK__builtin_sort_pack: + return true; + default: + return false; + } } bool clang::isPackProducingBuiltinTemplateName(TemplateName N) { diff --git a/clang/lib/Sema/SemaTemplate.cpp b/clang/lib/Sema/SemaTemplate.cpp index 50ff56ff7811e..9cae399651266 100644 --- a/clang/lib/Sema/SemaTemplate.cpp +++ b/clang/lib/Sema/SemaTemplate.cpp @@ -19,6 +19,7 @@ #include "clang/AST/DynamicRecursiveASTVisitor.h" #include "clang/AST/Expr.h" #include "clang/AST/ExprCXX.h" +#include "clang/AST/Mangle.h" #include "clang/AST/TemplateName.h" #include "clang/AST/Type.h" #include "clang/AST/TypeOrdering.h" @@ -40,6 +41,7 @@ #include "clang/Sema/SemaInternal.h" #include "clang/Sema/Template.h" #include "clang/Sema/TemplateDeduction.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallBitVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Support/Casting.h" @@ -3428,6 +3430,28 @@ static SpirvOperand checkHLSLSpirvTypeOperand(Sema &SemaRef, return SpirvOperand::createType(OperandArg); } +static QualType sortBuiltinTemplatePack(ASTContext &Context, + ArrayRef<TemplateArgument> InputArgs) { + // FIXME: cache mangling globally? + std::unique_ptr<MangleContext> MC(Context.createMangleContext()); + SmallVector<std::pair<std::string, TemplateArgument>> SortedArgs( + InputArgs.size()); + llvm::transform( + InputArgs, SortedArgs.begin(), [&](const TemplateArgument &Arg) { + assert(Arg.getKind() == TemplateArgument::Type); + std::string MangledName; + llvm::raw_string_ostream OS(MangledName); + MC->mangleCanonicalTypeName(Arg.getAsType(), OS); + return std::pair<std::string, TemplateArgument>(std::move(MangledName), + Arg); + }); + llvm::stable_sort(SortedArgs, llvm::less_first()); + + auto OutArgs = llvm::to_vector(llvm::make_second_range(SortedArgs)); + return Context.getSubstBuiltinTemplatePack( + TemplateArgument::CreatePackCopy(Context, OutArgs)); +} + static QualType checkBuiltinTemplateIdType( Sema &SemaRef, ElaboratedTypeKeyword Keyword, BuiltinTemplateDecl *BTD, ArrayRef<TemplateArgument> Converted, SourceLocation TemplateLoc, @@ -3587,6 +3611,15 @@ static QualType checkBuiltinTemplateIdType( return Context.getSubstBuiltinTemplatePack( TemplateArgument::CreatePackCopy(Context, OutArgs)); } + case BTK__builtin_sort_pack: { + assert(Converted.size() == 1 && + "__builtin_sort_pack should be given a parameter pack"); + TemplateArgument Ts = Converted[0]; + if (Ts.isDependent()) + return QualType(); + assert(Ts.getKind() == TemplateArgument::Pack); + return sortBuiltinTemplatePack(Context, Ts.getPackAsArray()); + } } llvm_unreachable("unexpected BuiltinTemplateDecl!"); } diff --git a/clang/test/Import/builtin-template/Inputs/S.cpp b/clang/test/Import/builtin-template/Inputs/S.cpp index 85c71f61b0220..c2e15da48a372 100644 --- a/clang/test/Import/builtin-template/Inputs/S.cpp +++ b/clang/test/Import/builtin-template/Inputs/S.cpp @@ -22,5 +22,11 @@ using SameAsX = X<I>; template <template <class...> class Templ, class...Types> using TypePackDedup = Templ<__builtin_dedup_pack<Types...>...>; +template <template <class...> class Templ, class...Types> +using TypePackSort = Templ<__builtin_sort_pack<Types...>...>; + +struct A {}; +struct B {}; + template <class ...Ts> struct TypeList {}; diff --git a/clang/test/Import/builtin-template/test.cpp b/clang/test/Import/builtin-template/test.cpp index aa76c6c752787..1e8132e60b8f8 100644 --- a/clang/test/Import/builtin-template/test.cpp +++ b/clang/test/Import/builtin-template/test.cpp @@ -1,11 +1,13 @@ // RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DSEQ | FileCheck --check-prefix=CHECK-SEQ %s // RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DPACK | FileCheck --check-prefix=CHECK-PACK %s // RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DDEDUP | FileCheck --check-prefix=CHECK-DEDUP %s -// RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DPACK -Xcc -DSEQ -Xcc -DDEDUP | FileCheck --check-prefixes=CHECK-SEQ,CHECK-PACK,CHECK-DEDUP %s +// RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DSORT | FileCheck --check-prefix=CHECK-SORT %s +// RUN: clang-import-test -dump-ast -import %S/Inputs/S.cpp -expression %s -Xcc -DPACK -Xcc -DSEQ -Xcc -DDEDUP -Xcc -DSORT | FileCheck --check-prefixes=CHECK-SEQ,CHECK-PACK,CHECK-DEDUP,CHECK-SORT %s // CHECK-SEQ: BuiltinTemplateDecl {{.+}} <<invalid sloc>> <invalid sloc> implicit referenced __make_integer_seq{{$}} // CHECK-PACK: BuiltinTemplateDecl {{.+}} <<invalid sloc>> <invalid sloc> implicit referenced __type_pack_element{{$}} // CHECK-DEDUP: BuiltinTemplateDecl {{.+}} <<invalid sloc>> <invalid sloc> implicit referenced __builtin_dedup_pack{{$}} +// CHECK-SORT: BuiltinTemplateDecl {{.+}} <<invalid sloc>> <invalid sloc> implicit referenced __builtin_sort_pack{{$}} void expr() { #ifdef SEQ @@ -30,4 +32,11 @@ void expr() { static_assert(__is_same(TypePackDedup<TypeList, X<0>, X<1>, X<1>, X<2>, X<0>>, TypeList<X<0>, X<1>, X<2>>), ""); static_assert(__is_same(TypePackDedup<TypeList, X0, SameAsX<1>, X<1>, X<0>>, TypeList<X<0>,X<1>>), ""); #endif + +#ifdef SORT + static_assert(__is_same(TypePackSort<TypeList>, TypeList<>), ""); + static_assert(__is_same(TypePackSort<TypeList, A, B>, TypeList<A, B>), ""); + static_assert(__is_same(TypePackSort<TypeList, B, A>, TypeList<A, B>), ""); + static_assert(__is_same(TypePackSort<TypeList, B, A, B>, TypeList<A, B, B>), ""); +#endif } diff --git a/clang/test/PCH/dedup_types.cpp b/clang/test/PCH/dedup_types.cpp index d4b19b4411169..ffad060d466f0 100644 --- a/clang/test/PCH/dedup_types.cpp +++ b/clang/test/PCH/dedup_types.cpp @@ -7,14 +7,22 @@ template <template <class...> class Templ, class...Types> using TypePackDedup = Templ<__builtin_dedup_pack<Types...>...>; +template <template <class...> class Templ, class...Types> +using TypePackSort = Templ<__builtin_sort_pack<Types...>...>; + template <class ...Ts> struct TypeList {}; template <int i> struct X {}; +struct A {}; +struct B {}; + void fn1() { TypeList<int, double> l1 = TypePackDedup<TypeList, int, double, int>{}; TypeList<> l2 = TypePackDedup<TypeList>{}; TypeList<X<0>, X<1>> x1 = TypePackDedup<TypeList, X<0>, X<1>, X<0>, X<1>>{}; + TypeList<A, B> s1 = TypePackSort<TypeList, B, A>{}; + TypeList<> s2 = TypePackSort<TypeList>{}; } diff --git a/clang/test/SemaTemplate/sort-types-builtin.cpp b/clang/test/SemaTemplate/sort-types-builtin.cpp new file mode 100644 index 0000000000000..0338e2cbd2a39 --- /dev/null +++ b/clang/test/SemaTemplate/sort-types-builtin.cpp @@ -0,0 +1,161 @@ +// RUN: %clang_cc1 -triple x86_64-unknown-linux-gnu -std=c++20 -fsyntax-only -verify -DITANIUM %s +// RUN: %clang_cc1 -triple x86_64-pc-windows-msvc -std=c++20 -fsyntax-only -verify -DMICROSOFT %s + +template <class...> struct TypeList; + +template <class... Ts> +struct Sorted { + using type = TypeList<__builtin_sort_pack<Ts...>...>; +}; + +template <class... Ts> +struct UniqueSorted { + using type = TypeList<__builtin_sort_pack<__builtin_dedup_pack<Ts...>...>...>; +}; + +template <class... Ts> +struct SortTwice { + using Once = TypeList<__builtin_sort_pack<Ts...>...>; + using Twice = TypeList<__builtin_sort_pack<__builtin_sort_pack<Ts...>...>...>; +}; + +namespace std { +struct strong_ordering { + enum __order { LT = -1, EQ = 0, GT = 1 }; + __order value; + + constexpr explicit strong_ordering(__order value) : value(value) {} + constexpr bool operator==(strong_ordering const &other) const { + return value == other.value; + } + static const strong_ordering less; + static const strong_ordering equal; + static const strong_ordering greater; +}; + +inline constexpr strong_ordering strong_ordering::less(__order::LT); +inline constexpr strong_ordering strong_ordering::equal(__order::EQ); +inline constexpr strong_ordering strong_ordering::greater(__order::GT); +} // namespace std + +struct A {}; +struct B {}; + +static_assert(__is_same(Sorted<>::type, TypeList<>)); +static_assert(__is_same(Sorted<int>::type, TypeList<int>)); +static_assert(__is_same(Sorted<int, int, int>::type, TypeList<int, int, int>)); +static_assert(__is_same(Sorted<A, B>::type, TypeList<A, B>)); +static_assert(__is_same(Sorted<B, A>::type, TypeList<A, B>)); + +#ifdef ITANIUM +static_assert(__is_same(Sorted<int, double>::type, TypeList<double, int>)); +static_assert(__is_same(Sorted<int, double, int, double>::type, + TypeList<double, double, int, int>)); +static_assert(__is_same(Sorted<char, int, double, float>::type, + TypeList<char, double, float, int>)); +static_assert(__is_same(Sorted<A, int>::type, TypeList<A, int>)); +static_assert(__is_same(UniqueSorted<int, double, int, float, double>::type, + TypeList<double, float, int>)); +#endif + +#ifdef MICROSOFT +static_assert(__is_same(Sorted<int, double>::type, TypeList<int, double>)); +static_assert(__is_same(Sorted<int, double, int, double>::type, + TypeList<int, int, double, double>)); +static_assert(__is_same(Sorted<char, int, double, float>::type, + TypeList<char, int, float, double>)); +static_assert(__is_same(Sorted<A, int>::type, TypeList<int, A>)); +static_assert(__is_same(UniqueSorted<int, double, int, float, double>::type, + TypeList<int, float, double>)); +#endif + +using Int = int; +using Dbl = double; +static_assert(__is_same(Sorted<Int, Dbl>::type, Sorted<int, double>::type)); +static_assert(__is_same(UniqueSorted<int, int, int>::type, TypeList<int>)); + +static_assert(__is_same(SortTwice<B, int, A, double>::Once, + SortTwice<B, int, A, double>::Twice)); + +template <class T, class U> +struct SortMatchesTypeOrder { + using SortedTU = TypeList<__builtin_sort_pack<T, U>...>; + using SortedUT = TypeList<__builtin_sort_pack<U, T>...>; + static constexpr auto Cmp = __builtin_type_order(T, U); + static_assert(Cmp != std::strong_ordering::greater + ? __is_same(SortedTU, TypeList<T, U>) + : __is_same(SortedTU, TypeList<U, T>)); + static_assert(__is_same(SortedTU, SortedUT)); +}; + +template struct SortMatchesTypeOrder<int, int>; +template struct SortMatchesTypeOrder<int, double>; +template struct SortMatchesTypeOrder<double, int>; +template struct SortMatchesTypeOrder<A, B>; +template struct SortMatchesTypeOrder<B, A>; +template struct SortMatchesTypeOrder<int, const int>; +template struct SortMatchesTypeOrder<const int, int>; +template struct SortMatchesTypeOrder<A, int>; +template struct SortMatchesTypeOrder<void *, const void *>; +template struct SortMatchesTypeOrder<int *, int[]>; + +template <class A, class B, class C> +struct AdjacentPairsSorted { + using T0 = __type_pack_element<0, __builtin_sort_pack<A, B, C>...>; + using T1 = __type_pack_element<1, __builtin_sort_pack<A, B, C>...>; + using T2 = __type_pack_element<2, __builtin_sort_pack<A, B, C>...>; + static_assert(__builtin_type_order(T0, T1) != std::strong_ordering::greater); + static_assert(__builtin_type_order(T1, T2) != std::strong_ordering::greater); +}; + +template struct AdjacentPairsSorted<int, double, char>; +template struct AdjacentPairsSorted<B, A, int>; +template struct AdjacentPairsSorted<const int, int, volatile int>; + +template <class T, class U> +struct Dependent { + using S1 = TypeList<__builtin_sort_pack<T, U>...>; + using S2 = TypeList<__builtin_sort_pack<U, T>...>; + using S3 = TypeList<__builtin_sort_pack<double, T>...>; + using S4 = TypeList<__builtin_sort_pack<U, int>...>; +}; + +static_assert(__is_same(Dependent<int, double>::S1, Dependent<int, double>::S2)); +static_assert(__is_same(Dependent<int, double>::S1, Sorted<int, double>::type)); +static_assert(__is_same(Dependent<int, double>::S3, Sorted<double, int>::type)); +static_assert(__is_same(Dependent<int, double>::S4, Sorted<double, int>::type)); + +template <class... Ts> +struct DependentPack { + using type = TypeList<__builtin_sort_pack<Ts...>...>; +}; + +static_assert(__is_same(DependentPack<>::type, TypeList<>)); +static_assert(__is_same(DependentPack<B, A, B>::type, Sorted<B, A, B>::type)); + +__builtin_sort_pack<int, double> err1; // expected-error {{cannot be used outside of template}} \ + // expected-error {{declaration type contains an unexpanded parameter pack}} +TypeList<__builtin_sort_pack<int, double> *> err2; // expected-error {{cannot be used outside of template}} \ + // expected-error {{declaration type contains an unexpanded parameter pack}} +TypeList<const __builtin_sort_pack<int, double>> *err3; // expected-error {{cannot be used outside of template}} \ + // expected-error {{declaration type contains an unexpanded parameter pack}} + +template <template <class...> class Inner> +struct Wrapper { + using result = Inner<int, int, int> *; +}; +TypeList<Wrapper<__builtin_sort_pack>::result> *err11; // expected-error {{cannot be used outside of template}} \ + // expected-error {{use of template '__builtin_sort_pack' requires template arguments}} \ + // expected-note@* {{template declaration from hidden source}} + +template <template <class...> class T = __builtin_sort_pack> // expected-error {{use of template '__builtin_sort_pack' requires template arguments}} \ + // expected-note@* {{template declaration from hidden source}} +struct UseAsTemplate; + +static_assert(__is_same(TypeList<__builtin_sort_pack<int>...>, TypeList<int>)); // expected-error {{outside}} + +template <class> +struct UnexpandedInTemplate { + static_assert(__is_same( // expected-error {{static assertion contains an unexpanded parameter pack}} + TypeList<__builtin_sort_pack<int, double>>, TypeList<double, int>)); +}; >From d119880b8d4b4b84190472309f3dab23c9e0867b Mon Sep 17 00:00:00 2001 From: Corentin Jabot <[email protected]> Date: Mon, 21 Sep 2026 10:18:01 +0200 Subject: [PATCH 2/2] forgot to format --- clang/lib/Sema/SemaTemplate.cpp | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) diff --git a/clang/lib/Sema/SemaTemplate.cpp b/clang/lib/Sema/SemaTemplate.cpp index 9cae399651266..be4044d856f3a 100644 --- a/clang/lib/Sema/SemaTemplate.cpp +++ b/clang/lib/Sema/SemaTemplate.cpp @@ -3436,15 +3436,15 @@ static QualType sortBuiltinTemplatePack(ASTContext &Context, std::unique_ptr<MangleContext> MC(Context.createMangleContext()); SmallVector<std::pair<std::string, TemplateArgument>> SortedArgs( InputArgs.size()); - llvm::transform( - InputArgs, SortedArgs.begin(), [&](const TemplateArgument &Arg) { - assert(Arg.getKind() == TemplateArgument::Type); - std::string MangledName; - llvm::raw_string_ostream OS(MangledName); - MC->mangleCanonicalTypeName(Arg.getAsType(), OS); - return std::pair<std::string, TemplateArgument>(std::move(MangledName), - Arg); - }); + llvm::transform(InputArgs, SortedArgs.begin(), + [&](const TemplateArgument &Arg) { + assert(Arg.getKind() == TemplateArgument::Type); + std::string MangledName; + llvm::raw_string_ostream OS(MangledName); + MC->mangleCanonicalTypeName(Arg.getAsType(), OS); + return std::pair<std::string, TemplateArgument>( + std::move(MangledName), Arg); + }); llvm::stable_sort(SortedArgs, llvm::less_first()); auto OutArgs = llvm::to_vector(llvm::make_second_range(SortedArgs)); _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
