[Feature] Add a builtin for indexing into parameter packs

[ldionne]

Summary

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.

[nwilson]

Hi Louis,

It would probably be useful to get the lines of context as well by doing a
full diff as describer here: http://llvm.org/docs/Phabricator.html#id3

For example, git diff -U999999 <branch-name>

[ldionne]

Added full lines of context. Sorry for not doing it the first time around.

[ldionne]

We should probably consider changing the name from __nth_element to something else, perhaps something that contains the word "pack". This is especially true if we are to implement other intrinsics for manipulating parameter packs, like slicing (as proposed by Eric Fiselier). Unless someone with a clearer view of the project suggests something, I would probably go with __pack_element (and then we could add __pack_slice, etc...). I have no strong preference.

This patch also raises the question of whether we should have a more separated way of adding builtin templates. My job here was very easy because I just copied David's revision and tweaked a couple of things here and there, but I could imagine it not being obvious at all otherwise. Also, and most importantly, if we add other builtin templates, do we want these builtins to "clutter" the rest of the code instead of being somewhat isolated? I don't know the answer to these questions, but I'd just like to point them out.

lib/AST/DeclTemplate.cpp

1245–1249

It would be simpler and better (IMO) to have template <std::size_t Index, typename ...T> instead of template <typename IndexType, IndexType Index, typename ...T>, but I couldn't figure out how to create a non-type template parameter. Hence, I just adapted the code from David's revision for __make_integer_seq.

lib/Sema/SemaTemplate.cpp

2101–2102

More generally, what is the proper way to retrieve a non-type template argument as a number that I can then use as a normal std::size_t (or similar) in the code? I really just want to retrieve the index, which is given as a non-type template parameter to __nth_element, and convert it to a numeric index n in order to fetch the n-th element of the parameter pack.

[ldionne]

Rebase on top of the master branch, and add Richard Smith as a reviewer, since he also reviewed David Majnemer's original patch (suggested by Nathan Wilson).

[rsmith]

include/clang/Basic/Builtins.h

216–219

Please put the comma after BTK__make_integer_seq, not on this line.

lib/AST/DeclTemplate.cpp

1243

Rename this createNthElementParameterList.

1244–1248

Use NonTypeTemplateParmDecl::Create. You can get size_t from ASTContext::getSizeType.

lib/Sema/SemaTemplate.cpp

2102–2103

getExtValue is OK here, as we don't support size_t being larger than 64 bits.

[rsmith]

Bikeshedding on the name a bit... how about __type_pack_element?

[nwilson]

In D15421#326144, @rsmith wrote:

Bikeshedding on the name a bit... how about __type_pack_element?

Hmm, I kind of felt like having nth in there implied we're indexing into something... What about __nth_pack_element?

[ldionne]

In D15421#326209, @nwilson wrote:

In D15421#326144, @rsmith wrote:

Bikeshedding on the name a bit... how about __type_pack_element?

Hmm, I kind of felt like having nth in there implied we're indexing into something... What about __nth_pack_element?

If anything, I would probably start the name with __pack. This way, we could add other builtins that follow the same pattern, like __pack_slice, __pack_reverse and probably others.

Or if we don't want to start with __pack, then no problem, but we might want to settle on a prefix that will work for other builtins on packs as well.

[ldionne]

Address Richard Smith's review comments:

• Remove IndexType parameter, and make Index a std::size_t
• Remove assertion about APSInt::GetExtValue()
• Other style changes

Still left to do:

• Settle on a name for __nth_element
• Should we produce a diagnostic when the index is out of bounds, or is this reserved for standard-mandated diagnostics (and we should use another mean to report the error)?

[ldionne]

Address some remaining issues:

• Rename nth_element to type_pack_element, as suggested by Richard Smith
• Fix template parameter position issue in createTypePackElementParameterList

AFAICT, the only remaining issue is whether we should produce a diagnostic when the index is out of bounds, or whether this is reserved for standard diagnostics and we should use another mean to report the error. This is a trivial issue and I'll fix it or remove the TODO as soon as someone tells me the right way to go.

I'm really hoping that we can move forward with this patch.

[ldionne]

ping

[rsmith]

Sorry for the delay, this all LGTM. Do you need someone to commit it for you?

lib/Sema/SemaTemplate.cpp

2082–2085

This is fine; we get to specify how our extensions work, so we can say that an Index that's out of bounds is ill-formed.

[ldionne]

No problem for the delay; we're all busy :-). Unfortunately, the patch does not apply cleanly on master anymore, so I'll rebase it and someone can then commit it for me.

[ldionne]

Rebase the patch on top of the current master. The patch passes all of Clang's tests (make check-clang). I also removed the TODO comment about diagnostics, since that was answered by Richard Smith.

[EricWF]

Ping? Is there a reason this hasn't been committed?

[EricWF]

Committed in r274316.

include/clang/AST/ASTContext.h

   /// The identifier '__make_integer_seq'.
   mutable IdentifierInfo *MakeIntegerSeqName = nullptr;
 
+  /// The identifier '__nth_element'.
+  mutable IdentifierInfo *NthElementName = nullptr;
+
   QualType ObjCConstantStringType;
   mutable RecordDecl *CFConstantStringTypeDecl;
   

   TranslationUnitDecl *TUDecl;
   mutable ExternCContextDecl *ExternCContext;
   mutable BuiltinTemplateDecl *MakeIntegerSeqDecl;
+  mutable BuiltinTemplateDecl *NthElementDecl;
 
   /// \brief The associated SourceManager object.a
   SourceManager &SourceMgr;

 
   ExternCContextDecl *getExternCContextDecl() const;
   BuiltinTemplateDecl *getMakeIntegerSeqDecl() const;
+  BuiltinTemplateDecl *getNthElementDecl() const;
 
   // Builtin Types.
   CanQualType VoidTy;

     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() {

include/clang/AST/DeclTemplate.h

 };
 
 /// \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;
 

include/clang/Basic/Builtins.h

 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

include/clang/Basic/DiagnosticSemaKinds.td

 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">;

include/clang/Serialization/ASTBitCodes.h

 
       /// \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;

lib/AST/ASTContext.cpp

       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),

   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;

lib/AST/DeclTemplate.cpp

                                        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!");

lib/Lex/PPMacroExpansion.cpp

         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)

lib/Sema/SemaLookup.cpp

         R.addDecl(S.getASTContext().getFloat128StubType());
         return true;
       }
-      if (S.getLangOpts().CPlusPlus && NameKind == Sema::LookupOrdinaryName &&
-          II == S.getASTContext().getMakeIntegerSeqName()) {
+      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.

lib/Sema/SemaTemplate.cpp

 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
+#include <iterator>
 using namespace clang;
 using namespace sema;
 

                            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>.
 

     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!");
 }
 

lib/Serialization/ASTReader.cpp

 
   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");
 }

lib/Serialization/ASTWriter.cpp

   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

test/PCH/nth-element.cpp

+// 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>>{};
+}

test/SemaCXX/nth_element.cpp

+// 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}}