1//! Generating timespan sets from a built Table.
2//!
3//! Once a table has been fully built, it needs to be turned into several
4//! *fixed timespan sets*: a series of spans of time where the local time
5//! offset remains the same throughout. One set is generated for each named
6//! time zone. These timespan sets can then be iterated over to produce
7//! *transitions*: when the local time changes from one offset to another.
8//!
9//! These sets are returned as `FixedTimespanSet` values, rather than
10//! iterators, because the generation logic does not output the timespans
11//! in any particular order, meaning they need to be sorted before they’re
12//! returned—so we may as well just return the vector, rather than an
13//! iterator over the vector.
14//!
15//! Similarly, there is a fixed set of years that is iterated over
16//! (currently 1800..2100), rather than having an iterator that produces
17//! timespans indefinitely. Not only do we need a complete set of timespans
18//! for sorting, but it is not necessarily advisable to rely on offset
19//! changes so far into the future!
20//!
21//! ### Example
22//!
23//! The complete definition of the `Indian/Mauritius` time zone, as
24//! specified in the `africa` file in my version of the tz database, has
25//! two Zone definitions, one of which refers to four Rule definitions:
26//!
27//! ```tz
28//! # Rule NAME FROM TO TYPE IN ON AT SAVE LETTER/S
29//! Rule Mauritius 1982 only - Oct 10 0:00 1:00 S
30//! Rule Mauritius 1983 only - Mar 21 0:00 0 -
31//! Rule Mauritius 2008 only - Oct lastSun 2:00 1:00 S
32//! Rule Mauritius 2009 only - Mar lastSun 2:00 0 -
33//!
34//! # Zone NAME GMTOFF RULES FORMAT [UNTIL]
35//! Zone Indian/Mauritius 3:50:00 - LMT 1907 # Port Louis
36//! 4:00 Mauritius MU%sT # Mauritius Time
37//! ```
38//!
39//! To generate a fixed timespan set for this timezone, we examine each of the
40//! Zone definitions, generating at least one timespan for each definition.
41//!
42//! * The first timespan describes the *local mean time* (LMT) in Mauritius,
43//! calculated by the geographical position of Port Louis, its capital.
44//! Although it’s common to have a timespan set begin with a city’s local mean
45//! time, it is by no means necessary. This timespan has a fixed offset of
46//! three hours and fifty minutes ahead of UTC, and lasts until the beginning
47//! of 1907, at which point the second timespan kicks in.
48//! * The second timespan has no ‘until’ date, so it’s in effect indefinitely.
49//! Instead of having a fixed offset, it refers to the set of rules under the
50//! name “Mauritius”, which we’ll have to consult to compute the timespans.
51//! * The first two rules refer to a summer time transition that began on
52//! the 10th of October 1982, and lasted until the 21st of March 1983. But
53//! before we get onto that, we need to add a timespan beginning at the
54//! time the last one ended (1907), up until the point Summer Time kicks
55//! in (1982), reflecting that it was four hours ahead of UTC.
56//! * After this, we add another timespan for Summer Time, when Mauritius
57//! was an extra hour ahead, bringing the total offset for that time to
58//! *five* hours.
59//! * The next (and last) two rules refer to another summer time
60//! transition from the last Sunday of October 2008 to the last Sunday of
61//! March 2009, this time at 2am local time instead of midnight. But, as
62//! before, we need to add a *standard* time timespan beginning at the
63//! time Summer Time ended (1983) up until the point the next span of
64//! Summer Time kicks in (2008), again reflecting that it was four hours
65//! ahead of UTC again.
66//! * Next, we add the Summer Time timespan, again bringing the total
67//! offset to five hours. We need to calculate when the last Sundays of
68//! the months are to get the dates correct.
69//! * Finally, we add one last standard time timespan, lasting from 2009
70//! indefinitely, as the Mauritian authorities decided not to change to
71//! Summer Time again.
72//!
73//! All this calculation results in the following six timespans to be added:
74//!
75//! | Timespan start | Abbreviation | UTC offset | DST? |
76//! |:--------------------------|:-------------|:-------------------|:-----|
77//! | *no start* | LMT | 3 hours 50 minutes | No |
78//! | 1906-11-31 T 20:10:00 UTC | MUT | 4 hours | No |
79//! | 1982-09-09 T 20:00:00 UTC | MUST | 5 hours | Yes |
80//! | 1983-02-20 T 19:00:00 UTC | MUT | 4 hours | No |
81//! | 2008-09-25 T 22:00:00 UTC | MUST | 5 hours | Yes |
82//! | 2009-02-28 T 21:00:00 UTC | MUT | 4 hours | No |
83//!
84//! There are a few final things of note:
85//!
86//! Firstly, this library records the times that timespans *begin*, while
87//! the tz data files record the times that timespans *end*. Pay attention to
88//! this if the timestamps aren’t where you expect them to be! For example, in
89//! the data file, the first zone rule has an ‘until’ date and the second has
90//! none, whereas in the list of timespans, the last timespan has a ‘start’
91//! date and the *first* has none.
92//!
93//! Secondly, although local mean time in Mauritius lasted until 1907, the
94//! timespan is recorded as ending in 1906! Why is this? It’s because the
95//! transition occurred at midnight *at the local time*, which in this case,
96//! was three hours fifty minutes ahead of UTC. So that time has to be
97//! *subtracted* from the date, resulting in twenty hours and ten minutes on
98//! the last day of the year. Similar things happen on the rest of the
99//! transitions, being either four or five hours ahead of UTC.
100//!
101//! The logic in this file is based off of `zic.c`, which comes with the
102//! zoneinfo files and is in the public domain.
103
104use crate::table::{RuleInfo, Saving, Table, ZoneInfo};
105
106/// A set of timespans, separated by the instances at which the timespans
107/// change over. There will always be one more timespan than transitions.
108///
109/// This mimics the `FixedTimespanSet` struct in `datetime::cal::zone`,
110/// except it uses owned `Vec`s instead of slices.
111#[derive(PartialEq, Debug, Clone)]
112pub struct FixedTimespanSet {
113 /// The first timespan, which is assumed to have been in effect up until
114 /// the initial transition instant (if any). Each set has to have at
115 /// least one timespan.
116 pub first: FixedTimespan,
117
118 /// The rest of the timespans, as a vector of tuples, each containing:
119 ///
120 /// 1. A transition instant at which the previous timespan ends and the
121 /// next one begins, stored as a Unix timestamp;
122 /// 2. The actual timespan to transition into.
123 pub rest: Vec<(i64, FixedTimespan)>,
124}
125
126/// An individual timespan with a fixed offset.
127///
128/// This mimics the `FixedTimespan` struct in `datetime::cal::zone`, except
129/// instead of “total offset” and “is DST” fields, it has separate UTC and
130/// DST fields. Also, the name is an owned `String` here instead of a slice.
131#[derive(PartialEq, Debug, Clone)]
132pub struct FixedTimespan {
133 /// The number of seconds offset from UTC during this timespan.
134 pub utc_offset: i64,
135
136 /// The number of *extra* daylight-saving seconds during this timespan.
137 pub dst_offset: i64,
138
139 /// The abbreviation in use during this timespan.
140 pub name: String,
141}
142
143impl FixedTimespan {
144 /// The total offset in effect during this timespan.
145 pub fn total_offset(&self) -> i64 {
146 self.utc_offset + self.dst_offset
147 }
148}
149
150/// Trait to put the `timespans` method on Tables.
151pub trait TableTransitions {
152 /// Computes a fixed timespan set for the timezone with the given name.
153 /// Returns `None` if the table doesn’t contain a time zone with that name.
154 fn timespans(&self, zone_name: &str) -> Option<FixedTimespanSet>;
155}
156
157impl TableTransitions for Table {
158 fn timespans(&self, zone_name: &str) -> Option<FixedTimespanSet> {
159 let mut builder = FixedTimespanSetBuilder::default();
160
161 let zoneset = match self.get_zoneset(zone_name) {
162 Some(zones) => zones,
163 None => return None,
164 };
165
166 for (i, zone_info) in zoneset.iter().enumerate() {
167 let mut dst_offset = 0;
168 let use_until = i != zoneset.len() - 1;
169 let utc_offset = zone_info.offset;
170
171 let mut insert_start_transition = i > 0;
172 let mut start_zone_id = None;
173 let mut start_utc_offset = zone_info.offset;
174 let mut start_dst_offset = 0;
175
176 match zone_info.saving {
177 Saving::NoSaving => {
178 builder.add_fixed_saving(
179 zone_info,
180 0,
181 &mut dst_offset,
182 utc_offset,
183 &mut insert_start_transition,
184 &mut start_zone_id,
185 );
186 }
187
188 Saving::OneOff(amount) => {
189 builder.add_fixed_saving(
190 zone_info,
191 amount,
192 &mut dst_offset,
193 utc_offset,
194 &mut insert_start_transition,
195 &mut start_zone_id,
196 );
197 }
198
199 Saving::Multiple(ref rules) => {
200 let rules = &self.rulesets[rules];
201 builder.add_multiple_saving(
202 zone_info,
203 rules,
204 &mut dst_offset,
205 use_until,
206 utc_offset,
207 &mut insert_start_transition,
208 &mut start_zone_id,
209 &mut start_utc_offset,
210 &mut start_dst_offset,
211 );
212 }
213 }
214
215 if insert_start_transition && start_zone_id.is_some() {
216 let t = (
217 builder.start_time.expect("Start time"),
218 FixedTimespan {
219 utc_offset: start_utc_offset,
220 dst_offset: start_dst_offset,
221 name: start_zone_id.clone().expect("Start zone ID"),
222 },
223 );
224 builder.rest.push(t);
225 }
226
227 if use_until {
228 builder.start_time = Some(
229 zone_info.end_time.expect("End time").to_timestamp() - utc_offset - dst_offset,
230 );
231 }
232 }
233
234 Some(builder.build())
235 }
236}
237
238#[derive(Debug, Default)]
239struct FixedTimespanSetBuilder {
240 first: Option<FixedTimespan>,
241 rest: Vec<(i64, FixedTimespan)>,
242
243 start_time: Option<i64>,
244 until_time: Option<i64>,
245}
246
247impl FixedTimespanSetBuilder {
248 fn add_fixed_saving(
249 &mut self,
250 timespan: &ZoneInfo,
251 amount: i64,
252 dst_offset: &mut i64,
253 utc_offset: i64,
254 insert_start_transition: &mut bool,
255 start_zone_id: &mut Option<String>,
256 ) {
257 *dst_offset = amount;
258 *start_zone_id = Some(timespan.format.format(*dst_offset, None));
259
260 if *insert_start_transition {
261 let time = self.start_time.unwrap();
262 let timespan = FixedTimespan {
263 utc_offset: timespan.offset,
264 dst_offset: *dst_offset,
265 name: start_zone_id.clone().unwrap_or_default(),
266 };
267
268 self.rest.push((time, timespan));
269 *insert_start_transition = false;
270 } else {
271 self.first = Some(FixedTimespan {
272 utc_offset,
273 dst_offset: *dst_offset,
274 name: start_zone_id.clone().unwrap_or_default(),
275 });
276 }
277 }
278
279 #[allow(unused_results)]
280 #[allow(clippy::too_many_arguments)]
281 fn add_multiple_saving(
282 &mut self,
283 timespan: &ZoneInfo,
284 rules: &[RuleInfo],
285 dst_offset: &mut i64,
286 use_until: bool,
287 utc_offset: i64,
288 insert_start_transition: &mut bool,
289 start_zone_id: &mut Option<String>,
290 start_utc_offset: &mut i64,
291 start_dst_offset: &mut i64,
292 ) {
293 use std::mem::replace;
294
295 for year in 1800..2100 {
296 if use_until && year > timespan.end_time.unwrap().year() {
297 break;
298 }
299
300 let mut activated_rules = rules
301 .iter()
302 .filter(|r| r.applies_to_year(year))
303 .collect::<Vec<_>>();
304
305 loop {
306 if use_until {
307 self.until_time =
308 Some(timespan.end_time.unwrap().to_timestamp() - utc_offset - *dst_offset);
309 }
310
311 // Find the minimum rule and its start time based on the current
312 // UTC and DST offsets.
313 let earliest = activated_rules
314 .iter()
315 .enumerate()
316 .map(|(i, r)| (i, r.absolute_datetime(year, utc_offset, *dst_offset)))
317 .min_by_key(|&(_, time)| time);
318
319 let (pos, earliest_at) = match earliest {
320 Some((pos, time)) => (pos, time),
321 None => break,
322 };
323
324 let earliest_rule = activated_rules.remove(pos);
325
326 if use_until && earliest_at >= self.until_time.unwrap() {
327 break;
328 }
329
330 *dst_offset = earliest_rule.time_to_add;
331
332 if *insert_start_transition && earliest_at == self.start_time.unwrap() {
333 *insert_start_transition = false;
334 }
335
336 if *insert_start_transition {
337 if earliest_at < self.start_time.unwrap() {
338 let _ = replace(start_utc_offset, timespan.offset);
339 let _ = replace(start_dst_offset, *dst_offset);
340 let _ = replace(
341 start_zone_id,
342 Some(
343 timespan
344 .format
345 .format(*dst_offset, earliest_rule.letters.as_ref()),
346 ),
347 );
348 continue;
349 }
350
351 if start_zone_id.is_none()
352 && *start_utc_offset + *start_dst_offset == timespan.offset + *dst_offset
353 {
354 let _ = replace(
355 start_zone_id,
356 Some(
357 timespan
358 .format
359 .format(*dst_offset, earliest_rule.letters.as_ref()),
360 ),
361 );
362 }
363 }
364
365 let t = (
366 earliest_at,
367 FixedTimespan {
368 utc_offset: timespan.offset,
369 dst_offset: earliest_rule.time_to_add,
370 name: timespan
371 .format
372 .format(earliest_rule.time_to_add, earliest_rule.letters.as_ref()),
373 },
374 );
375 self.rest.push(t);
376 }
377 }
378 }
379
380 fn build(mut self) -> FixedTimespanSet {
381 self.rest.sort_by(|a, b| a.0.cmp(&b.0));
382
383 let first = match self.first {
384 Some(ft) => ft,
385 None => self
386 .rest
387 .iter()
388 .find(|t| t.1.dst_offset == 0)
389 .unwrap()
390 .1
391 .clone(),
392 };
393
394 let mut zoneset = FixedTimespanSet {
395 first,
396 rest: self.rest,
397 };
398 optimise(&mut zoneset);
399 zoneset
400 }
401}
402
403#[allow(unused_results)] // for remove
404fn optimise(transitions: &mut FixedTimespanSet) {
405 let mut from_i = 0;
406 let mut to_i = 0;
407
408 while from_i < transitions.rest.len() {
409 if to_i > 1 {
410 let from = transitions.rest[from_i].0;
411 let to = transitions.rest[to_i - 1].0;
412 if from + transitions.rest[to_i - 1].1.total_offset()
413 <= to + transitions.rest[to_i - 2].1.total_offset()
414 {
415 transitions.rest[to_i - 1].1 = transitions.rest[from_i].1.clone();
416 from_i += 1;
417 continue;
418 }
419 }
420
421 if to_i == 0 || transitions.rest[to_i - 1].1 != transitions.rest[from_i].1 {
422 transitions.rest[to_i] = transitions.rest[from_i].clone();
423 to_i += 1;
424 }
425
426 from_i += 1
427 }
428
429 transitions.rest.truncate(to_i);
430
431 if !transitions.rest.is_empty() && transitions.first == transitions.rest[0].1 {
432 transitions.rest.remove(0);
433 }
434}
435
436#[cfg(test)]
437mod test {
438 use super::optimise;
439 use super::*;
440
441 // Allow unused results in test code, because the only ‘results’ that
442 // we need to ignore are the ones from inserting and removing from
443 // tables and vectors. And as we set them up ourselves, they’re bound
444 // to be correct, otherwise the tests would fail!
445 #[test]
446 #[allow(unused_results)]
447 fn optimise_macquarie() {
448 let mut transitions = FixedTimespanSet {
449 first: FixedTimespan {
450 utc_offset: 0,
451 dst_offset: 0,
452 name: "zzz".to_owned(),
453 },
454 rest: vec![
455 (
456 -2_214_259_200,
457 FixedTimespan {
458 utc_offset: 36000,
459 dst_offset: 0,
460 name: "AEST".to_owned(),
461 },
462 ),
463 (
464 -1_680_508_800,
465 FixedTimespan {
466 utc_offset: 36000,
467 dst_offset: 3600,
468 name: "AEDT".to_owned(),
469 },
470 ),
471 (
472 -1_669_892_400,
473 FixedTimespan {
474 utc_offset: 36000,
475 dst_offset: 3600,
476 name: "AEDT".to_owned(),
477 },
478 ), // gets removed
479 (
480 -1_665_392_400,
481 FixedTimespan {
482 utc_offset: 36000,
483 dst_offset: 0,
484 name: "AEST".to_owned(),
485 },
486 ),
487 (
488 -1_601_719_200,
489 FixedTimespan {
490 utc_offset: 0,
491 dst_offset: 0,
492 name: "zzz".to_owned(),
493 },
494 ),
495 (
496 -687_052_800,
497 FixedTimespan {
498 utc_offset: 36000,
499 dst_offset: 0,
500 name: "AEST".to_owned(),
501 },
502 ),
503 (
504 -94_730_400,
505 FixedTimespan {
506 utc_offset: 36000,
507 dst_offset: 0,
508 name: "AEST".to_owned(),
509 },
510 ), // also gets removed
511 (
512 -71_136_000,
513 FixedTimespan {
514 utc_offset: 36000,
515 dst_offset: 3600,
516 name: "AEDT".to_owned(),
517 },
518 ),
519 (
520 -55_411_200,
521 FixedTimespan {
522 utc_offset: 36000,
523 dst_offset: 0,
524 name: "AEST".to_owned(),
525 },
526 ),
527 (
528 -37_267_200,
529 FixedTimespan {
530 utc_offset: 36000,
531 dst_offset: 3600,
532 name: "AEDT".to_owned(),
533 },
534 ),
535 (
536 -25_776_000,
537 FixedTimespan {
538 utc_offset: 36000,
539 dst_offset: 0,
540 name: "AEST".to_owned(),
541 },
542 ),
543 (
544 -5_817_600,
545 FixedTimespan {
546 utc_offset: 36000,
547 dst_offset: 3600,
548 name: "AEDT".to_owned(),
549 },
550 ),
551 ],
552 };
553
554 let mut result = transitions.clone();
555 result.rest.remove(6);
556 result.rest.remove(2);
557
558 optimise(&mut transitions);
559 assert_eq!(transitions, result);
560 }
561}
562