[libc++][chrono] Adds tzdb_list implementation.

This is the first step to implement time zone support in libc++. This
adds the complete tzdb_list class and a minimal tzdb class. The tzdb
class only contains the version, which is used by reload_tzdb.

Next to these classes it contains documentation and build system support
needed for time zone support. The code depends on the IANA Time Zone
Database, which should be available on the platform used or provided by
the libc++ vendors.

The code is labeled as experimental since there will be ABI breaks
during development; the tzdb class needs to have the standard headers.

Implements parts of:
- P0355 Extending <chrono> to Calendars and Time Zones

Addresses:
- LWG3319 Properly reference specification of IANA time zone database

Reviewed By: #libc, ldionne

Differential Revision: https://reviews.llvm.org/D154282

3 files changed, 266 insertions, 0 deletions

diff --git a/libcxx/src/CMakeLists.txt b/libcxx/src/CMakeLists.txt
index daaa9df..e57fbf1 100644
--- a/libcxx/src/CMakeLists.txt
+++ b/libcxx/src/CMakeLists.txt
@@ -326,6 +326,13 @@ if (LIBCXX_PSTL_CPU_BACKEND STREQUAL "libdispatch")
     )
 endif()
 
+if (LIBCXX_ENABLE_LOCALIZATION AND LIBCXX_ENABLE_FILESYSTEM AND LIBCXX_ENABLE_TIME_ZONE_DATABASE)
+  list(APPEND LIBCXX_EXPERIMENTAL_SOURCES
+    tz.cpp
+    tzdb_list.cpp
+    )
+endif()
+
 add_library(cxx_experimental STATIC ${LIBCXX_EXPERIMENTAL_SOURCES})
 target_link_libraries(cxx_experimental PUBLIC cxx-headers)
 if (LIBCXX_ENABLE_SHARED)
