1//! Determining the structure of a set of ruleset names.
2//!
3//! The names of time zones in the zoneinfo database are of the form
4//! `Area/Location`, or more rarely, `Area/Location/Sublocation`. This means
5//! they form a hierarchy, with each level either serving as a time zone
6//! itself (usually a location) or as a parent of multiple other entries
7//! (usually an area).
8//!
9//! When generating Rust code containing the timezone data, we need to
10//! generate the entire tree structure, not just the leaves of actual timezone
11//! data. This module determines that structure, allowing it to be created
12//! before any actual timezone data is written.
13//!
14//! For example, say we have the following subset of time zone entries:
15//!
16//! - America/Antigua
17//! - America/Araguaina
18//! - America/Argentina/Buenos_Aires
19//! - America/Argentina/Catamarca
20//! - America/Argentina/Cordoba
21//! - America/Aruba
22//!
23//! On top of the six actual time zone files, we would need to create the following:
24//!
25//! - An America module that has three private submodules (Antigua, Araguaína,
26//! and Aruba) and one public submodule (Argentina);
27//! - An America/Argentina submodule that has there private submodules (Buenos
28//! Aires, Catamarca, Cordoba).
29//!
30//! This module contains an iterator that finds all parent zonesets, and
31//! sorts them so they’re output in a correct order.
32
33use std::collections::{BTreeMap, BTreeSet};
34
35use crate::table::Table;
36
37/// Trait to put the `structure` method on Tables.
38pub trait Structure {
39 /// Returns an iterator over the structure of this table.
40 fn structure(&self) -> TableStructure;
41}
42
43impl Structure for Table {
44 fn structure(&self) -> TableStructure {
45 let mut mappings = BTreeMap::new();
46
47 for key in self.zonesets.keys().chain(self.links.keys()) {
48 // Extract the name from the *last* slash. So
49 // `America/Kentucky/Louisville` is split into
50 // `America/Kentucky` and `Louisville` components.
51 let last_slash = match key.rfind('/') {
52 Some(pos) => pos,
53 None => continue,
54 };
55
56 // Split the string around the slash, which gets removed.
57 let parent = &key[..last_slash];
58 {
59 let set = mappings.entry(parent).or_insert_with(BTreeSet::new);
60 set.insert(Child::TimeZone(&key[last_slash + 1..]));
61 }
62
63 // If the *parent* name still has a slash in it, then this is
64 // a time zone of the form `America/Kentucky/Louisville`. We
65 // need to make sure that `America` now has a `Kentucky`
66 // child, too.
67 if let Some(first_slash) = parent.find('/') {
68 let grandparent = &parent[..first_slash];
69 let set = mappings.entry(grandparent).or_insert_with(BTreeSet::new);
70 set.insert(Child::Submodule(&parent[first_slash + 1..]));
71 }
72 }
73
74 TableStructure { mappings }
75 }
76}
77
78/// The structure of a set of time zone names.
79#[derive(PartialEq, Debug)]
80pub struct TableStructure<'table> {
81 mappings: BTreeMap<&'table str, BTreeSet<Child<'table>>>,
82}
83
84impl<'table> IntoIterator for TableStructure<'table> {
85 type Item = TableStructureEntry<'table>;
86 type IntoIter = Iter<'table>;
87
88 fn into_iter(self) -> Self::IntoIter {
89 // It’s necessary to sort the keys before producing them, to
90 // ensure that (for example) `America` is produced before
91 // `America/Kentucky`.
92 let mut keys: Vec<_> = self.mappings.keys().cloned().collect();
93 keys.sort_by(|a: &&str, b: &&str| b.cmp(a));
94
95 Iter {
96 structure: self,
97 keys,
98 }
99 }
100}
101
102/// Iterator over sorted entries in a `TableStructure`.
103#[derive(PartialEq, Debug)]
104pub struct Iter<'table> {
105 structure: TableStructure<'table>,
106 keys: Vec<&'table str>,
107}
108
109impl<'table> Iterator for Iter<'table> {
110 type Item = TableStructureEntry<'table>;
111
112 fn next(&mut self) -> Option<Self::Item> {
113 let key: &'table str = self.keys.pop()?;
114
115 // Move the strings out into an (automatically-sorted) vector.
116 let values: Vec> = self.structure.mappings[key].iter().cloned().collect();
117
118 Some(TableStructureEntry {
119 name: key,
120 children: values,
121 })
122 }
123}
124
125/// An entry returned from a `TableStructure` iterator.
126#[derive(PartialEq, Debug)]
127pub struct TableStructureEntry<'table> {
128 /// This entry’s name, which *can* still include slashes.
129 pub name: &'table str,
130
131 /// A vector of sorted child names, which should have no slashes in.
132 pub children: Vec<Child<'table>>,
133}
134
135/// A child module that needs to be created.
136///
137/// The order here is important for `PartialOrd`: submodules need to be
138/// created before actual time zones, as directories need to be created
139/// before the files in them can be written.
140#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Copy, Clone)]
141pub enum Child<'table> {
142 /// A module containing **only** submodules, no time zones.
143 Submodule(&'table str),
144
145 /// A module containing **only** the details of a time zone.
146 TimeZone(&'table str),
147}
148
149#[cfg(test)]
150#[allow(unused_results)]
151mod test {
152 use super::*;
153 use crate::table::Table;
154
155 #[test]
156 fn empty() {
157 let table = Table::default();
158 let mut structure = table.structure().into_iter();
159 assert_eq!(structure.next(), None);
160 }
161
162 #[test]
163 fn separate() {
164 let mut table = Table::default();
165 table.zonesets.insert("a".to_owned(), Vec::new());
166 table.zonesets.insert("b".to_owned(), Vec::new());
167 table.zonesets.insert("c".to_owned(), Vec::new());
168
169 let mut structure = table.structure().into_iter();
170 assert_eq!(structure.next(), None);
171 }
172
173 #[test]
174 fn child() {
175 let mut table = Table::default();
176 table.zonesets.insert("a/b".to_owned(), Vec::new());
177
178 let mut structure = table.structure().into_iter();
179 assert_eq!(
180 structure.next(),
181 Some(TableStructureEntry {
182 name: "a",
183 children: vec![Child::TimeZone("b")]
184 })
185 );
186 assert_eq!(structure.next(), None);
187 }
188
189 #[test]
190 fn hierarchy() {
191 let mut table = Table::default();
192 table.zonesets.insert("a/b/c".to_owned(), Vec::new());
193 table.zonesets.insert("a/b/d".to_owned(), Vec::new());
194 table.zonesets.insert("a/e".to_owned(), Vec::new());
195
196 let mut structure = table.structure().into_iter();
197 assert_eq!(
198 structure.next(),
199 Some(TableStructureEntry {
200 name: "a",
201 children: vec![Child::Submodule("b"), Child::TimeZone("e")]
202 })
203 );
204 assert_eq!(
205 structure.next(),
206 Some(TableStructureEntry {
207 name: "a/b",
208 children: vec![Child::TimeZone("c"), Child::TimeZone("d")]
209 })
210 );
211 assert_eq!(structure.next(), None);
212 }
213}
214