[clang] adds `__type_pack_index` so we can get a type's parameter pack index

[cjdb]

Summary

Similarly to __type_pack_element, C++ doesn't offer a way to extract a
the index of the first occurrence of a type in a parameter pack. This
means that we need to build up context for something that the compiler
already has, and then compute the value in a much less efficient manner
than the compiler.

Clang can compute this information without needing to use extra
resources.

[cjdb]

fixes some code I wrote when debugging

[cjdb]

clang/include/clang/AST/Stmt.h

796–802

These numbers feel very low for how this modification is using them. Perhaps they should both be bumped to 32?

[dblaikie]

clang/include/clang/AST/Stmt.h

796–802

clang does, I think, have specific implementation limits for this sort of thing -

Well, maybe we don't actually enforce a limit on number of template arguments... https://godbolt.org/z/accncYson compiles successfully, and has 2^18 parameters, beyond the 2^16 suggested here.

But maybe 2^16 is just what we test for/somewhat guarantee.

But if the Value is going to be the index into the args, shouldn't it be the same size as NumArgs, at least? (& the comment says 16, so 16 for both Value and NumArgs would seem suitably symmetric, and no larger than the current situation - since it'd just be splitting NumArgs in half, while still meeting the comment's suggestion/requirements?)

An assert, at least, when populating NumArgs to ensure it's no larger might not hurt... (which might be reachable from code/not checked prior - so it could be a hard compilation error, I guess, but I wouldn't feel super strongly about it)

[erichkeane]

Needs a release note.

Also, is this something that has been requested by library? I'd hope this is something that will be used, so I'd like evidence of that.

clang/include/clang/AST/Stmt.h

796–802

Can you explain the math here of how you chose to change this to 16? I see that you removed 7 bits, but took away 16. I'm not sure what NumExprBits is doing though, I got lost a little in that, so if you can calculate that to make sure this needs to be done, it would be appreciated.

Additionally, a static_assert after this to ensure the size isn't changing would also be appreciated.

clang/include/clang/Basic/DiagnosticSemaKinds.td

2960

clang/lib/Sema/SemaExprCXX.cpp

5562

Oh, please don't do this.

5591

What do you mean by usually deliberate here? This is a message users will see, so telling them an assertion is deliberate seems incorrect?

5620

I realize this is the 1st, but this seems like it is going to be a maintenance pain. Can you at least split this into a static-function of IsIntegralTypeTrait that we can use later with table-gen if this gets out of hand?

5625

For the purposes of making the two the same, can you integrate this into EvaluateBooleanTypeTrait? That would be something like:

if (IsIntegralTypeTrait(Kind))
  return EvaluateIntegralTypeTrait(...);
return EvaluateBooleanTypeTrait(...);

[dblaikie]

clang/lib/Sema/SemaExprCXX.cpp

5562

perhaps another way to do this if you want to avoid repeating the return expression would be a small lambda that contains the return expression and uses a simple name - so the returns can just be return ret(); ? (or I guess nest the switch in an if, or in another function that uses ref parameters to populate the result)

Though in this case it's only twice, so I'd probably repeat the expression?

5591

I second the question - though I'd push back on the "This is a message users will see" - unreachables won't be seen by users, they get lowered to UB in release builds - the text isn't in the program anymore. The text is only for Clang developers (and/or clang-as-library users).

[cjdb]

clang/include/clang/AST/Stmt.h

796–802

But if the Value is going to be the index into the args, shouldn't it be the same size as NumArgs, at least? (& the comment says 16, so 16 for both Value and NumArgs would seem suitably symmetric, and no larger than the current situation - since it'd just be splitting NumArgs in half, while still meeting the comment's suggestion/requirements?)

Someone independently confirmed that you can have 200k types in a template, so we should probably be able to count at least that high (or alternatively, we should possibly consider not allowing more than 2^16 template parameters).

Can you explain the math here of how you chose to change this to 16? I see that you removed 7 bits, but took away 16. I'm not sure what NumExprBits is doing though, I got lost a little in that, so if you can calculate that to make sure this needs to be done, it would be appreciated.

The value of NumArgs hasn't changed: I've just codified it. I can't work out why we need NumExprBits, but it's apparently required padding (when I removed it, a bunch of tests failed). Its value is 18, courtesy of clangd in VS Code.

Additionally, a static_assert after this to ensure the size isn't changing would also be appreciated.

