From 7f1c88139c2b906982cb036f39bfa80db122c7af Mon Sep 17 00:00:00 2001
From: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
Date: Wed, 4 Sep 2024 12:57:51 +0200
Subject: [PATCH] libstdc++: hashing support for chrono value classes (P2592R2)

This commit implements [time.hash], added by P2592 for C++26.
The implementation of the various hash specializations is
mostly straightforward:

* duration hashes its representation (not the period);
* time_point hashes its duration;
* the calendaring classes (year, month, day, etc.) hash their
  values;
* zoned_time hashes the time zone pointer and its time point.

There are however a couple of challenges:

* The noexcept specifications for hashing duration, time_point,
  zoned_time are slightly more convoluted than expected, as
  their getters are noexcept(false) (e.g. calling count() on a
  duration will copy the representation and that may throw);

* [time.duration] says that "Rep shall be an arithmetic type or a
  class emulating an arithmetic type". Technically speaking, this
  means that `const int` is a valid Rep; but we can't use
  hash<const int>.

  I'm not sure if this is deliberate or not (cf. LWG951, LWG953),
  but I've decided to support it nonetheless.

* zoned_time and the calendar classes that combine several
  parts (e.g. month_day) need a hash combiner. The one
  available in _Hash_impl works on objects representations,
  not values, and given the nature of the calendar classes
  I'm very afraid that I may accidentally be hashing padding
  bits. Therefore, I've added a helper convenience combiner.

libstdc++-v3/ChangeLog:

	* include/bits/functional_hash.h: Add a convenience hash
	  combiner.
	* include/bits/version.def: Bump the feature-testing macro.
	* include/bits/version.h: Regenerate.
	* include/std/chrono: Add std::hash specializations for the
	  value classes in namespace chrono.
	* testsuite/std/time/hash.cc: New test.

Signed-off-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
---
 libstdc++-v3/include/bits/functional_hash.h |  31 ++
 libstdc++-v3/include/bits/version.def       |   6 +
 libstdc++-v3/include/bits/version.h         |   7 +-
 libstdc++-v3/include/std/chrono             | 299 ++++++++++++++++++++
 libstdc++-v3/testsuite/std/time/hash.cc     | 225 +++++++++++++++
 5 files changed, 567 insertions(+), 1 deletion(-)
 create mode 100644 libstdc++-v3/testsuite/std/time/hash.cc

diff --git a/libstdc++-v3/include/bits/functional_hash.h b/libstdc++-v3/include/bits/functional_hash.h
index 3626ebe816b..c0f82601b4b 100644
--- a/libstdc++-v3/include/bits/functional_hash.h
+++ b/libstdc++-v3/include/bits/functional_hash.h
@@ -235,6 +235,37 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       { return hash(&__val, sizeof(__val), __hash); }
   };
 
+#if __cplusplus >= 201103L // C++11
+  // A convenience hash combiner
+  struct _Hash_combiner
+  {
+    static void __hash_combine(size_t&) {}
+
+    template<typename _Arg, typename... _Args>
+      static void
+      __hash_combine(size_t& __result,
+		     const _Arg& __arg,
+		     const _Args&... __args)
+      {
+	const size_t __arg_hash = hash<_Arg>{}(__arg);
+	__result = _Hash_impl::__hash_combine(__arg_hash, __result);
+	__hash_combine(__result, __args...);
+      }
+
+    static size_t __hash()
+      { return 0; }
+
+    template<typename _Arg, typename... _Args>
+      static size_t __hash(const _Arg& __arg, const _Args&... __args)
+      {
+	const size_t __arg_hash = hash<_Arg>{}(__arg);
+	size_t __result = _Hash_impl::hash(__arg_hash);
+	__hash_combine(__result, __args...);
+	return __result;
+      }
+  };
+#endif // C++11
+
   /// Specialization for float.
   template<>
     struct hash<float> : public __hash_base<size_t, float>
