Move some files to c10/util (#12245)

Summary:
Pull Request resolved: https://github.com/pytorch/pytorch/pull/12245

Move these files to c10/util:
- C++17.h
- Metaprogramming.h
- TypeList.h
- TypeTraits.h
- Array.h

(including .cpp files and test cases)

Reviewed By: ezyang

Differential Revision: D10139933

fbshipit-source-id: ce7ce89392bf1a6be070ffdfc0407a8a2ce4ba6e

10 files changed, 1110 insertions, 0 deletions

diff --git a/c10/util/Array.cpp b/c10/util/Array.cpp
new file mode 100644
index 0000000000..4d87d7d036
--- /dev/null
+++ b/c10/util/Array.cpp
@@ -0,0 +1 @@
+#include <c10/util/Array.h>
diff --git a/c10/util/Array.h b/c10/util/Array.h
new file mode 100644
index 0000000000..83e610bbf3
--- /dev/null
+++ b/c10/util/Array.h
@@ -0,0 +1,322 @@
+/**
+* This file is based on the std::array implementation of libstdc++ at
+* https://gcc.gnu.org/onlinedocs/gcc-7.1.0/libstdc++/api/a01056_source.html
+*
+* Changes:
+*  - isolate, i.e. remove dependencies on internal libstdc++ stuff
+*  - use c++17 behavior even in c++11 or c++14
+*  - remove std::swappable special case because that doesn't work with MSVC
+*  - constexpr more things
+*  - add some features like prepend/tail
+*
+* If using std::array at runtime, feel free to either keep using std::array or use this one - it doesn't really matter.
+* For compile time computations, this one here is preferred because std::array in C++11
+* misses some constexpr specifiers, forcing these methods to be called at runtime instead of compile time.
+*/
+
+// Copyright (C) 2007-2017 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+#pragma once
+
+#include <c10/util/C++17.h>
+#include <stdexcept>
+#include <string>
+#include <utility>
+
+namespace c10 { namespace guts {
+
+namespace detail {
+template<typename _Tp, std::size_t _Nm>
+struct __array_traits final {
+  using _Type = _Tp[_Nm];
+
+  static constexpr _Tp& _S_ref(const _Type& __t, std::size_t __n) noexcept {
+    return const_cast<_Tp&>(__t[__n]);
+  }
+
+  static constexpr _Tp* _S_ptr(const _Type& __t) noexcept {
+    return const_cast<_Tp*>(__t);
+  }
+};
+
+template<typename _Tp>
+struct __array_traits<_Tp, 0> final {
+  struct _Type final {};
+
+  static constexpr _Tp& _S_ref(const _Type& __t, std::size_t) noexcept {
+    return *_S_ptr(__t);
+  }
+
+  static constexpr _Tp* _S_ptr(const _Type&) noexcept {
+    return nullptr;
+  }
+};
+
+[[noreturn]] inline void __throw_out_of_range(std::string msg) {
+  throw std::out_of_range(std::move(msg));
+}
+}
+
+template<typename _Tp, std::size_t _Nm>
+class array final {
+public:
+  using value_type = _Tp;
+  using pointer = value_type*;
+  using const_pointer = const value_type*;
+  using reference = value_type&;
+  using const_reference = const value_type&;
+  using iterator = value_type*;
+  using const_iterator = const value_type*;
+  using size_type = std::size_t;
+  using difference_type = std::ptrdiff_t;
+  using reverse_iterator = std::reverse_iterator<iterator>;
+  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+private:
+  using _AT_Type = detail::__array_traits<_Tp, _Nm>;
+public: // needs to be public member for aggregate initialization
+  typename _AT_Type::_Type _M_elems;
+
+public:
+  // No explicit construct/copy/destroy for aggregate type.
+
+  // DR 776.
+  AT_CPP14_CONSTEXPR void fill(const value_type& __u)
+  { std::fill_n(begin(), size(), __u); }
+
+  AT_CPP14_CONSTEXPR void swap(array& __other)
+  { std::swap_ranges(begin(), end(), __other.begin()); }
+
+  // Iterators.
+  AT_CPP14_CONSTEXPR iterator begin() noexcept
+  { return iterator(data()); }
+
+  constexpr const_iterator begin() const noexcept
+  { return const_iterator(data()); }
+
+  AT_CPP14_CONSTEXPR iterator end() noexcept
+  { return iterator(data() + _Nm); }
+
+  constexpr const_iterator end() const noexcept
+  { return const_iterator(data() + _Nm); }
+
+  AT_CPP14_CONSTEXPR reverse_iterator rbegin() noexcept
+  { return reverse_iterator(end()); }
+
+  constexpr const_reverse_iterator rbegin() const noexcept
+  { return const_reverse_iterator(end()); }
+
+  AT_CPP14_CONSTEXPR reverse_iterator rend() noexcept
+  { return reverse_iterator(begin()); }
+
+  constexpr const_reverse_iterator rend() const noexcept
+  { return const_reverse_iterator(begin()); }
+
+  constexpr const_iterator cbegin() const noexcept
+  { return const_iterator(data()); }
+
+  constexpr const_iterator cend() const noexcept
+  { return const_iterator(data() + _Nm); }
+
+  constexpr const_reverse_iterator crbegin() const noexcept
+  { return const_reverse_iterator(end()); }
+
+  constexpr const_reverse_iterator crend() const noexcept
+  { return const_reverse_iterator(begin()); }
+
+  // Capacity.
+  constexpr size_type size() const noexcept { return _Nm; }
+
+  constexpr size_type max_size() const noexcept { return _Nm; }
+
+  constexpr bool empty() const noexcept { return size() == 0; }
+
+  // Element access.
+  AT_CPP14_CONSTEXPR reference operator[](size_type __n) noexcept
+  { return _AT_Type::_S_ref(_M_elems, __n); }
+
+  constexpr const_reference operator[](size_type __n) const noexcept
+  { return _AT_Type::_S_ref(_M_elems, __n); }
+
+  AT_CPP14_CONSTEXPR reference at(size_type __n) {
+    if (__n >= _Nm) {
+      detail::__throw_out_of_range(std::string() +
+          "array::at: __n (which is " + to_string(__n) + ") " +
+          ">= _Nm (which is " + to_string(_Nm) + ")");
+    }
+    return _AT_Type::_S_ref(_M_elems, __n);
+  }
+
+  constexpr const_reference at(size_type __n) const {
+    // Result of conditional expression must be an lvalue so use
+    // boolean ? lvalue : (throw-expr, lvalue)
+    return __n < _Nm ? _AT_Type::_S_ref(_M_elems, __n)
+      : (detail::__throw_out_of_range(std::string() +
+            "array::at: __n (which is " + to_string(__n) + ") " +
+            ">= _Nm (which is " + to_string(_Nm) + ")"),
+         _AT_Type::_S_ref(_M_elems, 0));
+     }
+
+  AT_CPP14_CONSTEXPR reference front() noexcept
+  { return *begin(); }
+
+  constexpr const_reference front() const noexcept
+  { return _AT_Type::_S_ref(_M_elems, 0); }
+
+  AT_CPP14_CONSTEXPR reference back() noexcept
+  { return _Nm ? *(end() - 1) : *end(); }
+
+  constexpr const_reference back() const noexcept
+  {
+    return _Nm ? _AT_Type::_S_ref(_M_elems, _Nm - 1)
+            : _AT_Type::_S_ref(_M_elems, 0);
+  }
+
+  AT_CPP14_CONSTEXPR pointer data() noexcept
+  { return _AT_Type::_S_ptr(_M_elems); }
+
+  constexpr const_pointer data() const noexcept
+  { return _AT_Type::_S_ptr(_M_elems); }
+};
+
+#if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606
+  template<typename _Tp, typename... _Up>
+  array(_Tp, _Up...) ->
+    array<enable_if_t<(std::is_same<_Tp, _Up>::value && ...), _Tp>, 1 + sizeof...(_Up)>;
+#endif
+
+// Array comparisons.
+namespace detail {
+template<class T, size_t N>
+constexpr inline bool array_equals_(const array<T, N>& lhs, const array<T, N>& rhs, size_t current_index) {
+  return (current_index == N)
+         ? true
+         : (lhs.at(current_index) == rhs.at(current_index) && array_equals_(lhs, rhs, current_index + 1));
+}
+template<class T, size_t N>
+constexpr inline bool array_less_(const array<T, N>& lhs, const array<T, N>& rhs, size_t current_index) {
+  return (current_index == N)
+         ? false
+         : (lhs.at(current_index) < rhs.at(current_index) || array_less_(lhs, rhs, current_index + 1));
+}
+}
+template<typename _Tp, std::size_t _Nm>
+constexpr inline bool operator==(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
+{ return detail::array_equals_(__one, __two, 0); }
+
+template<typename _Tp, std::size_t _Nm>
+constexpr inline bool operator!=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
+{ return !(__one == __two); }
+
+template<typename _Tp, std::size_t _Nm>
+constexpr inline bool operator<(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b)
+{ return detail::array_less_(__a, __b, 0); }
+
+template<typename _Tp, std::size_t _Nm>
+constexpr inline bool operator>(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
+{ return __two < __one; }
+
+template<typename _Tp, std::size_t _Nm>
+constexpr inline bool operator<=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
+{ return !(__one > __two); }
+
+template<typename _Tp, std::size_t _Nm>
+constexpr inline bool operator>=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
+{ return !(__one < __two); }
+
+// Specialized algorithms.
+template<typename _Tp, std::size_t _Nm>
+inline void swap(array<_Tp, _Nm>& __one, array<_Tp, _Nm>& __two) noexcept(noexcept(__one.swap(__two)))
+{ __one.swap(__two); }
+
+template<std::size_t _Int, typename _Tp, std::size_t _Nm>
+constexpr _Tp& get(array<_Tp, _Nm>& __arr) noexcept {
+   static_assert(_Int < _Nm, "array index is within bounds");
+   return detail::__array_traits<_Tp, _Nm>::_S_ref(__arr._M_elems, _Int);
+}
+
+template<std::size_t _Int, typename _Tp, std::size_t _Nm>
+constexpr _Tp&& get(array<_Tp, _Nm>&& __arr) noexcept
+{
+  static_assert(_Int < _Nm, "array index is within bounds");
+  return guts::move(get<_Int>(__arr));
+}
+
+template<std::size_t _Int, typename _Tp, std::size_t _Nm>
+constexpr const _Tp& get(const array<_Tp, _Nm>& __arr) noexcept
+{
+  static_assert(_Int < _Nm, "array index is within bounds");
+  return detail::__array_traits<_Tp, _Nm>::_S_ref(__arr._M_elems, _Int);
+}
+
+/**
+ * Some added features not available in std::array.
+ * Only call these at compile time, they're slow if called at runtime.
+ * Examples:
+ *  tail({2, 3, 4}) == {3, 4}
+ *  prepend(2, {3, 4}) == {2, 3, 4}
+ */
+namespace detail {
+template<class T, size_t N, size_t... I>
+constexpr inline array<T, N-1> tail_(const array<T, N>& arg, guts::index_sequence<I...>) {
+  static_assert(sizeof...(I) == N-1, "invariant");
+  return {{get<I+1>(arg)...}};
+}
+}
+template<class T, size_t N>
+constexpr inline array<T, N-1> tail(const array<T, N>& arg) {
+  static_assert(N > 0, "Can only call tail() on an array with at least one element");
+  return detail::tail_(arg, guts::make_index_sequence<N-1>());
+}
+
+namespace detail {
+template<class T, size_t N, size_t... I>
+constexpr inline array<T, N+1> prepend_(T&& head, const array<T, N>& tail, guts::index_sequence<I...>) {
+  return {{guts::forward<T>(head), get<I>(tail)...}};
+}
+}
+template<class T, size_t N>
+constexpr inline array<T, N+1> prepend(T&& head, const array<T, N>& tail) {
+  return detail::prepend_(guts::forward<T>(head), tail, guts::make_index_sequence<N>());
+}
+
+/**
+ * Convert a C array into a std::array.
+ * Example:
+ *   int source[3] = {2, 3, 4};
+ *   std::array<int, 3> target = to_std_array(source);
+ */
+
+namespace detail {
+template<class T, size_t N, size_t... I>
+constexpr array<T, N> to_array_(const T (&arr)[N], guts::index_sequence<I...>) {
+  return {{arr[I]...}};
+}
+}
+
+template<class T, size_t N>
+constexpr array<T, N> to_array(const T (&arr)[N]) {
+  return detail::to_array_(arr, guts::make_index_sequence<N>());
+}
+
+}}
diff --git a/c10/util/C++17.cpp b/c10/util/C++17.cpp
new file mode 100644
index 0000000000..736a002e5a
--- /dev/null
+++ b/c10/util/C++17.cpp
@@ -0,0 +1 @@
+#include <c10/util/C++17.h>
diff --git a/c10/util/C++17.h b/c10/util/C++17.h
new file mode 100644
index 0000000000..8dd61b9fb2
--- /dev/null
+++ b/c10/util/C++17.h
@@ -0,0 +1,258 @@
+#pragma once
+#ifndef C10_UTIL_CPP17_H_
+#define C10_UTIL_CPP17_H_
+
+#include <type_traits>
+#include <utility>
+#include <memory>
+#include <sstream>
+#include <string>
+
+/*
+ * This header adds some polyfills with C++14 and C++17 functionality
+ */
+
+namespace c10 { namespace guts {
+
+
+
+#ifdef __cpp_lib_transformation_trait_aliases
+template<bool B, class T, class F> using conditional_t = std::conditional_t<B, T, F>;
+template<bool B, class T = void> using enable_if_t = std::enable_if_t<B, T>;
+template<class T> using add_lvalue_reference_t = std::add_lvalue_reference_t<T>;
+template<class T> using remove_reference_t = std::remove_reference_t<T>;
+template<class T> using remove_cv_t = std::remove_cv_t<T>;
+template<class T> using result_of_t = std::result_of_t<T>;
+template<class T> using decay_t = std::decay_t<T>;
+template<class T> using remove_const_t = std::remove_const_t<T>;
+template<class T> using remove_pointer_t = std::remove_pointer_t<T>;
+#else
+template<bool B, class T, class F> using conditional_t = typename std::conditional<B, T, F>::type;
+template<bool B, class T = void> using enable_if_t = typename std::enable_if<B, T>::type;
+template<class T> using add_lvalue_reference_t = typename std::add_lvalue_reference<T>::type;
+template<class T> using remove_reference_t = typename std::remove_reference<T>::type;
+template<class T> using remove_cv_t = typename std::remove_cv<T>::type;
+template<class T> using result_of_t = typename std::result_of<T>::type;
+template<class T> using decay_t = typename std::decay<T>::type;
+template<class T> using remove_const_t = typename std::remove_const<T>::type;
+template<class T> using remove_pointer_t = typename std::remove_pointer<T>::type;
+#endif
+
+
+
+
+// C++11 doesn't have constexpr std::move / std::forward.
+// Implementation taken from libc++.
+template<class T>
+constexpr inline guts::remove_reference_t<T>&& move(T&& t) noexcept {
+  return static_cast<guts::remove_reference_t<T>&&>(t);
+}
+template <class T>
+constexpr inline T&& forward(guts::remove_reference_t<T>& t) noexcept {
+    return static_cast<T&&>(t);
+}
+template <class T>
+constexpr inline T&& forward(guts::remove_reference_t<T>&& t) noexcept {
+    static_assert(!std::is_lvalue_reference<T>::value,
+                  "can not forward an rvalue as an lvalue.");
+    return static_cast<T&&>(t);
+}
+
+
+
+
+#if __cplusplus >= 201402L || defined(__cpp_lib_make_unique) && __cpp_lib_make_unique >= 201304L || \
+  (defined(__ANDROID__) && __ANDROID__ && __cplusplus >= 201300L) || defined(_MSC_VER) && _MSC_VER >= 1900
+
+/* using override */ using std::make_unique;
+
+#else
+
+// Implementation taken from folly
+template <typename T, typename... Args>
+typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
+make_unique(Args&&... args) {
+  return std::unique_ptr<T>(new T(forward<Args>(args)...));
+}
+// Allows 'make_unique<T[]>(10)'. (N3690 s20.9.1.4 p3-4)
+template <typename T>
+typename std::enable_if<std::is_array<T>::value, std::unique_ptr<T>>::type
+make_unique(const size_t n) {
+  return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
+}
+// Disallows 'make_unique<T[10]>()'. (N3690 s20.9.1.4 p5)
+template <typename T, typename... Args>
+typename std::enable_if<std::extent<T>::value != 0, std::unique_ptr<T>>::type
+make_unique(Args&&...) = delete;
+
+#endif
+
+
+
+#ifdef __cpp_lib_integer_sequence
+
+template<class T, T... Ints> using integer_sequence = std::integer_sequence<T, Ints...>;
+template<std::size_t... Ints> using index_sequence = std::index_sequence<Ints...>;
+template<class T, T N> using make_integer_sequence = std::make_integer_sequence<T, N>;
+template<std::size_t N> using make_index_sequence = std::make_index_sequence<N>;
+template<class... T> using index_sequence_for = std::index_sequence_for<T...>;
+
+#else
+
+template<class T, T... Ints> struct integer_sequence {
+  using value_type = T;
+  static constexpr std::size_t size() noexcept {return sizeof...(Ints);}
+};
+template<std::size_t... Ints> using index_sequence = integer_sequence<std::size_t, Ints...>;
+namespace detail {
+  template<class T, std::size_t I, std::size_t N, T... Ints>
+  struct make_integer_sequence_ {
+    using type = typename make_integer_sequence_<T, I+1, N, Ints..., I>::type;
+  };
+  template<class T, std::size_t N, T... Ints>
+  struct make_integer_sequence_<T, N, N, Ints...> {
+    using type = integer_sequence<T, Ints...>;
+  };
+}
+template<class T, T N> using make_integer_sequence = typename detail::make_integer_sequence_<T, 0, N>::type;
+template<std::size_t N> using make_index_sequence = make_integer_sequence<std::size_t, N>;
+static_assert(std::is_same<index_sequence<>, make_index_sequence<0>>::value, "");
+static_assert(std::is_same<index_sequence<0, 1, 2>, make_index_sequence<3>>::value, "");
+template<class... T> using index_sequence_for = make_index_sequence<sizeof...(T)>;
+
+#endif
+
+
+
+
+#ifdef __cpp_lib_logical_traits
+
+template <class... B>
+using conjunction = std::conjunction<B...>;
+template <class... B>
+using disjunction = std::disjunction<B...>;
+template <bool B>
+using bool_constant = std::bool_constant<B>;
+template <class B>
+using negation = std::negation<B>;
+
+#else
+
+// Implementation taken from http://en.cppreference.com/w/cpp/types/conjunction
+template<class...> struct conjunction : std::true_type { };
+template<class B1> struct conjunction<B1> : B1 { };
+template<class B1, class... Bn>
+struct conjunction<B1, Bn...>
+    : conditional_t<bool(B1::value), conjunction<Bn...>, B1> {};
+
+// Implementation taken from http://en.cppreference.com/w/cpp/types/disjunction
+template<class...> struct disjunction : std::false_type { };
+template<class B1> struct disjunction<B1> : B1 { };
+template<class B1, class... Bn>
+struct disjunction<B1, Bn...>
+    : conditional_t<bool(B1::value), B1, disjunction<Bn...>>  { };
+
+// Implementation taken from http://en.cppreference.com/w/cpp/types/integral_constant
+template <bool B>
+using bool_constant = std::integral_constant<bool, B>;
+
+// Implementation taken from http://en.cppreference.com/w/cpp/types/negation
+template<class B>
+struct negation : bool_constant<!bool(B::value)> { };
+
+#endif
+
+
+
+#ifdef __cpp_lib_void_t
+
+template<class T> using void_t = std::void_t<T>;
+
+#else
+
+// Implementation taken from http://en.cppreference.com/w/cpp/types/void_t
+// (it takes CWG1558 into account and also works for older compilers)
+template<typename... Ts> struct make_void { typedef void type;};
+template<typename... Ts> using void_t = typename make_void<Ts...>::type;
+
+#endif
+
+
+
+#ifdef __cpp_lib_apply
+
+template <class F, class Tuple>
+inline constexpr decltype(auto) apply(F&& f, Tuple&& t) {
+  return std::apply(forward<F>(f), forward<Tuple>(t));
+}
+
+#else
+
+// Implementation from http://en.cppreference.com/w/cpp/utility/apply (but modified)
+// TODO This is an incomplete implementation of std::apply, not working for member functions.
+namespace detail {
+template <class F, class Tuple, std::size_t... I>
+constexpr auto apply_impl(F&& f, Tuple&& t, guts::index_sequence<I...>) -> decltype(forward<F>(f)(std::get<I>(forward<Tuple>(t))...))
+{
+    return forward<F>(f)(std::get<I>(forward<Tuple>(t))...);
+}
+}  // namespace detail
+
+template <class F, class Tuple>
+constexpr auto apply(F&& f, Tuple&& t) -> decltype(detail::apply_impl(
+    forward<F>(f), forward<Tuple>(t),
+    guts::make_index_sequence<std::tuple_size<guts::remove_reference_t<Tuple>>::value>{}))
+{
+    return detail::apply_impl(
+        forward<F>(f), forward<Tuple>(t),
+        guts::make_index_sequence<std::tuple_size<guts::remove_reference_t<Tuple>>::value>{});
+}
+
+#endif
+
+
+
+
+#if defined(__cpp_constexpr) && __cpp_constexpr >= 201304
+#  define AT_CPP14_CONSTEXPR constexpr
+#else
+#  define AT_CPP14_CONSTEXPR
+#endif
+
+
+
+
+// GCC 4.8 doesn't define std::to_string, even though that's in C++11. Let's define it.
+namespace detail {
+class DummyClassForToString final {};
+}}}
+namespace std {
+// We use SFINAE to detect if std::to_string exists for a type, but that only works
+// if the function name is defined. So let's define a std::to_string for a dummy type.
+inline std::string to_string(c10::guts::detail::DummyClassForToString) { return ""; }
+}
+namespace c10 { namespace guts { namespace detail {
+
+template<class T, class Enable = void>
+struct to_string_ final {
+    static std::string call(T value) {
+        std::ostringstream str;
+        str << value;
+        return str.str();
+    }
+};
+// If a std::to_string exists, use that instead
+template<class T>
+struct to_string_<T, void_t<decltype(std::to_string(std::declval<T>()))>> final {
+    static std::string call(T value) {
+        return std::to_string(value);
+    }
+};
+}
+template<class T> inline std::string to_string(T value) {
+    return detail::to_string_<T>::call(value);
+}
+
+}}
+
+#endif // C10_UTIL_CPP17_H_
diff --git a/c10/util/Metaprogramming.cpp b/c10/util/Metaprogramming.cpp
new file mode 100644
index 0000000000..f6ee24a79b
--- /dev/null
+++ b/c10/util/Metaprogramming.cpp
@@ -0,0 +1 @@
+#include <c10/util/Metaprogramming.h>
diff --git a/c10/util/Metaprogramming.h b/c10/util/Metaprogramming.h
new file mode 100644
index 0000000000..aa3cf074de
--- /dev/null
+++ b/c10/util/Metaprogramming.h
@@ -0,0 +1,159 @@
+#pragma once
+
+#include <type_traits>
+#include <array>
+#include <functional>
+#include <c10/util/TypeList.h>
+#include <c10/util/Array.h>
+
+namespace c10 { namespace guts {
+namespace detail {
+/**
+ * strip_class: helper to remove the class type from pointers to `operator()`.
+ */
+
+template <typename T>
+struct strip_class {};
+template <typename Class, typename Result, typename... Args>
+struct strip_class<Result (Class::*)(Args...)> {
+  using type = Result(Args...);
+};
+template <typename Class, typename Result, typename... Args>
+struct strip_class<Result (Class::*)(Args...) const> {
+  using type = Result(Args...);
+};
+template <typename T>
+using strip_class_t = typename strip_class<T>::type;
+} // namespace detail
+
+/**
+ * Access information about result type or arguments from a function type.
+ * Example:
+ * using A = function_traits<int (float, double)>::return_type // A == int
+ * using A = function_traits<int (float, double)>::parameter_types::tuple_type // A == tuple<float, double>
+ */
+template<class Func> struct function_traits {
+  static_assert(!std::is_same<Func, Func>::value, "In function_traits<Func>, Func must be a plain function type.");
+};
+template<class Result, class... Args>
+struct function_traits<Result (Args...)> {
+  using func_type = Result (Args...);
+  using return_type = Result;
+  using parameter_types = typelist::typelist<Args...>;
+  static constexpr auto number_of_parameters = sizeof...(Args);
+};
+
+/**
+ * infer_function_traits: creates a `function_traits` type for a simple
+ * function (pointer) or functor (lambda/struct). Currently does not support
+ * class methods.
+ */
+
+template <typename Functor>
+struct infer_function_traits {
+  using type = function_traits<detail::strip_class_t<decltype(&Functor::operator())>>;
+};
+
+template <typename Result, typename... Args>
+struct infer_function_traits<Result (*)(Args...)> {
+  using type = function_traits<Result(Args...)>;
+};
+
+template <typename T>
+using infer_function_traits_t = typename infer_function_traits<T>::type;
+
+/**
+ * Use extract_arg_by_filtered_index to return the i-th argument whose
+ * type fulfills a given type trait. The argument itself is perfectly forwarded.
+ *
+ * Example:
+ * std::string arg1 = "Hello";
+ * std::string arg2 = "World";
+ * std::string&& result = extract_arg_by_filtered_index<is_string, 1>(0, arg1, 2.0, std::move(arg2));
+ *
+ * Warning: Taking the result by rvalue reference can cause segfaults because ownership will not be passed on
+ *          from the original reference. The original reference dies after the expression and the resulting
+ */
+namespace detail {
+template<template <class> class Condition, size_t index, class Enable, class... Args> struct extract_arg_by_filtered_index_;
+template<template <class> class Condition, size_t index, class Head, class... Tail>
+struct extract_arg_by_filtered_index_<Condition, index, guts::enable_if_t<!Condition<Head>::value>, Head, Tail...> {
+  static auto call(Head&& /*head*/, Tail&&... tail)
+  -> decltype(extract_arg_by_filtered_index_<Condition, index, void, Tail...>::call(std::forward<Tail>(tail)...)) {
+    return extract_arg_by_filtered_index_<Condition, index, void, Tail...>::call(std::forward<Tail>(tail)...);
+  }
+};
+template<template <class> class Condition, size_t index, class Head, class... Tail>
+struct extract_arg_by_filtered_index_<Condition, index, guts::enable_if_t<Condition<Head>::value && index != 0>, Head, Tail...> {
+  static auto call(Head&& /*head*/, Tail&&... tail)
+  -> decltype(extract_arg_by_filtered_index_<Condition, index-1, void, Tail...>::call(std::forward<Tail>(tail)...)) {
+    return extract_arg_by_filtered_index_<Condition, index-1, void, Tail...>::call(std::forward<Tail>(tail)...);
+  }
+};
+template<template <class> class Condition, size_t index>
+struct extract_arg_by_filtered_index_<Condition, index, void> {
+  static void call() {
+    static_assert(index != index, "extract_arg_by_filtered_index out of range.");
+  }
+};
+template<template <class> class Condition, size_t index, class Head, class... Tail>
+struct extract_arg_by_filtered_index_<Condition, index, guts::enable_if_t<Condition<Head>::value && index == 0>, Head, Tail...> {
+  static auto call(Head&& head, Tail&&... /*tail*/)
+  -> decltype(std::forward<Head>(head)) {
+    return std::forward<Head>(head);
+  }
+};
+}
+template<template <class> class Condition, size_t index, class... Args>
+auto extract_arg_by_filtered_index(Args&&... args)
+-> decltype(detail::extract_arg_by_filtered_index_<Condition, index, void, Args...>::call(std::forward<Args>(args)...)) {
+  static_assert(is_type_condition<Condition>::value, "In extract_arg_by_filtered_index, the Condition argument must be a condition type trait, i.e. have a static constexpr bool ::value member.");
+  return detail::extract_arg_by_filtered_index_<Condition, index, void, Args...>::call(std::forward<Args>(args)...);
+}
+
+
+
+/**
+ * Use filter_map to map a subset of the arguments to values.
+ * The subset is defined by type traits, and will be evaluated at compile time.
+ * At runtime, it will just loop over the pre-filtered arguments to create an std::array.
+ *
+ * Example:
+ *  // in C++14
+ *  std::array<double, 2> result = filter_map<double, std::is_integral>([] (auto a) {return (double)a;}, 3, "bla", 4);
+ *  // result == {3.0, 4.0}
+ *
+ *  // same example in C++11
+ *  struct my_map {
+ *    template<class T> constexpr double operator()(T a) {
+ *      return (double)a;
+ *    }
+ *  };
+ *  std::array<double, 2> result = filter_map<double, std::is_integral>(my_map(), 3, "bla", 4);
+ *  // result == {3.0, 4.0}
+ */
+namespace detail {
+
+template<class ResultType, size_t num_results> struct filter_map_ {
+   template<template <class> class Condition, class Mapper, class... Args, size_t... I>
+   static guts::array<ResultType, num_results> call(const Mapper& mapper, guts::index_sequence<I...>, Args&&... args) {
+     return guts::array<ResultType, num_results> { mapper(extract_arg_by_filtered_index<Condition, I>(std::forward<Args>(args)...))... };
+   }
+};
+template<class ResultType> struct filter_map_<ResultType, 0> {
+  template<template <class> class Condition, class Mapper, class... Args, size_t... I>
+  static guts::array<ResultType, 0> call(const Mapper& /*mapper*/, guts::index_sequence<I...>, Args&&... /*args*/) {
+    return guts::array<ResultType, 0> { };
+  }
+};
+}
+
+template<class ResultType, template <class> class Condition, class Mapper, class... Args> auto filter_map(const Mapper& mapper, Args&&... args)
+-> decltype(detail::filter_map_<ResultType, typelist::count_if<Condition, typelist::typelist<Args...>>::value>::template call<Condition, Mapper, Args...>(mapper, guts::make_index_sequence<typelist::count_if<Condition, typelist::typelist<Args...>>::value>(), std::forward<Args>(args)...)) {
+  static_assert(is_type_condition<Condition>::value, "In filter_map<Result, Condition>, the Condition argument must be a condition type trait, i.e. have a static constexpr bool ::value member.");
+
+  static constexpr size_t num_results = typelist::count_if<Condition, typelist::typelist<Args...>>::value;
+  return detail::filter_map_<ResultType, num_results>::template call<Condition, Mapper, Args...>(mapper, guts::make_index_sequence<num_results>(), std::forward<Args>(args)...);
+}
+
+}}
diff --git a/c10/util/TypeList.cpp b/c10/util/TypeList.cpp
new file mode 100644
index 0000000000..aa418df1c8
--- /dev/null
+++ b/c10/util/TypeList.cpp
@@ -0,0 +1 @@
+#include <c10/util/TypeList.h>
diff --git a/c10/util/TypeList.h b/c10/util/TypeList.h
new file mode 100644
index 0000000000..4a55e9aaae
--- /dev/null
+++ b/c10/util/TypeList.h
@@ -0,0 +1,301 @@
+#pragma once
+
+#include <c10/util/C++17.h>
+#include <c10/util/TypeTraits.h>
+
+namespace c10 { namespace guts { namespace typelist {
+
+namespace detail {
+template<class... T> struct false_t : std::false_type {};
+}
+
+/**
+ * Type holding a list of types for compile time type computations
+ */
+template<class... Items> struct typelist final {
+private:
+    typelist() = delete; // not for instantiation
+};
+
+
+
+/**
+ * Returns the number of types in a typelist
+ * Example:
+ *   3  ==  size<typelist<int, int, double>>::value
+ */
+template<class TypeList> struct size final {
+    static_assert(detail::false_t<TypeList>::value, "In typelist::size<T>, T must be typelist<...>.");
+};
+template<class... Types> struct size<typelist<Types...>> final {
+    static constexpr size_t value = sizeof...(Types);
+};
+
+
+
+/**
+ * Transforms a list of types into a tuple holding these types.
+ * Example:
+ *   std::tuple<int, string>  ==  to_tuple_t<typelist<int, string>>
+ */
+template<class TypeList> struct to_tuple final {
+    static_assert(detail::false_t<TypeList>::value, "In typelist::to_tuple<T>, T must be typelist<...>.");
+};
+template<class... Types> struct to_tuple<typelist<Types...>> final {
+    using type = std::tuple<Types...>;
+};
+template<class TypeList> using to_tuple_t = typename to_tuple<TypeList>::type;
+
+
+
+
+/**
+ * Creates a typelist containing the types of a given tuple.
+ * Example:
+ *   typelist<int, string>  ==  from_tuple_t<std::tuple<int, string>>
+ */
+template<class Tuple> struct from_tuple final {
+    static_assert(detail::false_t<Tuple>::value, "In typelist::from_tuple<T>, T must be std::tuple<...>.");
+};
+template<class... Types> struct from_tuple<std::tuple<Types...>> final {
+  using type = typelist<Types...>;
+};
+template<class Tuple> using from_tuple_t = typename from_tuple<Tuple>::type;
+
+
+
+/**
+ * Concatenates multiple type lists.
+ * Example:
+ *   typelist<int, string, int>  ==  concat_t<typelist<int, string>, typelist<int>>
+ */
+template<class... TypeLists> struct concat final {
+    static_assert(detail::false_t<TypeLists...>::value, "In typelist::concat<T1, ...>, the T arguments each must be typelist<...>.");
+};
+template<class... Head1Types, class... Head2Types, class... TailLists>
+struct concat<typelist<Head1Types...>, typelist<Head2Types...>, TailLists...> final {
+  using type = typename concat<typelist<Head1Types..., Head2Types...>, TailLists...>::type;
+};
+template<class... HeadTypes>
+struct concat<typelist<HeadTypes...>> final {
+  using type = typelist<HeadTypes...>;
+};
+template<>
+struct concat<> final {
+  using type = typelist<>;
+};
+template<class... TypeLists> using concat_t = typename concat<TypeLists...>::type;
+
+
+
+/**
+ * Filters the types in a type list by a type trait.
+ * Examples:
+ *   typelist<int&, const string&&>  ==  filter_t<std::is_reference, typelist<void, string, int&, bool, const string&&, int>>
+ */
+template<template <class> class Condition, class TypeList> struct filter final {
+  static_assert(detail::false_t<TypeList>::value, "In typelist::filter<Condition, TypeList>, the TypeList argument must be typelist<...>.");
+};
+template<template <class> class Condition, class Head, class... Tail>
+struct filter<Condition, typelist<Head, Tail...>> final {
+  static_assert(is_type_condition<Condition>::value, "In typelist::filter<Condition, TypeList>, the Condition argument must be a condition type trait, i.e. have a static constexpr bool ::value member.");
+  using type = guts::conditional_t<
+    Condition<Head>::value,
+    concat_t<typelist<Head>, typename filter<Condition, typelist<Tail...>>::type>,
+    typename filter<Condition, typelist<Tail...>>::type
+  >;
+};
+template<template <class> class Condition>
+struct filter<Condition, typelist<>> final {
+  static_assert(is_type_condition<Condition>::value, "In typelist::filter<Condition, TypeList>, the Condition argument must be a condition type trait, i.e. have a static constexpr bool ::value member.");
+  using type = typelist<>;
+};
+template<template <class> class Condition, class TypeList>
+using filter_t = typename filter<Condition, TypeList>::type;
+
+
+
+/**
+ * Counts how many types in the list fulfill a type trait
+ * Examples:
+ *   2  ==  count_if<std::is_reference, typelist<void, string, int&, bool, const string&&, int>>
+ */
+template<template <class> class Condition, class TypeList>
+struct count_if final {
+  static_assert(is_type_condition<Condition>::value, "In typelist::count_if<Condition, TypeList>, the Condition argument must be a condition type trait, i.e. have a static constexpr bool ::value member.");
+  static_assert(is_instantiation_of<typelist, TypeList>::value, "In typelist::count_if<Condition, TypeList>, the TypeList argument must be typelist<...>.");
+  // TODO Direct implementation might be faster
+  static constexpr size_t value = size<filter_t<Condition, TypeList>>::value;
+};
+
+
+
+/**
+ * Returns true iff the type trait is true for all types in the type list
+ * Examples:
+ *   true   ==  true_for_each_type<std::is_reference, typelist<int&, const float&&, const MyClass&>>::value
+ *   false  ==  true_for_each_type<std::is_reference, typelist<int&, const float&&, MyClass>>::value
+ */
+template<template <class> class Condition, class TypeList> struct true_for_each_type final {
+    static_assert(detail::false_t<TypeList>::value, "In typelist::true_for_each_type<Condition, TypeList>, the TypeList argument must be typelist<...>.");
+};
+template<template <class> class Condition, class... Types>
+struct true_for_each_type<Condition, typelist<Types...>> final
+: guts::conjunction<Condition<Types>...> {
+    static_assert(is_type_condition<Condition>::value, "In typelist::true_for_each_type<Condition, TypeList>, the Condition argument must be a condition type trait, i.e. have a static constexpr bool ::value member.");
+};
+
+
+
+/**
+ * Maps types of a type list using a type trait
+ * Example:
+ *  typelist<int&, double&, string&>  ==  map_t<std::add_lvalue_reference_t, typelist<int, double, string>>
+ */
+template<template <class> class Mapper, class TypeList> struct map final {
+    static_assert(detail::false_t<TypeList>::value, "In typelist::map<Mapper, TypeList>, the TypeList argument must be typelist<...>.");
+};
+template<template <class> class Mapper, class... Types>
+struct map<Mapper, typelist<Types...>> final {
+  using type = typelist<Mapper<Types>...>;
+};
+template<template <class> class Mapper, class TypeList>
+using map_t = typename map<Mapper, TypeList>::type;
+
+
+
+/**
+ * Returns the first element of a type list.
+ * Example:
+ *   int  ==  head_t<typelist<int, string>>
+ */
+template<class TypeList> struct head final {
+    static_assert(detail::false_t<TypeList>::value, "In typelist::head<T>, the T argument must be typelist<...>.");
+};
+template<class Head, class... Tail> struct head<typelist<Head, Tail...>> final {
+  using type = Head;
+};
+template<class TypeList> using head_t = typename head<TypeList>::type;
+
+/**
+ * Returns the N-th element of a type list.
+ * Example:
+ * int == element_t<1, typelist<float, int, char>>
+ */
+
+/// Base template.
+template<size_t Index, class TypeList> struct element final {
+    static_assert(detail::false_t<TypeList>::value, "In typelist::element<T>, the T argument must be typelist<...>.");
+};
+
+/// Successful case, we have reached the zero index and can "return" the head type.
+template<class Head, class... Tail> struct element<0, typelist<Head, Tail...>> { using type = Head; };
+
+/// Error case, we have an index but ran out of types! It will only be selected
+/// if `Ts...` is actually empty!
+template <size_t Index, class... Ts>
+struct element<Index, typelist<Ts...>> {
+  static_assert(Index < sizeof...(Ts), "Index is out of bounds in typelist::element");
+};
+
+/// Shave off types until we hit the <0, Head, Tail...> or <Index> case.
+template<size_t Index, class Head, class... Tail> struct element<Index, typelist<Head, Tail...>> : element<Index-1, typelist<Tail...>> { };
+
+/// Convenience alias.
+template<size_t Index, class TypeList>
+using element_t = typename element<Index, TypeList>::type;
+
+/**
+ * Returns the last element of a type list.
+ * Example:
+ *   int  ==  last_t<typelist<int, string>>
+ */
+template <class TypeList>
+struct last final {
+  static_assert(
+      detail::false_t<TypeList>::value,
+      "In typelist::last<T>, the T argument must be typelist<...>.");
+};
+template <class Head, class... Tail>
+struct last<typelist<Head, Tail...>> final {
+  using type = typename last<typelist<Tail...>>::type;
+};
+template <class Head>
+struct last<typelist<Head>> final {
+  using type = Head;
+};
+template <class TypeList>
+using last_t = typename last<TypeList>::type;
+static_assert(
+    std::is_same<int, last_t<typelist<double, float, int>>>::value,
+    "");
+
+/**
+ * Reverses a typelist.
+ * Example:
+ *   typelist<int, string>  == reverse_t<typelist<string, int>>
+ */
+template<class TypeList> struct reverse final {
+    static_assert(detail::false_t<TypeList>::value, "In typelist::reverse<T>, the T argument must be typelist<...>.");
+};
+template<class Head, class... Tail> struct reverse<typelist<Head, Tail...>> final {
+  using type = concat_t<typename reverse<typelist<Tail...>>::type, typelist<Head>>;
+};
+template<> struct reverse<typelist<>> final {
+  using type = typelist<>;
+};
+template<class TypeList> using reverse_t = typename reverse<TypeList>::type;
+
+
+
+/**
+ * Maps a list of types into a list of values.
+ * Examples:
+ *   // C++14 example
+ *   auto sizes =
+ *     map_types_to_values<typelist<int64_t, bool, uint32_t>>(
+ *       [] (auto t) { return sizeof(decltype(t)::type); }
+ *     );
+ *   //  sizes  ==  std::tuple<size_t, size_t, size_t>{8, 1, 4}
+ *
+ *   // C++14 example
+ *   auto shared_ptrs =
+ *     map_types_to_values<typelist<int, double>>(
+ *       [] (auto t) { return make_shared<typename decltype(t)::type>(); }
+ *     );
+ *   // shared_ptrs == std::tuple<shared_ptr<int>, shared_ptr<double>>()
+ *
+ *   // C++11 example
+ *   struct map_to_size {
+ *     template<class T> constexpr size_t operator()(T) {
+ *       return sizeof(typename T::type);
+ *     }
+ *   };
+ *   auto sizes =
+ *     map_types_to_values<typelist<int64_t, bool, uint32_t>>(
+ *       map_to_size()
+ *     );
+ *   //  sizes  ==  std::tuple<size_t, size_t, size_t>{8, 1, 4}
+ */
+namespace detail {
+template<class T> struct type_ final {
+    using type = T;
+};
+template<class TypeList> struct map_types_to_values final {
+    static_assert(detail::false_t<TypeList>::value, "In typelist::map_types_to_values<T>, the T argument must be typelist<...>.");
+};
+template<class... Types> struct map_types_to_values<typelist<Types...>> final {
+  template<class Func>
+  static std::tuple<guts::result_of_t<Func(type_<Types>)>...> call(Func&& func) {
+    return std::tuple<guts::result_of_t<Func(type_<Types>)>...> { std::forward<Func>(func)(type_<Types>())... };
+  }
+};
+}
+
+template<class TypeList, class Func> auto map_types_to_values(Func&& func)
+-> decltype(detail::map_types_to_values<TypeList>::call(std::forward<Func>(func))) {
+  return detail::map_types_to_values<TypeList>::call(std::forward<Func>(func));
+}
+
+
+}}}
diff --git a/c10/util/TypeTraits.cpp b/c10/util/TypeTraits.cpp
new file mode 100644
index 0000000000..4457c32179
--- /dev/null
+++ b/c10/util/TypeTraits.cpp
@@ -0,0 +1 @@
+#include <c10/util/TypeTraits.h>
diff --git a/c10/util/TypeTraits.h b/c10/util/TypeTraits.h
new file mode 100644
index 0000000000..ec6437a5a4
--- /dev/null
+++ b/c10/util/TypeTraits.h
@@ -0,0 +1,65 @@
+#pragma once
+
+#include <c10/util/C++17.h>
+#include <functional>
+
+namespace c10 {
+namespace guts {
+
+
+/**
+ * is_equality_comparable<T> is true_type iff the equality operator is defined for T.
+ */
+template<class T, class Enable = void> struct is_equality_comparable : std::false_type {};
+template<class T> struct is_equality_comparable<T, void_t<decltype(std::declval<T&>() == std::declval<T&>())>> : std::true_type {};
+template<class T> using is_equality_comparable_t = typename is_equality_comparable<T>::type;
+
+
+
+/**
+ * is_hashable<T> is true_type iff std::hash is defined for T
+ */
+template<class T, class Enable = void> struct is_hashable : std::false_type {};
+template<class T> struct is_hashable<T, void_t<decltype(std::hash<T>()(std::declval<T&>()))>> : std::true_type {};
+template<class T> using is_hashable_t = typename is_hashable<T>::type;
+
+
+
+/**
+ * is_function_type<T> is true_type iff T is a plain function type (i.e. "Result(Args...)")
+ */
+template<class T>
+struct is_function_type : std::false_type {};
+template<class Result, class... Args>
+struct is_function_type<Result (Args...)> : std::true_type {};
+template<class T> using is_function_type_t = typename is_function_type<T>::type;
+
+
+
+/**
+ * is_instantiation_of<T, I> is true_type iff I is a template instantiation of T (e.g. vector<int> is an instantiation of vector)
+ *  Example:
+ *    is_instantiation_of_t<vector, vector<int>> // true
+ *    is_instantiation_of_t<pair, pair<int, string>> // true
+ *    is_instantiation_of_t<vector, pair<int, string>> // false
+ */
+template <template <class...> class Template, class T>
+struct is_instantiation_of : std::false_type {};
+template <template <class...> class Template, class... Args>
+struct is_instantiation_of<Template, Template<Args...>> : std::true_type {};
+template<template<class...> class Template, class T> using is_instantiation_of_t = typename is_instantiation_of<Template, T>::type;
+
+
+
+/**
+ * is_type_condition<C> is true_type iff C<...> is a type trait representing a condition (i.e. has a constexpr static bool ::value member)
+ * Example:
+ *   is_type_condition<std::is_reference>  // true
+ */
+template<template<class> class C, class Enable = void>
+struct is_type_condition : std::false_type {};
+template<template<class> class C>
+struct is_type_condition<C, guts::enable_if_t<std::is_same<bool, guts::remove_cv_t<decltype(C<int>::value)>>::value>> : std::true_type {};
+
+}
+}