There's a static_assert in one of the Stmt constructors, which doesn't want more than eight bytes (we apparently need 16 if we're to change this).

[erichkeane]

clang/include/clang/AST/Stmt.h

796–802

Got it, thanks! We need the NumExprBits because this gets cast to that ExprBitFields (since this inherits from Expr). So thats the 'base type' bits.

18 + 8 + 8 (for the NumExprbits and Kind and Value fields) is 34, so that leaves plenty of extra bits here, right? Usually in these cases we leave things 'as big as we can without growing the thing', then comment where extra bits can be stolen in the future.

So I would just make this 'the rest' of our size, since we're already over 4 bytes, mind as well use them as long as we can.

[cjdb]

clang/lib/Sema/SemaExprCXX.cpp

5620

Done, but in D152034. It's a change that should happen independently of this one IMO.

[erichkeane]

clang/lib/Sema/SemaExprCXX.cpp

5620

Thanks! THat looks good.

[rsmith]

Taking a step back for a moment: what is the intended use case for this? My concern is that most of the time you're going to want to make O(N) such queries into a pack of N elements, resulting in O(N^2) compile time, much like we regrettably get from uses of __type_pack_element. If we can avoid the regret in this case by providing a different intrinsic, perhaps we should do so. (For example, we could take two packs of types, and produce a sequence of integers giving the indexes of each of the first types in the second list, in O(N) time. And similarly we could add a __type_pack_elements that takes a pack of types and a pack of indexes and performs N indexing operations at once, in O(N) time, rather than having the program do it in O(N^2) time.)

[cjdb]

In D151952#4392329, @rsmith wrote:

Taking a step back for a moment: what is the intended use case for this? My concern is that most of the time you're going to want to make O(N) such queries into a pack of N elements, resulting in O(N^2) compile time, much like we regrettably get from uses of __type_pack_element. If we can avoid the regret in this case by providing a different intrinsic, perhaps we should do so. (For example, we could take two packs of types, and produce a sequence of integers giving the indexes of each of the first types in the second list, in O(N) time. And similarly we could add a __type_pack_elements that takes a pack of types and a pack of indexes and performs N indexing operations at once, in O(N) time, rather than having the program do it in O(N^2) time.)

When I wrote this I narrowly had std::get<T>(tuple) and std::get<T>(variant) in mind, both of which are linear in nature. Now that you raise this, I can see the described problem and will implement said feature (maybe there exists a world where std::visit can use this too?). Since we're doing this, it may also be worth checking that T1s... are unique in T2s..., which I'd intended to be a separate feature.

Can we get away with modifying __type_pack_element so that we don't need to introduce a new keyword, or should we have two for each?

[BertalanD]

I am considering making use of this feature in a real-world project. I have a few short observations after rebasing this diff and playing with it for a bit:

• It seems to me that __has_builtin(__type_pack_index) currently evaluates to false. Please include a check for the feature detection working correctly in the test.

• Has there been any coordination with GCC folks on the name/semantics of this builtin?
  
  GCC trunk has recently gained support for __type_pack_element, and on the feature request for it (PR100157), @jwakely has already expressed interest in implementing the reverse of that, i.e. what this diff proposes. A slight incompatibility has managed to seep in: GCC does not allow the use of __type_pack_element in a position where its name would end up being manged; see the Folly bug report. While this is easy to work around (wrap it in a template), as a user, it would be inconvenient needing to add a GCC/Clang check alongside __has_builtin if the two compilers were to come up with incompatibly behaving implementations for this one.

• What would be the expected way of gracefully handing the queried type not being present in the list?
  
  Our std::variant-like type uses a can_contain constraint on its accessors to prevent asking for a type that's not in the type list. We currently achieve this by index_of returning sizeof...(Ts) as a sentinel value if no match was found. libc++'s __find_exactly_one_t uses (size_t)-1 for the same purpose.
  
  I'm targeting C++20, so requires { __type_pack_index(T, InTypes...); } seems to do just what I want, but std::variant is C++17 and std::tuple is even earlier than that. Of course, in earlier language modes you don't have to worry about it working in concepts, but e.g. libc++ static_asserts that the index is not the sentinel. Not sure about what libstdc++'s requirements would be.
  
  In any case, could you please test/document the expected way of recovering from the error?

[jwakely]

In D151952#4396485, @cjdb wrote:

Since we're doing this, it may also be worth checking that T1s... are unique in T2s..., which I'd intended to be a separate feature.

It seems like it would be more efficient to include the uniqueness check in the intrinsic, otherwise std::get<T> and helpers like libstdc++'s variant::__index_of<T> will still need some template metaprogramming to check for uniqueness. Even if there's a separate intrinsic for that, it seems more useful to just have one intrinsic that does both. If you have a use case for finding the index of the first T in a pack, maybe add an additional boolean that requests uniqueness and would cause __type_pack_index to fail if T is not unique.

As @BertalanD also said, it doesn't seem useful to be ill-formed if the type isn't in the pack. That makes it unusable for std::get<T> and std::variant. Libstdc++'s __find_uniq_type_in_pack<T, Types...> returns sizeof...(Types) if T isn't found (either this or -1uz seems fine, you can check the returned index is < sizeof...(Types) to tell if the type was found).

clang/docs/LanguageExtensions.rst

1660

If this intrinsic doesn't (yet?) check for uniqueness, then this get<T> doesn't match std::get<T>. It might be worth mentioning that here.

clang/docs/LanguageExtensions.rst

.. code-block:: c++
   template<typename From, typename To>
   struct is_convertible_to {
     static const bool value = __is_convertible_to(From, To);
   };
   #else
   // Emulate type trait for compatibility with other compilers.
   #endif
 
+.. cpp:function:: __type_pack_index(T, Ts...)
+
+  :cpp:expr:`__type_pack_index` performs a linear search on :cpp:expr:`Ts...` for
+  :cpp:expr:`T` and returns its zero-based index. This is useful for implementing
+  functions like :cpp:expr:`std::get<T>(tuple)`.
+
+  .. code-block:: cpp
+    :caption: Example
+
+    template<class T, class... Ts>
+    T& get(tuple<Ts...>& ts) noexcept {
+      return std::get<__type_pack_index(T, Ts...)>(ts);
+    }
+
 Blocks
 ======
 
 The syntax and high level language feature description is in
 :doc:`BlockLanguageSpec<BlockLanguageSpec>`. Implementation and ABI details for
 the clang implementation are in :doc:`Block-ABI-Apple<Block-ABI-Apple>`.
 
 Query for this feature with ``__has_extension(blocks)``.

clang/include/clang/AST/ExprCXX.h

class TypeTraitExpr final
   SourceLocation RParenLoc;
 
   // Note: The TypeSourceInfos for the arguments are allocated after the
   // TypeTraitExpr.
 
   TypeTraitExpr(QualType T, SourceLocation Loc, TypeTrait Kind,
                 ArrayRef<TypeSourceInfo *> Args,
                 SourceLocation RParenLoc,
-                bool Value);
+                unsigned Value);
 
   TypeTraitExpr(EmptyShell Empty) : Expr(TypeTraitExprClass, Empty) {}
 
   size_t numTrailingObjects(OverloadToken<TypeSourceInfo *>) const {
     return getNumArgs();
   }
 
 public:
   friend class ASTStmtReader;
   friend class ASTStmtWriter;
   friend TrailingObjects;
 
   /// Create a new type trait expression.
   static TypeTraitExpr *Create(const ASTContext &C, QualType T,
                                SourceLocation Loc, TypeTrait Kind,
                                ArrayRef<TypeSourceInfo *> Args,
                                SourceLocation RParenLoc,
-                               bool Value);
+                               unsigned Value);
 
   static TypeTraitExpr *CreateDeserialized(const ASTContext &C,
                                            unsigned NumArgs);
 
   /// Determine which type trait this expression uses.
   TypeTrait getTrait() const {
     return static_cast<TypeTrait>(TypeTraitExprBits.Kind);
   }
 