diff --git a/libcxx/src/tz.cpp b/libcxx/src/tz.cpp
new file mode 100644
index 0000000..4425f0e
--- /dev/null
+++ b/libcxx/src/tz.cpp
@@ -0,0 +1,146 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// For information see https://libcxx.llvm.org/DesignDocs/TimeZone.html
+
+#include <chrono>
+#include <filesystem>
+#include <fstream>
+#include <stdexcept>
+#include <string>
+
+// Contains a parser for the IANA time zone data files.
+//
+// These files can be found at https://data.iana.org/time-zones/ and are in the
+// public domain. Information regarding the input can be found at
+// https://data.iana.org/time-zones/tz-how-to.html and
+// https://man7.org/linux/man-pages/man8/zic.8.html.
+//
+// As indicated at https://howardhinnant.github.io/date/tz.html#Installation
+// For Windows another file seems to be required
+// https://raw.githubusercontent.com/unicode-org/cldr/master/common/supplemental/windowsZones.xml
+// This file seems to contain the mapping of Windows time zone name to IANA
+// time zone names.
+//
+// However this article mentions another way to do the mapping on Windows
+// https://devblogs.microsoft.com/oldnewthing/20210527-00/?p=105255
+// This requires Windows 10 Version 1903, which was released in May of 2019
+// and considered end of life in December 2020
+// https://learn.microsoft.com/en-us/lifecycle/announcements/windows-10-1903-end-of-servicing
+//
+// TODO TZDB Implement the Windows mapping in tzdb::current_zone
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace chrono {
+
+// This function is weak so it can be overriden in the tests. The
+// declaration is in the test header test/support/test_tzdb.h
+_LIBCPP_WEAK string_view __libcpp_tzdb_directory() {
+#if defined(__linux__)
+  return "/usr/share/zoneinfo/";
+#else
+#  error "unknown path to the IANA Time Zone Database"
+#endif
+}
+
+[[nodiscard]] static bool __is_whitespace(int __c) { return __c == ' ' || __c == '\t'; }
+
+static void __skip_optional_whitespace(istream& __input) {
+  while (chrono::__is_whitespace(__input.peek()))
+    __input.get();
+}
+
+static void __skip_mandatory_whitespace(istream& __input) {
+  if (!chrono::__is_whitespace(__input.get()))
+    std::__throw_runtime_error("corrupt tzdb: expected whitespace");
+
+  chrono::__skip_optional_whitespace(__input);
+}
+
+static void __matches(istream& __input, char __expected) {
+  if (std::tolower(__input.get()) != __expected)
+    std::__throw_runtime_error((string("corrupt tzdb: expected character '") + __expected + '\'').c_str());
+}
+
+static void __matches(istream& __input, string_view __expected) {
+  for (auto __c : __expected)
+    if (std::tolower(__input.get()) != __c)
+      std::__throw_runtime_error((string("corrupt tzdb: expected string '") + string(__expected) + '\'').c_str());
+}
+
+[[nodiscard]] static string __parse_string(istream& __input) {
+  string __result;
+  while (true) {
+    int __c = __input.get();
+    switch (__c) {
+    case ' ':
+    case '\t':
+    case '\n':
+      __input.unget();
+      [[fallthrough]];
+    case istream::traits_type::eof():
+      if (__result.empty())
+        std::__throw_runtime_error("corrupt tzdb: expected a string");
+
+      return __result;
+
+    default:
+      __result.push_back(__c);
+    }
+  }
+}
+
+static string __parse_version(istream& __input) {
+  // The first line in tzdata.zi contains
+  //    # version YYYYw
+  // The parser expects this pattern
+  // #\s*version\s*\(.*)
+  // This part is not documented.
+  chrono::__matches(__input, '#');
+  chrono::__skip_optional_whitespace(__input);
+  chrono::__matches(__input, "version");
+  chrono::__skip_mandatory_whitespace(__input);
+  return chrono::__parse_string(__input);
+}
+
+static tzdb __make_tzdb() {
+  tzdb __result;
+
+  filesystem::path __root = chrono::__libcpp_tzdb_directory();
+  ifstream __tzdata{__root / "tzdata.zi"};
+
+  __result.version = chrono::__parse_version(__tzdata);
+  return __result;
+}
+
+//===----------------------------------------------------------------------===//
+//                           Public API
+//===----------------------------------------------------------------------===//
+
+_LIBCPP_NODISCARD_EXT _LIBCPP_AVAILABILITY_TZDB _LIBCPP_EXPORTED_FROM_ABI tzdb_list& get_tzdb_list() {
+  static tzdb_list __result{chrono::__make_tzdb()};
+  return __result;
+}
+
+_LIBCPP_AVAILABILITY_TZDB _LIBCPP_EXPORTED_FROM_ABI const tzdb& reload_tzdb() {
+  if (chrono::remote_version() == chrono::get_tzdb().version)
+    return chrono::get_tzdb();
+
+  return chrono::get_tzdb_list().__emplace_front(chrono::__make_tzdb());
+}
+
+_LIBCPP_NODISCARD_EXT _LIBCPP_AVAILABILITY_TZDB _LIBCPP_EXPORTED_FROM_ABI string remote_version() {
+  filesystem::path __root = chrono::__libcpp_tzdb_directory();
+  ifstream __tzdata{__root / "tzdata.zi"};
+  return chrono::__parse_version(__tzdata);
+}
+
+} // namespace chrono
+
+_LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/src/tzdb_list.cpp b/libcxx/src/tzdb_list.cpp
new file mode 100644
index 0000000..7eaaedc
--- /dev/null
+++ b/libcxx/src/tzdb_list.cpp
@@ -0,0 +1,113 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// For information see https://libcxx.llvm.org/DesignDocs/TimeZone.html
+
+#include <chrono>
+
+#include <__mutex/unique_lock.h>
+#include <forward_list>
+
+// When threads are not available the locking is not required.
+#ifndef _LIBCPP_HAS_NO_THREADS
+#  include <shared_mutex>
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace chrono {
+
+//===----------------------------------------------------------------------===//
+//                          Private API
+//===----------------------------------------------------------------------===//
+
+class tzdb_list::__impl {
+public:
+  explicit __impl(tzdb&& __tzdb) { __tzdb_.push_front(std::move(__tzdb)); }
+
+  using const_iterator = tzdb_list::const_iterator;
+
+  const tzdb& front() const noexcept {
+#ifndef _LIBCPP_HAS_NO_THREADS
+    shared_lock __lock{__mutex_};
+#endif
+    return __tzdb_.front();
+  }
+
+  const_iterator erase_after(const_iterator __p) {
+#ifndef _LIBCPP_HAS_NO_THREADS
+    unique_lock __lock{__mutex_};
+#endif
+    return __tzdb_.erase_after(__p);
+  }
+
+  tzdb& __emplace_front(tzdb&& __tzdb) {
+#ifndef _LIBCPP_HAS_NO_THREADS
+    unique_lock __lock{__mutex_};
+#endif
+    return __tzdb_.emplace_front(std::move(__tzdb));
+  }
+
+  const_iterator begin() const noexcept {
+#ifndef _LIBCPP_HAS_NO_THREADS
+    shared_lock __lock{__mutex_};
+#endif
+    return __tzdb_.begin();
+  }
+  const_iterator end() const noexcept {
+    //  forward_list<T>::end does not access the list, so no need to take a lock.
+    return __tzdb_.end();
+  }
+
+  const_iterator cbegin() const noexcept { return begin(); }
+  const_iterator cend() const noexcept { return end(); }
+
+private:
+#ifndef _LIBCPP_HAS_NO_THREADS
+  mutable shared_mutex __mutex_;
+#endif
+  forward_list<tzdb> __tzdb_;
+};
+
+//===----------------------------------------------------------------------===//
+//                           Public API
+//===----------------------------------------------------------------------===//
+
+_LIBCPP_EXPORTED_FROM_ABI tzdb_list::tzdb_list(tzdb&& __tzdb) : __impl_{new __impl(std::move(__tzdb))} {}
+
+_LIBCPP_EXPORTED_FROM_ABI tzdb_list::~tzdb_list() { delete __impl_; }
+
+_LIBCPP_NODISCARD_EXT _LIBCPP_EXPORTED_FROM_ABI const tzdb& tzdb_list::front() const noexcept {
+  return __impl_->front();
+}
+
+_LIBCPP_EXPORTED_FROM_ABI tzdb_list::const_iterator tzdb_list::erase_after(const_iterator __p) {
+  return __impl_->erase_after(__p);
+}
+
+_LIBCPP_EXPORTED_FROM_ABI tzdb& tzdb_list::__emplace_front(tzdb&& __tzdb) {
+  return __impl_->__emplace_front(std::move(__tzdb));
+}
+
+_LIBCPP_NODISCARD_EXT _LIBCPP_EXPORTED_FROM_ABI tzdb_list::const_iterator tzdb_list::begin() const noexcept {
+  return __impl_->begin();
+}
+_LIBCPP_NODISCARD_EXT _LIBCPP_EXPORTED_FROM_ABI tzdb_list::const_iterator tzdb_list::end() const noexcept {
+  return __impl_->end();
+}
+
+_LIBCPP_NODISCARD_EXT _LIBCPP_EXPORTED_FROM_ABI tzdb_list::const_iterator tzdb_list::cbegin() const noexcept {
+  return __impl_->cbegin();
+}
+_LIBCPP_NODISCARD_EXT _LIBCPP_EXPORTED_FROM_ABI tzdb_list::const_iterator tzdb_list::cend() const noexcept {
+  return __impl_->cend();
+}
+
+} // namespace chrono
+
+_LIBCPP_END_NAMESPACE_STD