diff --git a/libstdc++-v3/include/bits/version.def b/libstdc++-v3/include/bits/version.def
index 59b028c44af..2a2bbf54b3f 100644
--- a/libstdc++-v3/include/bits/version.def
+++ b/libstdc++-v3/include/bits/version.def
@@ -575,6 +575,12 @@ ftms = {
 
 ftms = {
   name = chrono;
+  values = {
+    v = 202306;
+    cxxmin = 26;
+    hosted = yes;
+    cxx11abi = yes;
+  };
   values = {
     v = 201907;
     cxxmin = 20;
diff --git a/libstdc++-v3/include/bits/version.h b/libstdc++-v3/include/bits/version.h
index e465131d99b..c75cb009ada 100644
--- a/libstdc++-v3/include/bits/version.h
+++ b/libstdc++-v3/include/bits/version.h
@@ -644,7 +644,12 @@
 #undef __glibcxx_want_boyer_moore_searcher
 
 #if !defined(__cpp_lib_chrono)
-# if (__cplusplus >= 202002L) && _GLIBCXX_USE_CXX11_ABI && _GLIBCXX_HOSTED
+# if (__cplusplus >  202302L) && _GLIBCXX_USE_CXX11_ABI && _GLIBCXX_HOSTED
+#  define __glibcxx_chrono 202306L
+#  if defined(__glibcxx_want_all) || defined(__glibcxx_want_chrono)
+#   define __cpp_lib_chrono 202306L
+#  endif
+# elif (__cplusplus >= 202002L) && _GLIBCXX_USE_CXX11_ABI && _GLIBCXX_HOSTED
 #  define __glibcxx_chrono 201907L
 #  if defined(__glibcxx_want_all) || defined(__glibcxx_want_chrono)
 #   define __cpp_lib_chrono 201907L
diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
index 7ffa5360728..8c6b173bc5d 100644
--- a/libstdc++-v3/include/std/chrono
+++ b/libstdc++-v3/include/std/chrono
@@ -50,6 +50,10 @@
 # include <bits/unique_ptr.h>
 #endif
 
+#if __cplusplus > 202302L
+# include <bits/functional_hash.h>
+#endif
+
 #define __glibcxx_want_chrono
 #define __glibcxx_want_chrono_udls
 #include <bits/version.h>
@@ -3329,6 +3333,301 @@ namespace __detail
 #endif // C++20
   } // namespace chrono
 
+#if __glibcxx_chrono >= 202306 // C++26
+  // Hash support [time.hash]
+
+  // duration
+  template<typename _Rep, typename _Period,
+	   typename _ActualRep = remove_cv_t<_Rep>,
+	   bool = __poison_hash<_ActualRep>::__enable_hash_call>
+    struct __chrono_duration_hash_base
+    {
+      size_t
+      operator()(const chrono::duration<_Rep, _Period>& __val) const
+      noexcept(
+	is_nothrow_copy_constructible_v<_Rep> &&
+	noexcept(hash<_ActualRep>{}(std::declval<_Rep>()))
+      )
+      {
+	return hash<_ActualRep>{}(__val.count());
+      }
+    };
+
+  template<typename _Rep, typename _Period, typename _ActualRep>
+    struct __chrono_duration_hash_base<_Rep, _Period, _ActualRep, false>
+    {};
+
+  template<typename _Rep, typename _Period>
+    struct hash<chrono::duration<_Rep, _Period>>
+    : private __poison_hash<remove_cv_t<_Rep>>,
+      public __chrono_duration_hash_base<_Rep, _Period>
+    {
+      using result_type [[__deprecated__]] = size_t;
+      using argument_type [[__deprecated__]] = chrono::duration<_Rep, _Period>;
+    };
+
+  template<typename _Rep, typename _Period>
+    struct __is_fast_hash<hash<chrono::duration<_Rep, _Period>>>
+    : __is_fast_hash<hash<_Rep>>
+    {};
+
+  // time_point
+  template<typename _Clock, typename _Dur,
+	   bool = __poison_hash<_Dur>::__enable_hash_call>
+    struct __chrono_time_point_hash_base
+    {
+      size_t
+      operator()(const chrono::time_point<_Clock, _Dur>& __val) const
+      noexcept(
+	is_nothrow_copy_constructible_v<_Dur> &&
+	noexcept(hash<_Dur>{}(std::declval<_Dur>()))
+      )
+      {
+	return hash<_Dur>{}(__val.time_since_epoch());
+      }
+    };
+
+  template<typename _Clock, typename _Dur>
+    struct __chrono_time_point_hash_base<_Clock, _Dur, false>
+    {};
+
+  template<typename _Clock, typename _Dur>
+    struct hash<chrono::time_point<_Clock, _Dur>>
+    : private __poison_hash<_Dur>,
+      public __chrono_time_point_hash_base<_Clock, _Dur>
+    {
+      using result_type [[__deprecated__]] = size_t;
+      using argument_type [[__deprecated__]] = chrono::time_point<_Clock, _Dur>;
+    };
+
+  template<typename _Clock, typename _Dur>
+    struct __is_fast_hash<hash<chrono::time_point<_Clock, _Dur>>>
+    : __is_fast_hash<hash<_Dur>>
+    {};
+
+  // day
+  template<>
+    struct hash<chrono::day>
+    : public __hash_base<size_t, chrono::day>
+    {
+      size_t operator()(chrono::day __val) const noexcept
+      { return static_cast<unsigned>(__val); }
+    };
+
+  // month
+  template<>
+    struct hash<chrono::month>
+    : public __hash_base<size_t, chrono::month>
+    {
+      size_t operator()(chrono::month __val) const noexcept
+      { return static_cast<unsigned>(__val); }
+    };
+
+  // year
+  template<>
+    struct hash<chrono::year>
+    : public __hash_base<size_t, chrono::year>
+    {
+      size_t operator()(chrono::year __val) const noexcept
+      {
+	const int __tmp = static_cast<int>(__val);
+	return static_cast<size_t>(__tmp);
+      }
+    };
+
+  // weekday
+  template<>
+    struct hash<chrono::weekday>
+    : public __hash_base<size_t, chrono::weekday>
+    {
+      size_t operator()(chrono::weekday __val) const noexcept
+      { return static_cast<size_t>(__val.c_encoding()); }
+    };
+
+  // weekday_indexed
+  template<>
+    struct hash<chrono::weekday_indexed>
+    : public __hash_base<size_t, chrono::weekday_indexed>
+    {
+      size_t operator()(chrono::weekday_indexed __val) const noexcept
+      {
+	return _Hash_combiner::__hash(__val.weekday(), __val.index());
+      }
+    };
+
+  // weekday_last
+  template<>
+    struct hash<chrono::weekday_last>
+    : public __hash_base<size_t, chrono::weekday_last>
+    {
+      size_t operator()(chrono::weekday_last __val) const noexcept
+      { return static_cast<size_t>(__val.weekday().c_encoding()); }
+    };
+
+  // month_day
+  template<>
+    struct hash<chrono::month_day>
+    : public __hash_base<size_t, chrono::month_day>
+    {
+      size_t operator()(chrono::month_day __val) const noexcept
+      {
+	return _Hash_combiner::__hash(__val.month(), __val.day());
+      }
+    };
+
+  // month_day_last
+  template<>
+    struct hash<chrono::month_day_last>
+    : public __hash_base<size_t, chrono::month_day_last>
+    {
+      size_t operator()(chrono::month_day_last __val) const noexcept
+      { return static_cast<unsigned>(__val.month()); }
+    };
+
+  // month_weekday
+  template<>
+    struct hash<chrono::month_weekday>
+    : public __hash_base<size_t, chrono::month_weekday>
+    {
+      size_t operator()(chrono::month_weekday __val) const noexcept
+      {
+	return _Hash_combiner::__hash(__val.month(), __val.weekday_indexed());
+      }
+    };
+
+  // month_weekday_last
+  template<>
+    struct hash<chrono::month_weekday_last>
+    : public __hash_base<size_t, chrono::month_weekday_last>
+    {
+      size_t
+      operator()(chrono::month_weekday_last __val) const noexcept
+      {
+	return _Hash_combiner::__hash(__val.month(), __val.weekday_last());
+      }
+    };
+
+  // year_month
+  template<>
+    struct hash<chrono::year_month>
+    : public __hash_base<size_t, chrono::year_month>
+    {
+      size_t operator()(chrono::year_month __val) const noexcept
+      {
+	return _Hash_combiner::__hash(__val.year(), __val.month());
+      }
+    };
+
+  // year_month_day
+  template<>
+    struct hash<chrono::year_month_day>
+    : public __hash_base<size_t, chrono::year_month_day>
+    {
+      size_t operator()(chrono::year_month_day __val) const noexcept
+      {
+	return _Hash_combiner::__hash(__val.year(),
+	                              __val.month(),
+	                              __val.day());
+      }
+    };
+
+  // year_month_day_last
+  template<>
+    struct hash<chrono::year_month_day_last>
+    : public __hash_base<size_t, chrono::year_month_day_last>
+    {
+      size_t
+      operator()(chrono::year_month_day_last __val) const noexcept
+      {
+	return _Hash_combiner::__hash(__val.year(),
+	                              __val.month_day_last());
+      }
+    };
+
+  // year_month_weekday
+  template<>
+    struct hash<chrono::year_month_weekday>
+    : public __hash_base<size_t, chrono::year_month_weekday>
+    {
+      size_t operator()(chrono::year_month_weekday __val) const noexcept
+      {
+	return _Hash_combiner::__hash(__val.year(),
+	                              __val.month(),
+	                              __val.weekday_indexed());
+      }
+    };
+
+  // year_month_weekday_last
+  template<>
+    struct hash<chrono::year_month_weekday_last>
+    : public __hash_base<size_t, chrono::year_month_weekday_last>
+    {
+      size_t
+      operator()(chrono::year_month_weekday_last __val) const noexcept
+      {
+	return _Hash_combiner::__hash(__val.year(),
+	                            __val.month(),
+	                            __val.weekday_last());
+      }
+    };
+
+  // zoned_time
+  template<typename _Duration, typename _TimeZonePtr,
+	   typename _ActualDuration =
+	     typename chrono::zoned_time<_Duration, _TimeZonePtr>::duration,
+	   bool = (__poison_hash<_ActualDuration>::__enable_hash_call &&
+		   __poison_hash<_TimeZonePtr>::__enable_hash_call)>
+    struct __chrono_zoned_time_hash_base
+    {
+      size_t
+      operator()
+      (const chrono::zoned_time<_Duration, _TimeZonePtr>& __val)
+      const
+      noexcept(
+	is_nothrow_copy_constructible_v<_ActualDuration> &&
+	noexcept(hash<_ActualDuration>{}(std::declval<_ActualDuration>())) &&
+	is_nothrow_copy_constructible_v<_TimeZonePtr> &&
+	noexcept(hash<_TimeZonePtr>{}(std::declval<_TimeZonePtr>()))
+      )
+      {
+	return _Hash_combiner::__hash(__val.get_sys_time(),
+	                              __val.get_time_zone());
+      }
+    };
+
+  template<typename _Duration, typename _TimeZonePtr,
+	   typename _ActualDuration>
+    struct __chrono_zoned_time_hash_base
+	<_Duration, _TimeZonePtr, _ActualDuration, false>
+    {};
+
+  template<typename _Duration, typename _TimeZonePtr>
+    struct hash<chrono::zoned_time<_Duration, _TimeZonePtr>>
+    : private __poison_hash<_Duration>,
+      private __poison_hash<_TimeZonePtr>,
+      public __chrono_zoned_time_hash_base<_Duration, _TimeZonePtr>
+    {
+      using result_type [[__deprecated__]] = size_t;
+      using argument_type [[__deprecated__]] =
+	chrono::zoned_time<_Duration, _TimeZonePtr>;
+    };
+
+  template<typename _Duration, typename _TimeZonePtr>
+    struct __is_fast_hash<hash<chrono::zoned_time<_Duration, _TimeZonePtr>>>
+    : bool_constant<__is_fast_hash<hash<_Duration>>::value &&
+	            __is_fast_hash<hash<_TimeZonePtr>>::value>
+    {};
+
+  // leap_second
+  template<>
+    struct hash<chrono::leap_second>
+    : public __hash_base<size_t, chrono::leap_second>
+    {
+      size_t operator()(chrono::leap_second __val) const noexcept
+      { return hash<chrono::seconds>{}(__val.value()); }
+    };
+#endif // __glibcxx_chrono >= 202306
+
 #if __cplusplus >= 202002L
   inline namespace literals
   {
diff --git a/libstdc++-v3/testsuite/std/time/hash.cc b/libstdc++-v3/testsuite/std/time/hash.cc
new file mode 100644
index 00000000000..bbc7699bf68
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/time/hash.cc
@@ -0,0 +1,225 @@
+// { dg-do run { target c++26 } }
+// { dg-require-effective-target tzdb }
+
+#include <chrono>
+#include <unordered_set>
+#include <limits.h>
+#include <testsuite_hooks.h>
+
+#if !defined(__cpp_lib_chrono)
+#error "__cpp_lib_chrono not defined"
+#elif __cpp_lib_chrono < 202306L
+#error "Wrong value for __cpp_lib_chrono"
+#endif
+
+template <typename T>
+struct arithmetic_wrapper
+{
+  arithmetic_wrapper() = default;
+  arithmetic_wrapper(T t) : t(t) {}
+  friend bool operator==(arithmetic_wrapper, arithmetic_wrapper) = default;
+  T t;
+};
+
+template <typename T>
+struct std::hash<arithmetic_wrapper<T>>
+{
+  size_t operator()(arithmetic_wrapper<T> val) const noexcept
+  { return std::hash<T>{}(val.t); }
+};
+
+template <typename T>
+void test_unordered_set(const T& t)
+{
+  std::unordered_set<T> set;
+
+  set.insert(t);
+  VERIFY(set.size() == 1);
+  VERIFY(set.contains(t));
+
+  set.erase(t);
+  VERIFY(set.size() == 0);
+  VERIFY(!set.contains(t));
+}
+
+template <typename T>
+void test_hash(const T& t)
+{
+  static_assert(noexcept(std::hash<T>{}(t)));
+  test_unordered_set(t);
+}
+
+void test01()
+{
+  using namespace std::chrono;
+  using namespace std::literals::chrono_literals;
+
+  // duration
+  test_hash(-999s);
+  test_hash(1234ms);
+  test_hash(duration<double>(123.45));
+  using AWint = arithmetic_wrapper<int>;
+  test_hash(duration<AWint>(AWint(1234)));
+  using AWdouble = arithmetic_wrapper<double>;
+  test_hash(duration<AWdouble>(AWdouble(123.45)));
+
+  // time_point
+  test_hash(sys_seconds(1234s));
+  test_hash(sys_time<duration<double>>(duration<double>(123.45)));
+  test_hash(utc_seconds(1234s));
+  test_hash(local_days(days(1234)));
+  test_hash(system_clock::now());
+  test_hash(steady_clock::now());
+  test_hash(utc_clock::now());
+  test_hash(gps_clock::now());
+
+  // day
+  test_hash(1d);
+  test_hash(0d);
+  test_hash(255d);
+  test_hash(1234d);
+  test_hash(day(UINT_MAX));
+
+  // month
+  test_hash(January);
+  test_hash(September);
+  test_hash(month(0u));
+  test_hash(month(255u));
+  test_hash(month(1234u));
+  test_hash(month(UINT_MAX));
+
+  // year
+  test_hash(2024y);
+  test_hash(0y);
+  test_hash(year::min());
+  test_hash(year::max());
+  test_hash(year(INT_MAX));
+  test_hash(year(INT_MIN));
+
+  // weekday
+  test_hash(Monday);
+  test_hash(Thursday);
+  test_hash(weekday(255u));
+  test_hash(weekday(UINT_MAX));
+
+  // weekday_indexed
+  test_hash(Monday[0u]);
+  test_hash(Monday[7u]);
+  test_hash(Monday[1234u]);
+  test_hash(weekday(1234u)[0u]);
+
+  // weekday_last
+  test_hash(Monday[last]);
+  test_hash(Friday[last]);
+  test_hash(weekday(1234u)[last]);
+
+  // month_day
+  test_hash(March / 3);
+  test_hash(March / 31);
+  test_hash(February / 31);
+  test_hash(February / 1234);
+  test_hash(month(1234u) / 1);
+
+  // month_day_last
+  test_hash(March / last);
+  test_hash(month(1234u) / last);
+
+  // month_weekday
+  test_hash(March / Tuesday[2u]);
+  test_hash(month(1234u) / Tuesday[2u]);
+  test_hash(March / weekday(1234u)[2u]);
+  test_hash(March / Tuesday[1234u]);
+
+  // month_weekday_last
+  test_hash(April / Sunday[last]);
+  test_hash(month(1234u) / Tuesday[last]);
+  test_hash(April / weekday(1234u)[last]);
+
+  // year_month
+  test_hash(2024y / August);
+  test_hash(1'000'000y / August);
+  test_hash(2024y / month(1234u));
+
+  // year_month_day
+  test_hash(2024y / August / 31);
+  test_hash(-10y / March / 5);
+  test_hash(2024y / February / 31);
+  test_hash(1'000'000y / March / 5);
+  test_hash(2024y / month(1234u) / 5);
+  test_hash(2024y / March / 1234);
+
+  // year_month_day_last
+  test_hash(2024y / August / last);
+  test_hash(1'000'000y / August / last);
+  test_hash(2024y / month(1234u) / last);
+
+  // year_month_weekday
+  test_hash(2024y / August / Tuesday[2u]);
+  test_hash(-10y / August / Tuesday[2u]);
+  test_hash(1'000'000y / August / Tuesday[2u]);
+  test_hash(2024y / month(1234u) / Tuesday[2u]);
+  test_hash(2024y / August / weekday(1234u)[2u]);
+  test_hash(2024y / August / Tuesday[1234u]);
+
+  // year_month_weekday_last
+  test_hash(2024y / August / Tuesday[last]);
+  test_hash(-10y / August / Tuesday[last]);
+  test_hash(1'000'000y / August / Tuesday[last]);
+  test_hash(2024y / month(1234u) / Tuesday[last]);
+  test_hash(2024y / August / weekday(1234u)[last]);
+
+  // zoned_time
+  test_hash(zoned_seconds("Europe/Rome", sys_seconds(1234s)));
+  test_hash(zoned_time("Europe/Rome", system_clock::now()));
+
+  // leap_second
+  for (leap_second l : get_tzdb().leap_seconds)
+    test_hash(l);
+}
+
+void test02()
+{
+  using namespace std::chrono;
+  using namespace std::literals::chrono_literals;
+
+  {
+    std::unordered_set<milliseconds> set;
+    set.insert(2000ms);
+    VERIFY(set.contains(2000ms));
+    VERIFY(set.contains(2s));
+    VERIFY(!set.contains(1234ms));
+    VERIFY(!set.contains(1234s));
+  }
+  {
+    using TP = sys_time<milliseconds>;
+    std::unordered_set<TP> set;
+    set.insert(TP(2000ms));
+    VERIFY(set.contains(TP(2000ms)));
+    VERIFY(set.contains(sys_seconds(2s)));
+    VERIFY(!set.contains(TP(1234ms)));
+    VERIFY(!set.contains(sys_seconds(1234s)));
+  }
+}
+
+void test03()
+{
+  using namespace std::chrono;
+
+  const auto test = []<typename T>(const T& t)
+  {
+    static_assert(noexcept(std::hash<T>{}(t)));
+  };
+
+  test(duration<const int>(123));
+  test(duration<const int, std::ratio<1, 1000>>(123));
+  test(duration<const int, std::ratio<1000, 1>>(123));
+  test(duration<const volatile double>(123.456));
+  test(duration<const arithmetic_wrapper<int>>(arithmetic_wrapper<int>(123)));
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+}
-- 
2.34.1

