[libc++][TZDB] Fixes parsing interleaved rules. (#84808)

Typically the rules in the database are contiguous, but that is not a
requirement. This fixes the case when they are not.

---------

Co-authored-by: Louis Dionne <ldionne.2@gmail.com>

2 files changed, 47 insertions, 4 deletions

diff --git a/libcxx/src/tzdb.cpp b/libcxx/src/tzdb.cpp
index 2bb801e..0307f754 100644
--- a/libcxx/src/tzdb.cpp
+++ b/libcxx/src/tzdb.cpp
@@ -511,14 +511,33 @@ static string __parse_version(istream& __input) {
   return chrono::__parse_string(__input);
 }
 
+[[nodiscard]]
+static __tz::__rule& __create_entry(__tz::__rules_storage_type& __rules, const string& __name) {
+  auto __result = [&]() -> __tz::__rule& {
+    auto& __rule = __rules.emplace_back(__name, vector<__tz::__rule>{});
+    return __rule.second.emplace_back();
+  };
+
+  if (__rules.empty())
+    return __result();
+
+  // Typically rules are in contiguous order in the database.
+  // But there are exceptions, some rules are interleaved.
+  if (__rules.back().first == __name)
+    return __rules.back().second.emplace_back();
+
+  if (auto __it = ranges::find(__rules, __name, [](const auto& __r) { return __r.first; });
+      __it != ranges::end(__rules))
+    return __it->second.emplace_back();
+
+  return __result();
+}
+
 static void __parse_rule(tzdb& __tzdb, __tz::__rules_storage_type& __rules, istream& __input) {
   chrono::__skip_mandatory_whitespace(__input);
   string __name = chrono::__parse_string(__input);
 
-  if (__rules.empty() || __rules.back().first != __name)
-    __rules.emplace_back(__name, vector<__tz::__rule>{});
-
-  __tz::__rule& __rule = __rules.back().second.emplace_back();
+  __tz::__rule& __rule = __create_entry(__rules, __name);
 
   chrono::__skip_mandatory_whitespace(__input);
   __rule.__from = chrono::__parse_year(__input);
diff --git a/libcxx/test/libcxx/time/time.zone/time.zone.db/rules.pass.cpp b/libcxx/test/libcxx/time/time.zone/time.zone.db/rules.pass.cpp
index 5ae2ed1..4814f4a 100644
--- a/libcxx/test/libcxx/time/time.zone/time.zone.db/rules.pass.cpp
+++ b/libcxx/test/libcxx/time/time.zone/time.zone.db/rules.pass.cpp
@@ -550,6 +550,29 @@ R a 0 1 - Ja Su>=31 1w 2s abc
   assert(result.rules[0].second[2].__letters == "abc");
 }
 
+static void test_mixed_order() {
+  // This is a part of the real database. The interesting part is that the
+  // rules NZ and Chatham are interleaved. Make sure the parse algorithm
+  // handles this correctly.
+  parse_result result{
+      R"(
+# Since 1957 Chatham has been 45 minutes ahead of NZ, but until 2018a
+# there was no documented single notation for the date and time of this
+# transition.  Duplicate the Rule lines for now, to give the 2018a change
+# time to percolate out.
+Rule NZ  1974    only    -   Nov Sun>=1  2:00s   1:00    D
+Rule Chatham 1974    only    -   Nov Sun>=1  2:45s   1:00    -
+Rule NZ  1975    only    -   Feb lastSun 2:00s   0   S
+Rule Chatham 1975    only    -   Feb lastSun 2:45s   0   -
+Rule NZ  1975    1988    -   Oct lastSun 2:00s   1:00    D
+Rule Chatham 1975    1988    -   Oct lastSun 2:45s   1:00    -
+)"};
+
+  assert(result.rules.size() == 2);
+  assert(result.rules[0].second.size() == 3);
+  assert(result.rules[1].second.size() == 3);
+}
+
 int main(int, const char**) {
   test_invalid();
   test_name();
@@ -560,6 +583,7 @@ int main(int, const char**) {
   test_at();
   test_save();
   test_letter();
+  test_mixed_order();
 
   return 0;
 }