ldionne created this revision.
ldionne added a reviewer: majnemer.
ldionne added a subscriber: cfe-commits.
This patch adds a `__nth_element` builtin that allows fetching the n-th type of
a parameter pack with very little compile-time overhead. The patch was inspired
by r252036 and r252115 by David Majnemer, which add a similar
`__make_integer_seq` builtin for efficiently creating a `std::integer_sequence`.
http://reviews.llvm.org/D15421
Files:
include/clang/AST/ASTContext.h
include/clang/AST/DeclTemplate.h
include/clang/Basic/Builtins.h
include/clang/Basic/DiagnosticSemaKinds.td
include/clang/Serialization/ASTBitCodes.h
lib/AST/ASTContext.cpp
lib/AST/DeclTemplate.cpp
lib/Lex/PPMacroExpansion.cpp
lib/Sema/SemaLookup.cpp
lib/Sema/SemaTemplate.cpp
lib/Serialization/ASTReader.cpp
lib/Serialization/ASTWriter.cpp
test/PCH/nth-element.cpp
test/SemaCXX/nth_element.cpp
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 <unsigned int i, typename ...T>
+using NthElement = __nth_element<unsigned int, i, T...>;
+
+template <int i>
+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 <typename IndexType, IndexType Index, typename ...T>
+using ErrorNthElement1 = __nth_element<IndexType, Index, T...>; // expected-error{{may not be accessed at an out of bounds index}}
+using illformed1 = ErrorNthElement1<int, 3, X<0>, X<1>>; // expected-note{{in instantiation}}
+
+
+template <typename IndexType, IndexType Index, typename ...T>
+using ErrorNthElement2 = __nth_element<IndexType, Index, T...>; // expected-error{{may not be accessed at an out of bounds index}}
+using illformed2 = ErrorNthElement2<int, -2, X<0>, X<1>>; // expected-note{{in instantiation}}
+
+
+template <typename IndexType, IndexType Index, typename ...T>
+using ErrorNthElement3 = __nth_element<IndexType, Index, T...>; // expected-error{{must be indexed using an integral type}}
+enum Color : int { Red, Green, Blue };
+using illformed3 = ErrorNthElement3<Color, Blue, X<0>, X<1>, X<2>>; // expected-note{{in instantiation}}
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 <int i>
+struct X { };
+
+template <unsigned int i, typename ...T>
+using NthElement = __nth_element<unsigned int, i, T...>;
+
+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: lib/Serialization/ASTWriter.cpp
===================================================================
--- lib/Serialization/ASTWriter.cpp
+++ lib/Serialization/ASTWriter.cpp
@@ -4145,6 +4145,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: lib/Serialization/ASTReader.cpp
===================================================================
--- lib/Serialization/ASTReader.cpp
+++ lib/Serialization/ASTReader.cpp
@@ -6422,6 +6422,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/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 <iterator>
using namespace clang;
using namespace sema;
@@ -2026,7 +2027,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<S, T, N> are treated like
// S<T, 0, ..., N-1>.
@@ -2068,6 +2069,42 @@
return SemaRef.CheckTemplateIdType(Converted[0].getAsTemplate(),
TemplateLoc, SyntheticTemplateArgs);
}
+
+ case BTK__nth_element:
+ // Specializations of
+ // __nth_element<IndexType, Index, T_1, ..., T_N>
+ // 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/Sema/SemaLookup.cpp
===================================================================
--- lib/Sema/SemaLookup.cpp
+++ lib/Sema/SemaLookup.cpp
@@ -669,10 +669,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/Lex/PPMacroExpansion.cpp
===================================================================
--- lib/Lex/PPMacroExpansion.cpp
+++ lib/Lex/PPMacroExpansion.cpp
@@ -1642,6 +1642,7 @@
StringRef Feature = FeatureII->getName();
Value = llvm::StringSwitch<bool>(Feature)
.Case("__make_integer_seq", getLangOpts().CPlusPlus)
+ .Case("__nth_element", getLangOpts().CPlusPlus)
.Default(false);
}
} else if (II == Ident__has_attribute)
Index: lib/AST/DeclTemplate.cpp
===================================================================
--- lib/AST/DeclTemplate.cpp
+++ lib/AST/DeclTemplate.cpp
@@ -1240,11 +1240,40 @@
Params, 3, 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 <typename IndexType, IndexType Index, typename ...T>
+ NamedDecl *Params[] = {IndexType, Index, Ts};
+ return TemplateParameterList::Create(C, SourceLocation(), SourceLocation(),
+ Params, 3, 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/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),
@@ -930,6 +931,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: include/clang/Serialization/ASTBitCodes.h
===================================================================
--- include/clang/Serialization/ASTBitCodes.h
+++ include/clang/Serialization/ASTBitCodes.h
@@ -985,13 +985,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: include/clang/Basic/DiagnosticSemaKinds.td
===================================================================
--- include/clang/Basic/DiagnosticSemaKinds.td
+++ include/clang/Basic/DiagnosticSemaKinds.td
@@ -2072,6 +2072,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/Basic/Builtins.h
===================================================================
--- include/clang/Basic/Builtins.h
+++ include/clang/Basic/Builtins.h
@@ -210,6 +210,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/AST/DeclTemplate.h
===================================================================
--- include/clang/AST/DeclTemplate.h
+++ include/clang/AST/DeclTemplate.h
@@ -1483,8 +1483,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/AST/ASTContext.h
===================================================================
--- include/clang/AST/ASTContext.h
+++ include/clang/AST/ASTContext.h
@@ -250,6 +250,9 @@
/// The identifier '__make_integer_seq'.
mutable IdentifierInfo *MakeIntegerSeqName = nullptr;
+ /// The identifier '__nth_element'.
+ mutable IdentifierInfo *NthElementName = nullptr;
+
QualType ObjCConstantStringType;
mutable RecordDecl *CFConstantStringTypeDecl;
@@ -404,6 +407,7 @@
TranslationUnitDecl *TUDecl;
mutable ExternCContextDecl *ExternCContext;
mutable BuiltinTemplateDecl *MakeIntegerSeqDecl;
+ mutable BuiltinTemplateDecl *NthElementDecl;
/// \brief The associated SourceManager object.a
SourceManager &SourceMgr;
@@ -874,6 +878,7 @@
ExternCContextDecl *getExternCContextDecl() const;
BuiltinTemplateDecl *getMakeIntegerSeqDecl() const;
+ BuiltinTemplateDecl *getNthElementDecl() const;
// Builtin Types.
CanQualType VoidTy;
@@ -1459,6 +1464,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() {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