-  bool getValue() const {
+  unsigned getValue() const {
     assert(!isValueDependent());
     return TypeTraitExprBits.Value;
   }
 
   /// Determine the number of arguments to this type trait.
   unsigned getNumArgs() const { return TypeTraitExprBits.NumArgs; }
 
   /// Retrieve the Ith argument.

clang/include/clang/AST/Stmt.h

class TypeTraitExprBitfields {
     friend class ASTStmtWriter;
     friend class TypeTraitExpr;
 
     unsigned : NumExprBits;
 
     /// The kind of type trait, which is a value of a TypeTrait enumerator.
     unsigned Kind : 8;
 
-    /// If this expression is not value-dependent, this indicates whether
-    /// the trait evaluated true or false.
-    unsigned Value : 1;
+    /// If this expression is not value-dependent, this stores the value.
+    unsigned Value : 8;
 
     /// The number of arguments to this type trait. According to [implimits]
     /// 8 bits would be enough, but we require (and test for) at least 16 bits
     /// to mirror FunctionType.
-    unsigned NumArgs;
+    unsigned NumArgs : 16;
   };
 
   class DependentScopeDeclRefExprBitfields {
     friend class ASTStmtReader;
     friend class ASTStmtWriter;
     friend class DependentScopeDeclRefExpr;
 
     unsigned : NumExprBits;

clang/include/clang/Basic/DiagnosticSemaKinds.td

def err_integer_sequence_negative_length : Error<
   "integer sequences must have non-negative sequence length">;
 def err_integer_sequence_integral_element_type : Error<
   "integer sequences must have integral element type">;
 
 // __type_pack_element
 def err_type_pack_element_out_of_bounds : Error<
   "a parameter pack may not be accessed at an out of bounds index">;
 
+// __type_pack_index
+def err_type_pack_index_not_found : Error<
+  "'__type_pack_index' couldn't find type %0">;
+
 // Objective-C++
 def err_objc_decls_may_only_appear_in_global_scope : Error<
   "Objective-C declarations may only appear in global scope">;
 def warn_auto_var_is_id : Warning<
   "'auto' deduced as 'id' in declaration of %0">,
   InGroup<DiagGroup<"auto-var-id">>;
 
 // Attributes

clang/include/clang/Basic/TokenKinds.def

 TYPE_TRAIT_1(__is_trivially_equality_comparable, IsTriviallyEqualityComparable, KEYCXX)
 TYPE_TRAIT_1(__is_bounded_array, IsBoundedArray, KEYCXX)
 TYPE_TRAIT_1(__is_unbounded_array, IsUnboundedArray, KEYCXX)
 TYPE_TRAIT_1(__is_nullptr, IsNullPointer, KEYCXX)
 TYPE_TRAIT_1(__is_scoped_enum, IsScopedEnum, KEYCXX)
 TYPE_TRAIT_1(__is_referenceable, IsReferenceable, KEYCXX)
 TYPE_TRAIT_1(__can_pass_in_regs, CanPassInRegs, KEYCXX)
 TYPE_TRAIT_2(__reference_binds_to_temporary, ReferenceBindsToTemporary, KEYCXX)
+TYPE_TRAIT_N(__type_pack_index, TypePackIndex, KEYCXX)
 
 // Embarcadero Expression Traits
 EXPRESSION_TRAIT(__is_lvalue_expr, IsLValueExpr, KEYCXX)
 EXPRESSION_TRAIT(__is_rvalue_expr, IsRValueExpr, KEYCXX)
 
 // Embarcadero Unary Type Traits
 TYPE_TRAIT_1(__is_arithmetic, IsArithmetic, KEYCXX)
 TYPE_TRAIT_1(__is_floating_point, IsFloatingPoint, KEYCXX)

clang/lib/AST/ASTImporter.cpp

ExpectedStmt ASTNodeImporter::VisitTypeTraitExpr(TypeTraitExpr *E) {
   if (Err)
     return std::move(Err);
 
   SmallVector<TypeSourceInfo *, 4> ToArgs(E->getNumArgs());
   if (Error Err = ImportContainerChecked(E->getArgs(), ToArgs))
     return std::move(Err);
 
   // According to Sema::BuildTypeTrait(), if E is value-dependent,
-  // Value is always false.
-  bool ToValue = (E->isValueDependent() ? false : E->getValue());
+  // Value is always 0.
+  unsigned ToValue = (E->isValueDependent() ? 0 : E->getValue());
 
   return TypeTraitExpr::Create(
       Importer.getToContext(), ToType, ToBeginLoc, E->getTrait(), ToArgs,
       ToEndLoc, ToValue);
 }
 
 ExpectedStmt ASTNodeImporter::VisitCXXTypeidExpr(CXXTypeidExpr *E) {
   ExpectedType ToTypeOrErr = import(E->getType());

clang/lib/AST/ExprCXX.cpp

bool MaterializeTemporaryExpr::isUsableInConstantExpressions(
   return VD && getType().isConstant(Context) &&
          !getType().isVolatileQualified() &&
          getType()->isLiteralType(Context) &&
          VD->isUsableInConstantExpressions(Context);
 }
 
 TypeTraitExpr::TypeTraitExpr(QualType T, SourceLocation Loc, TypeTrait Kind,
                              ArrayRef<TypeSourceInfo *> Args,
-                             SourceLocation RParenLoc, bool Value)
+                             SourceLocation RParenLoc, unsigned Value)
     : Expr(TypeTraitExprClass, T, VK_PRValue, OK_Ordinary), Loc(Loc),
       RParenLoc(RParenLoc) {
   assert(Kind <= TT_Last && "invalid enum value!");
   TypeTraitExprBits.Kind = Kind;
   assert(static_cast<unsigned>(Kind) == TypeTraitExprBits.Kind &&
          "TypeTraitExprBits.Kind overflow!");
   TypeTraitExprBits.Value = Value;
   TypeTraitExprBits.NumArgs = Args.size();
   assert(Args.size() == TypeTraitExprBits.NumArgs &&
          "TypeTraitExprBits.NumArgs overflow!");
 
   auto **ToArgs = getTrailingObjects<TypeSourceInfo *>();
   for (unsigned I = 0, N = Args.size(); I != N; ++I)
     ToArgs[I] = Args[I];
 
   setDependence(computeDependence(this));
 }
 
 TypeTraitExpr *TypeTraitExpr::Create(const ASTContext &C, QualType T,
                                      SourceLocation Loc,
                                      TypeTrait Kind,
                                      ArrayRef<TypeSourceInfo *> Args,
                                      SourceLocation RParenLoc,
-                                     bool Value) {
+                                     unsigned Value) {
   void *Mem = C.Allocate(totalSizeToAlloc<TypeSourceInfo *>(Args.size()));
   return new (Mem) TypeTraitExpr(T, Loc, Kind, Args, RParenLoc, Value);
 }
 
 TypeTraitExpr *TypeTraitExpr::CreateDeserialized(const ASTContext &C,
                                                  unsigned NumArgs) {
   void *Mem = C.Allocate(totalSizeToAlloc<TypeSourceInfo *>(NumArgs));
   return new (Mem) TypeTraitExpr(EmptyShell());

clang/lib/Parse/ParseDeclCXX.cpp

#include "clang/Basic/TransformTypeTraits.def"
           tok::kw___is_trivially_equality_comparable,
           tok::kw___is_trivially_assignable,
           tok::kw___is_trivially_constructible,
           tok::kw___is_trivially_copyable,
           tok::kw___is_unbounded_array,
           tok::kw___is_union,
           tok::kw___is_unsigned,
           tok::kw___is_void,
-          tok::kw___is_volatile))
+          tok::kw___is_volatile,
+          tok::kw___type_pack_index))
     // GNU libstdc++ 4.2 and libc++ use certain intrinsic names as the
     // name of struct templates, but some are keywords in GCC >= 4.3
     // and Clang. Therefore, when we see the token sequence "struct
     // X", make X into a normal identifier rather than a keyword, to
     // allow libstdc++ 4.2 and libc++ to work properly.
     TryKeywordIdentFallback(true);
 
   struct PreserveAtomicIdentifierInfoRAII {

clang/lib/Parse/ParseExpr.cpp

#define REVERTIBLE_TYPE_TRAIT(Name)                         \
           REVERTIBLE_TYPE_TRAIT(__is_trivially_assignable);
           REVERTIBLE_TYPE_TRAIT(__is_trivially_constructible);
           REVERTIBLE_TYPE_TRAIT(__is_trivially_copyable);
           REVERTIBLE_TYPE_TRAIT(__is_unbounded_array);
           REVERTIBLE_TYPE_TRAIT(__is_union);
           REVERTIBLE_TYPE_TRAIT(__is_unsigned);
           REVERTIBLE_TYPE_TRAIT(__is_void);
           REVERTIBLE_TYPE_TRAIT(__is_volatile);
+          REVERTIBLE_TYPE_TRAIT(__type_pack_index);
 #define TRANSFORM_TYPE_TRAIT_DEF(_, Trait)                                     \
   REVERTIBLE_TYPE_TRAIT(RTT_JOIN(__, Trait));
 #include "clang/Basic/TransformTypeTraits.def"
 #undef REVERTIBLE_TYPE_TRAIT
 #undef RTT_JOIN
         }
 
         // If we find that this is in fact the name of a type trait,

