Index: include/clang/AST/ASTContext.h =================================================================== --- include/clang/AST/ASTContext.h +++ include/clang/AST/ASTContext.h @@ -252,6 +252,9 @@ /// The identifier '__make_integer_seq'. mutable IdentifierInfo *MakeIntegerSeqName = nullptr; + /// The identifier '__nth_element'. + mutable IdentifierInfo *NthElementName = nullptr; + QualType ObjCConstantStringType; mutable RecordDecl *CFConstantStringTypeDecl; @@ -406,6 +409,7 @@ TranslationUnitDecl *TUDecl; mutable ExternCContextDecl *ExternCContext; mutable BuiltinTemplateDecl *MakeIntegerSeqDecl; + mutable BuiltinTemplateDecl *NthElementDecl; /// \brief The associated SourceManager object.a SourceManager &SourceMgr; @@ -876,6 +880,7 @@ ExternCContextDecl *getExternCContextDecl() const; BuiltinTemplateDecl *getMakeIntegerSeqDecl() const; + BuiltinTemplateDecl *getNthElementDecl() const; // Builtin Types. CanQualType VoidTy; @@ -1464,6 +1469,12 @@ return MakeIntegerSeqName; } + IdentifierInfo *getNthElementName() const { + if (!NthElementName) + NthElementName = &Idents.get("__nth_element"); + return NthElementName; + } + /// \brief Retrieve the Objective-C "instancetype" type, if already known; /// otherwise, returns a NULL type; QualType getObjCInstanceType() { Index: include/clang/AST/DeclTemplate.h =================================================================== --- include/clang/AST/DeclTemplate.h +++ include/clang/AST/DeclTemplate.h @@ -1480,8 +1480,8 @@ }; /// \brief Represents the builtin template declaration which is used to -/// implement __make_integer_seq. It serves no real purpose beyond existing as -/// a place to hold template parameters. +/// implement __make_integer_seq and other builtin templates. It serves +/// no real purpose beyond existing as a place to hold template parameters. class BuiltinTemplateDecl : public TemplateDecl { void anchor() override; Index: include/clang/Basic/Builtins.h =================================================================== --- include/clang/Basic/Builtins.h +++ include/clang/Basic/Builtins.h @@ -214,6 +214,9 @@ enum BuiltinTemplateKind : int { /// \brief This names the __make_integer_seq BuiltinTemplateDecl. BTK__make_integer_seq + + /// \brief This names the __nth_element BuiltinTemplateDecl. + , BTK__nth_element }; } // end namespace clang Index: include/clang/Basic/DiagnosticSemaKinds.td =================================================================== --- include/clang/Basic/DiagnosticSemaKinds.td +++ include/clang/Basic/DiagnosticSemaKinds.td @@ -2079,6 +2079,12 @@ def err_integer_sequence_integral_element_type : Error< "integer sequences must have integral element type">; +// __nth_element +def err_nth_element_out_of_bounds : Error< + "a parameter pack may not be accessed at an out of bounds index">; +def err_nth_element_integral_index_type : Error< + "a parameter pack must be indexed using an integral type">; + // Objective-C++ def err_objc_decls_may_only_appear_in_global_scope : Error< "Objective-C declarations may only appear in global scope">; Index: include/clang/Serialization/ASTBitCodes.h =================================================================== --- include/clang/Serialization/ASTBitCodes.h +++ include/clang/Serialization/ASTBitCodes.h @@ -987,13 +987,16 @@ /// \brief The internal '__make_integer_seq' template. PREDEF_DECL_MAKE_INTEGER_SEQ_ID = 13, + + /// \brief The internal '__nth_element' template. + PREDEF_DECL_NTH_ELEMENT_ID = 14, }; /// \brief The number of declaration IDs that are predefined. /// /// For more information about predefined declarations, see the /// \c PredefinedDeclIDs type and the PREDEF_DECL_*_ID constants. - const unsigned int NUM_PREDEF_DECL_IDS = 14; + const unsigned int NUM_PREDEF_DECL_IDS = 15; /// \brief Record code for a list of local redeclarations of a declaration. const unsigned int LOCAL_REDECLARATIONS = 50; Index: lib/AST/ASTContext.cpp =================================================================== --- lib/AST/ASTContext.cpp +++ lib/AST/ASTContext.cpp @@ -743,7 +743,8 @@ ucontext_tDecl(nullptr), BlockDescriptorType(nullptr), BlockDescriptorExtendedType(nullptr), cudaConfigureCallDecl(nullptr), FirstLocalImport(), LastLocalImport(), ExternCContext(nullptr), - MakeIntegerSeqDecl(nullptr), SourceMgr(SM), LangOpts(LOpts), + MakeIntegerSeqDecl(nullptr), NthElementDecl(nullptr), SourceMgr(SM), + LangOpts(LOpts), SanitizerBL(new SanitizerBlacklist(LangOpts.SanitizerBlacklistFiles, SM)), AddrSpaceMap(nullptr), Target(nullptr), AuxTarget(nullptr), PrintingPolicy(LOpts), Idents(idents), Selectors(sels), @@ -928,6 +929,14 @@ return MakeIntegerSeqDecl; } +BuiltinTemplateDecl * +ASTContext::getNthElementDecl() const { + if (!NthElementDecl) + NthElementDecl = buildBuiltinTemplateDecl(BTK__nth_element, + getNthElementName()); + return NthElementDecl; +} + RecordDecl *ASTContext::buildImplicitRecord(StringRef Name, RecordDecl::TagKind TK) const { SourceLocation Loc; Index: lib/AST/DeclTemplate.cpp =================================================================== --- lib/AST/DeclTemplate.cpp +++ lib/AST/DeclTemplate.cpp @@ -1239,11 +1239,41 @@ Params, SourceLocation()); } +static TemplateParameterList * +createNthElement(const ASTContext &C, DeclContext *DC) { + // typename IndexType + auto *IndexType = TemplateTypeParmDecl::Create( + C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/0, + /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/false); + IndexType->setImplicit(true); + + // IndexType Index + TypeSourceInfo *TInfo = C.getTrivialTypeSourceInfo( + QualType(IndexType->getTypeForDecl(), 0)); + auto *Index = NonTypeTemplateParmDecl::Create( + C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/1, + /*Id=*/nullptr, TInfo->getType(), /*ParameterPack=*/false, TInfo); + + // typename ...T + auto *Ts = TemplateTypeParmDecl::Create( + C, DC, SourceLocation(), SourceLocation(), /*Depth=*/0, /*Position=*/2, + /*Id=*/nullptr, /*Typename=*/true, /*ParameterPack=*/true); + Ts->setImplicit(true); + + // template + NamedDecl *Params[] = {IndexType, Index, Ts}; + return TemplateParameterList::Create(C, SourceLocation(), SourceLocation(), + llvm::makeArrayRef(Params), + SourceLocation()); +} + static TemplateParameterList *createBuiltinTemplateParameterList( const ASTContext &C, DeclContext *DC, BuiltinTemplateKind BTK) { switch (BTK) { case BTK__make_integer_seq: return createMakeIntegerSeqParameterList(C, DC); + case BTK__nth_element: + return createNthElement(C, DC); } llvm_unreachable("unhandled BuiltinTemplateKind!"); Index: lib/Lex/PPMacroExpansion.cpp =================================================================== --- lib/Lex/PPMacroExpansion.cpp +++ lib/Lex/PPMacroExpansion.cpp @@ -1640,6 +1640,7 @@ StringRef Feature = FeatureII->getName(); Value = llvm::StringSwitch(Feature) .Case("__make_integer_seq", getLangOpts().CPlusPlus) + .Case("__nth_element", getLangOpts().CPlusPlus) .Default(false); } } else if (II == Ident__has_attribute) Index: lib/Sema/SemaLookup.cpp =================================================================== --- lib/Sema/SemaLookup.cpp +++ lib/Sema/SemaLookup.cpp @@ -676,10 +676,14 @@ R.addDecl(S.getASTContext().getFloat128StubType()); return true; } - if (S.getLangOpts().CPlusPlus && NameKind == Sema::LookupOrdinaryName && - II == S.getASTContext().getMakeIntegerSeqName()) { - R.addDecl(S.getASTContext().getMakeIntegerSeqDecl()); - return true; + if (S.getLangOpts().CPlusPlus && NameKind == Sema::LookupOrdinaryName) { + if (II == S.getASTContext().getMakeIntegerSeqName()) { + R.addDecl(S.getASTContext().getMakeIntegerSeqDecl()); + return true; + } else if (II == S.getASTContext().getNthElementName()) { + R.addDecl(S.getASTContext().getNthElementDecl()); + return true; + } } // If this is a builtin on this (or all) targets, create the decl. Index: lib/Sema/SemaTemplate.cpp =================================================================== --- lib/Sema/SemaTemplate.cpp +++ lib/Sema/SemaTemplate.cpp @@ -32,6 +32,7 @@ #include "llvm/ADT/SmallBitVector.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringExtras.h" +#include using namespace clang; using namespace sema; @@ -2027,7 +2028,7 @@ TemplateArgumentListInfo &TemplateArgs) { ASTContext &Context = SemaRef.getASTContext(); switch (BTD->getBuiltinTemplateKind()) { - case BTK__make_integer_seq: + case BTK__make_integer_seq: { // Specializations of __make_integer_seq are treated like // S. @@ -2069,6 +2070,42 @@ return SemaRef.CheckTemplateIdType(Converted[0].getAsTemplate(), TemplateLoc, SyntheticTemplateArgs); } + + case BTK__nth_element: + // Specializations of + // __nth_element + // are treated like T_Index. + assert(Converted.size() == 3 && + "__nth_element should be given an index type, an index and a parameter pack"); + + // IndexType shall be an integer type. + if (!Converted[0].getAsType()->isIntegralType(Context)) { + SemaRef.Diag(TemplateArgs[0].getLocation(), + diag::err_nth_element_integral_index_type); + return QualType(); + } + + // If the Index is out of bounds, the program is ill-formed. + // + // TODO: + // This is not actually mandated by the standard, of course, so does it + // have its place here? + TemplateArgument IndexArg = Converted[1], Ts = Converted[2]; + llvm::APSInt Index = IndexArg.getAsIntegral(); + if (Index < 0 || Index >= Ts.pack_size()) { + SemaRef.Diag(TemplateArgs[1].getLocation(), + diag::err_nth_element_out_of_bounds); + return QualType(); + } + + // We simply return the type at index `Index`. + // TODO: + // What are the implications of calling .getExtValue() on an APSInt? + assert(Index.getExtValue() == Index && + "oops, I must have done something really wrong here"); + auto Nth = std::next(Ts.pack_begin(), Index.getExtValue()); + return Nth->getAsType(); + } llvm_unreachable("unexpected BuiltinTemplateDecl!"); } Index: lib/Serialization/ASTReader.cpp =================================================================== --- lib/Serialization/ASTReader.cpp +++ lib/Serialization/ASTReader.cpp @@ -6444,6 +6444,9 @@ case PREDEF_DECL_MAKE_INTEGER_SEQ_ID: return Context.getMakeIntegerSeqDecl(); + + case PREDEF_DECL_NTH_ELEMENT_ID: + return Context.getNthElementDecl(); } llvm_unreachable("PredefinedDeclIDs unknown enum value"); } Index: lib/Serialization/ASTWriter.cpp =================================================================== --- lib/Serialization/ASTWriter.cpp +++ lib/Serialization/ASTWriter.cpp @@ -4152,6 +4152,7 @@ RegisterPredefDecl(Context.ExternCContext, PREDEF_DECL_EXTERN_C_CONTEXT_ID); RegisterPredefDecl(Context.MakeIntegerSeqDecl, PREDEF_DECL_MAKE_INTEGER_SEQ_ID); + RegisterPredefDecl(Context.NthElementDecl, PREDEF_DECL_NTH_ELEMENT_ID); // Build a record containing all of the tentative definitions in this file, in // TentativeDefinitions order. Generally, this record will be empty for Index: test/PCH/nth-element.cpp =================================================================== --- /dev/null +++ test/PCH/nth-element.cpp @@ -0,0 +1,14 @@ +// RUN: %clang_cc1 -std=c++14 -x c++-header %s -emit-pch -o %t.pch +// RUN: %clang_cc1 -std=c++14 -x c++ /dev/null -include-pch %t.pch + +template +struct X { }; + +template +using NthElement = __nth_element; + +void fn1() { + X<0> x0 = NthElement<0, X<0>, X<1>, X<2>>{}; + X<1> x1 = NthElement<1, X<0>, X<1>, X<2>>{}; + X<2> x2 = NthElement<2, X<0>, X<1>, X<2>>{}; +} Index: test/SemaCXX/nth_element.cpp =================================================================== --- /dev/null +++ test/SemaCXX/nth_element.cpp @@ -0,0 +1,51 @@ +// RUN: %clang_cc1 -fsyntax-only -verify -std=c++11 %s + +static_assert(__has_builtin(__nth_element), ""); + +template +using NthElement = __nth_element; + +template +struct X; + +static_assert(__is_same(NthElement<0, X<0>>, X<0>), ""); + +static_assert(__is_same(NthElement<0, X<0>, X<1>>, X<0>), ""); +static_assert(__is_same(NthElement<1, X<0>, X<1>>, X<1>), ""); + +static_assert(__is_same(NthElement<0, X<0>, X<1>, X<2>>, X<0>), ""); +static_assert(__is_same(NthElement<1, X<0>, X<1>, X<2>>, X<1>), ""); +static_assert(__is_same(NthElement<2, X<0>, X<1>, X<2>>, X<2>), ""); + +static_assert(__is_same(NthElement<0, X<0>, X<1>, X<2>, X<3>>, X<0>), ""); +static_assert(__is_same(NthElement<1, X<0>, X<1>, X<2>, X<3>>, X<1>), ""); +static_assert(__is_same(NthElement<2, X<0>, X<1>, X<2>, X<3>>, X<2>), ""); +static_assert(__is_same(NthElement<3, X<0>, X<1>, X<2>, X<3>>, X<3>), ""); + +static_assert(__is_same(NthElement<0, X<0>, X<1>, X<2>, X<3>, X<4>>, X<0>), ""); +static_assert(__is_same(NthElement<1, X<0>, X<1>, X<2>, X<3>, X<4>>, X<1>), ""); +static_assert(__is_same(NthElement<2, X<0>, X<1>, X<2>, X<3>, X<4>>, X<2>), ""); +static_assert(__is_same(NthElement<3, X<0>, X<1>, X<2>, X<3>, X<4>>, X<3>), ""); +static_assert(__is_same(NthElement<4, X<0>, X<1>, X<2>, X<3>, X<4>>, X<4>), ""); + +static_assert(__is_same(NthElement<0, X<0>, X<1>, X<2>, X<3>, X<4>, X<5>>, X<0>), ""); +static_assert(__is_same(NthElement<1, X<0>, X<1>, X<2>, X<3>, X<4>, X<5>>, X<1>), ""); +static_assert(__is_same(NthElement<2, X<0>, X<1>, X<2>, X<3>, X<4>, X<5>>, X<2>), ""); +static_assert(__is_same(NthElement<3, X<0>, X<1>, X<2>, X<3>, X<4>, X<5>>, X<3>), ""); +static_assert(__is_same(NthElement<4, X<0>, X<1>, X<2>, X<3>, X<4>, X<5>>, X<4>), ""); +static_assert(__is_same(NthElement<5, X<0>, X<1>, X<2>, X<3>, X<4>, X<5>>, X<5>), ""); + +template +using ErrorNthElement1 = __nth_element; // expected-error{{may not be accessed at an out of bounds index}} +using illformed1 = ErrorNthElement1, X<1>>; // expected-note{{in instantiation}} + + +template +using ErrorNthElement2 = __nth_element; // expected-error{{may not be accessed at an out of bounds index}} +using illformed2 = ErrorNthElement2, X<1>>; // expected-note{{in instantiation}} + + +template +using ErrorNthElement3 = __nth_element; // expected-error{{must be indexed using an integral type}} +enum Color : int { Red, Green, Blue }; +using illformed3 = ErrorNthElement3, X<1>, X<2>>; // expected-note{{in instantiation}}