clang/lib/Sema/SemaExprCXX.cpp

static bool EvaluateUnaryTypeTrait(Sema &Self, TypeTrait UTT,
   case UTT_IsTriviallyEqualityComparable:
     return T.isTriviallyEqualityComparableType(C);
   }
 }
 
 static bool EvaluateBinaryTypeTrait(Sema &Self, TypeTrait BTT, QualType LhsT,
                                     QualType RhsT, SourceLocation KeyLoc);
 
-static bool evaluateTypeTrait(Sema &S, TypeTrait Kind, SourceLocation KWLoc,
+static bool EvaluateBooleanTypeTrait(Sema &S, TypeTrait Kind, SourceLocation KWLoc,
                                      ArrayRef<TypeSourceInfo *> Args,
                                      SourceLocation RParenLoc) {
   if (Kind <= UTT_Last)
     return EvaluateUnaryTypeTrait(S, Kind, KWLoc, Args[0]->getType());
 
   // Evaluate BTT_ReferenceBindsToTemporary alongside the IsConstructible
   // traits to avoid duplication.
   if (Kind <= BTT_Last && Kind != BTT_ReferenceBindsToTemporary)
     return EvaluateBinaryTypeTrait(S, Kind, Args[0]->getType(),
                                    Args[1]->getType(), RParenLoc);
bool Sema::CheckTypeTraitArity(unsigned Arity, SourceLocation Loc, size_t N) {
   if (!Arity && N == 0) {
     Diag(Loc, diag::err_type_trait_arity)
         << 1 << 1 << 1 << (int)N << SourceRange(Loc);
     return false;
   }
   return true;
 }
 
+static ExprResult EvaluateIntegralTypeTrait(Sema &S, TypeTrait Kind,
+                                            SourceLocation KeywordLoc,
+                                            ArrayRef<TypeSourceInfo *> Args,
+                                            SourceLocation RParenLoc,
+                                            bool IsDependent) {
+  QualType ResultType = S.Context.getSizeType();
+
+  // Start with zero in case we have a dependent context.
+  unsigned ResultValue = 0;
+
+  if (IsDependent)
+    goto Return;
+
+  switch (Kind) {
+  case clang::TT_TypePackIndex: {
+    // __type_pack_index requires at least two values, but we only checked for
+    // one.
+    if (Args.size() < 2) {
+      S.Diag(KeywordLoc, diag::err_type_trait_arity)
+          << /*Arity*/ 2 << /*select "or more"*/ true
+          << /*pluralise "argument"*/ true << Args.size()
+          << SourceRange(KeywordLoc);
+      return ExprError();
+    }
+
+    QualType Needle = Args[0]->getType();
+    ArrayRef<TypeSourceInfo *> Haystack = Args.drop_front();
+    auto Found = llvm::find_if(Haystack, [&Needle, &S](TypeSourceInfo *RhsT) {
+      return S.Context.hasSameType(Needle, RhsT->getType());
+    });
+
+    if (Found == Args.end()) {
+      S.Diag(KeywordLoc, diag::err_type_pack_index_not_found) << Needle;
+      return ExprError();
+    }
+
+    ResultValue = std::distance(Haystack.begin(), Found);
+    break;
+  }
+  default:
+    llvm_unreachable("unhandled type trait (usualy deliberate)");
+  }
+
+Return:
+  return TypeTraitExpr::Create(S.Context, ResultType, KeywordLoc, Kind, Args,
+                               RParenLoc, ResultValue);
+}
+
 ExprResult Sema::BuildTypeTrait(TypeTrait Kind, SourceLocation KWLoc,
                                 ArrayRef<TypeSourceInfo *> Args,
                                 SourceLocation RParenLoc) {
   if (!CheckTypeTraitArity(getTypeTraitArity(Kind), KWLoc, Args.size()))
     return ExprError();
   QualType ResultType = Context.getLogicalOperationType();
 
   if (Kind <= UTT_Last && !CheckUnaryTypeTraitTypeCompleteness(
                                *this, Kind, KWLoc, Args[0]->getType()))
     return ExprError();
 
   DiagnoseBuiltinDeprecation(*this, Kind, KWLoc);
 
   bool Dependent = false;
   for (unsigned I = 0, N = Args.size(); I != N; ++I) {
     if (Args[I]->getType()->isDependentType()) {
       Dependent = true;
       break;
     }
   }
 
+  if (Kind == clang::TT_TypePackIndex)
+    return EvaluateIntegralTypeTrait(*this, Kind, KWLoc, Args, RParenLoc,
+                                     Dependent);
+
   bool Result = false;
   if (!Dependent)
-    Result = evaluateTypeTrait(*this, Kind, KWLoc, Args, RParenLoc);
+    Result = EvaluateBooleanTypeTrait(*this, Kind, KWLoc, Args, RParenLoc);
 
   return TypeTraitExpr::Create(Context, ResultType, KWLoc, Kind, Args,
                                RParenLoc, Result);
 }
 
 ExprResult Sema::ActOnTypeTrait(TypeTrait Kind, SourceLocation KWLoc,
                                 ArrayRef<ParsedType> Args,
                                 SourceLocation RParenLoc) {

clang/test/SemaCXX/type_pack_index.cpp

+// RUN: %clang_cc1 -fsyntax-only -verify -std=c++11 %s
+
+using size_t = decltype(sizeof(0));
+
+static_assert(__type_pack_index(int, int) == 0, "");
+static_assert(__type_pack_index(long, long, int) == 0, "");
+static_assert(__type_pack_index(int, long, int) == 1, "");
+
+// This will be used by parameter packs most of the time, so we should check they
+// work too.
+template<class T, size_t N, class... Ts>
+constexpr size_t mock_get()
+{
+  return __type_pack_index(T, Ts...);
+}
+
+static_assert(mock_get<int, 0, int, long, double>() == 0, "");
+static_assert(mock_get<long, 1, float, long, int>() == 1, "");
+static_assert(mock_get<double, 2, struct S, long, double>() == 2, "");
+
+// Types mentioned twice return the first occurrence
+// -------------------------------------------------
+enum E {};
+enum class EC : int {};
+struct S;
+union U;
+static_assert(__type_pack_index(S, U, S, S) == 1, "");
+static_assert(__type_pack_index(U, int, long, EC, U, double, __int128, S, EC, U) == 3, "");
+
+template<class T>
+union UT;
+static_assert(__type_pack_index(UT<double>, int, long, EC, U, double, __int128, S, EC, U, UT<int>, UT<double>, UT<short>) == 10, "");
+
+// Qualifiers
+// ----------
+static_assert(__type_pack_index(int const, int const, int) == 0, "");
+static_assert(__type_pack_index(int, int const, int) == 1, "");
+
+static_assert(__type_pack_index(int volatile, int volatile, int) == 0, "");
+static_assert(__type_pack_index(int, int volatile, int) == 1, "");
+
+static_assert(__type_pack_index(int const volatile, int const volatile, int) == 0, "");
+static_assert(__type_pack_index(int, int const volatile, int) == 1, "");
+
+static_assert(__type_pack_index(int&, int const, int, int&) == 2, "");
+static_assert(__type_pack_index(int const&, int const, int const&) == 1, "");
+static_assert(__type_pack_index(int volatile&, int volatile, int const&, int&, int volatile&) == 3, "");
+static_assert(__type_pack_index(int const volatile&, int volatile, int const&, int&, int volatile&, int const volatile&) == 4, "");
+
+static_assert(__type_pack_index(int&&, int const, int, int&, int&&, int const&&) == 3, "");
+static_assert(__type_pack_index(int const&&, int const, int const&, int const&&) == 2, "");
+static_assert(__type_pack_index(int volatile&&, int volatile, int const&, int&, int volatile&, int volatile&&) == 4, "");
+static_assert(__type_pack_index(int const volatile&&, int volatile, int const&, int&, int volatile&, int volatile&&, int const volatile&&) == 5, "");
+
+static_assert(__type_pack_index(int* __restrict, int*, int * __restrict) == 1, "");
+
+// Aliases
+// -------
+using Int = int;
+typedef long Long;
+static_assert(__type_pack_index(int, Int, Long) == 0, "");
+static_assert(__type_pack_index(Int, Int, Long) == 0, "");
+static_assert(__type_pack_index(long, Int, Long) == 1, "");
+static_assert(__type_pack_index(Long, Int, Long) == 1, "");
+
+// Error handling
+// --------------
+//
+// Not enough arguments
+// --------------------
+static_assert(__type_pack_index(), "");    // expected-error{{expected a type}}
+static_assert(__type_pack_index(int), ""); // expected-error{{type trait requires 2 or more arguments; have 1 argument}}
+
+// Type not found
+// --------------
+static_assert(__type_pack_index(int, long long, double));
+// expected-error@-1{{'__type_pack_index' couldn't find type 'int'}}