Handling Time Zone in Scheme (4): Rule Conversion

Previously we have discussed timezone handling in a series of posts:

1. motivation and overview
2. parsing zoneinfo database
3. calculating offsets

To continue from the third post where we are in the midst of calculating daylight saving offsets, we have figured out the applicable rules, and we now need to convert them into date structs so we can determine the exact boundary.

Going back to our two rule examples for America/Los_Angeles:

  (2007 +inf.0 - 3 (match 0 >= 8) (2 0 0 w) 3600 "D")
  (2007 +inf.0 - 11 (match 0 >= 1) (2 0 0 w) 0 "S")

We want to convert them into the applicable values (for both 2009 and the previous year - 2008):

2009/3/8 02:00:00-08:00 
2009/11/1 02:00:00-07:00
2008/3/9 02:00:00-08:00 
2008/11/2 02:00:00-07:00 

In order to do so, we'll first have to be able to convert the ON (day of the month) into the correct date value, and then we'll have to convert the AT (time of the date) into the correct time value. Let's get started.

Day of the Month

The simplest ON format is a day number (ranging from 1-31), and for that we do not have to do too much. But there are also two other formats that are based on weekdays:

'(last 0) ;; => last sunday (sunday = 0, monday = 1 ..., saturday = 6) 
'(match 0 >= 5) ;; => sunday on or after 5th 
'(match 2 <= 10) ;; => tuesday on or before 10th 

That means we need to be able to convert them to the appropriate day of the month based on the year and the month.

Doomsday Algorithm and Weekday Calculation

To be able to calculate the weekday-based date values, we first need to be able to calculate the weekday of a particular date. For that we can make use of the doomsday algorithm, which are based on the concept that there is a doomsday every month, and they are easy to remember based on a moniker (4/4, 6/6, 8/8, 10/10, 12/12, ...). The linked explanation makes it sounds more complicated than it actually is - below is the oneline doomsday algorithm in scheme:

(define (doomsday y)
  (modulo (+ 2 (floor (+ y (/ y 4) (- (/ y 100)) (/ y 400)))) 7))

Then with doomsday we can calculate the weekday of a date:

(define (leap-year? year)
  ;; every 4 year is a leap year
  (or (and (= (modulo year 4) 0)
           ;; unless it's divisble by 100 
           (not (= (modulo year 100) 0)))
       ;; but if it's divisible by 400 then we'll be fine.
      (= (modulo year 400) 0)))

(define (week-day d)
  (modulo (+ (doomsday (date-year d)) (year-day d)
             (if (leap-year? (date-year d)) -3 -2)) 7))

Then to figure out the weekday on or greater than a particular date, we just need to do the following:

1. figure out the weekday of the date
2. figure out the difference between the weekday of the date and the weekday of your choice
3. add the differences to the date

The following figures out the difference between 2 weekdays

(define (week-day-diff to from)
  (modulo (- to from) 7))

And assuming we have a date+ that takes in a date and a number as the days to add, then the following will determine the date on or after a particular date by weekday:

(define (week-day>=? year month wday mday) 
  (define (helper date)
    (date+ date (week-day-diff wday (week-day date))))
  (helper (build-date year month mday)))

The other combinations (week-day>?, week-day<=?, and week-day<?) are left as exercises.

To determine the last (or nth) weekday of the month, we can employ a similar algorithm:

1. figure out the weekday of the first of the month
2. figure out the difference between that weekday and the weekday of your choice
3. add the number of weeks on top of the date to get the desired date
4. if the date exceeds the month, subtract a week to get to the last weekday within the month boundary

The following accomplish the above:

(define (nth-week-day year month wday nth)
  ;; the way to do so is to figure out the weekday for the first of the month, and then work toward 
  ;; the nth wday 
  (define (date-helper date)
    (if (not (= (date-month date) month))
        (date+ date -7)
        date))
  (define (helper date)
    (date-helper 
     (date+ date 
            (+ (week-day-diff wday (week-day date)) 
               (* (sub1 (case nth
                          ((first) 1)
                          ((last) 5)
                          (else nth))) 
                  7)))))
  (helper (build-date year month 1)))

With the above, we can now finally convert the ON field into the correct date value:

(define (on/year->date rule year) 
  (match (rule-date rule) 
    ((? integer? date)
     (build-date year (rule-month rule) date))
    ((list 'last (? number? wday))
     (nth-weekday year (rule-month rule) wday 'last)) 
    ((list 'match (? number? wday) (? symbol? test) (? number? day))
     ((case test 
        ((>=) week-day>=?)
        ((>) week-day>?)
        ((<=) week-day<=?)
        ((<) week-day<?)) year (rule-month rule) wday day))))

Determining "Wall Clock" Time

We are almost able to convert an applicable rule into a date object, but we first still have to fully convert the AT field into the corresponding time of the day value.

Unfortunately, AT field holds more than just a representation of hour:minute:seconds. It also holds the type of the clock, which can be one of the following:

• universal time - no offsets
• standard time - time-zone offsets only; no daylight saving offsets
• "wall clock" time - time-zone offsets + daylight saving offsets

The first two are straight forward - universal time has an offset of 0, and the standard time has the default offsets that we should pass in from the zone. But the "wall clock" time is more complicated. It basically means we need to know what the previous rule is at the moment of the rule coming into effect, since at the moment of daylight saving transition, the previous rules would have been effecting the wall clock.

Yes - it means that in order for us to arrive at the correct wall-clock time, we need to figure out the previous rule's offsets.

Serendipitously, we have already generated the previous-year's applicable rules. But since the previous year's rules also depend on its own previous year's rules, we will need to calculate the dates 2-years-prior to ensure we get the wall clock time correctly for the previous year (we can drop the 2-years-prior from the final consideration once they aid in calculating the offsets).

(define (applicable-rules date rules)
  ... 
  (let ((year (date-year date))) 
    (append (by-year year rules)
            (by-year (sub1 year) rules) 
            (by-year (- year 2) rules))))

Let's first convert a single rule/year pair to be a date, based on the previous applicable rule:

(define (rule/year->date rule year prev-rule std-offset) 
  (let ((date (on/year->date rule year)))
    (match (rule-time rule) 
      ((list hour minute second type) ;; wall clock 
       (build-date (date-year date)
                   (date-month date)
                   (date-day date)
                   hour 
                   minute
                   second 
                   #:tz (case type 
                          ((g u z) 0 0)
                          ((s) std-offset)
                          (else ;; wall-clock requires the previous rule...  
                           (+ std-offset (rule-offset prev-rule)))))))))

Then we will sort the rule/year pairs according to their precedence, and then call rule/year->date by passing in the rules and the previous rules.

(define (rule/year>? r/y1 r/y2) 
  (define (date-helper r1 r2 year) 
    (date>? (on/year->date r1 year) (on/year->date r2 year)))
  (define (month-helper r1 r2 year)
    (cond ((> (rule-month r1) (rule-month r2)) #t)
          ((= (rule-month r1) (rule-month r2))
           (date-helper r1 r2 year)) 
          (else #f))) 
  (let ((r1 (car r/y1)) 
        (y1 (cdr r/y1))
        (r2 (car r/y2))
        (y2 (cdr r/y2))) 
    (cond ((> y1 y2) #t)
          ((= y1 y2) 
           (month-helper r1 r2 y1)) 
          (else #f))))

(define (rule/years->date/offsets rule/years std-offset) 
  (define (helper rest acc)
    (cond ((null? rest) (reverse acc)) 
          ((null? (cdr rest)) ;; we have the last one... 
           (reverse acc)) 
          (else ;; we'll 
           (helper (cdr rest)
                   (cons (cons (rule/year->date (caar rest) (cdar rest) (caadr rest) std-offset)
                               (rule-offset (caar rest)))
                         acc)))))
  (helper (sort rule/years rule/year>?)
          '()))

With rule/years->date/offsets we finally were able to map rules into an ordered pairs of date boundaries and offsets that we can use to determine the correct offset:

(define (tz-rules-offset date rules std-offset) 
  (define (helper date/offsets)
    (cond ((null? date/offsets) 0) 
          ((date>? date (caar date/offsets)) 
           (cdar date/offsets))
          (else
           (helper (cdr date/offsets)))))
  (helper (rule/years->date/offsets (applicable-rules date rules) std-offset)))

And tz-daylight-saving-offset needs to be updated accordingly since tz-rules-offset now requires an additional std-offset:

(define (tz-daylight-saving-offset date zone-name)
  (define (until/rules-helper until offset rules)
    (define (until->date year month day hour minute second type)
      (date->seconds (build-date year month day hour minute second #:tz offset)))
    (list (if (not until) 
              +inf.0
              (apply until->date until))
          rules
          offset))
  (define (match-until/rules-helper date u/r)
    (cond ((null? u/r) 
           (error 'tz-standard-offset "invalid zone ~a for date ~a" zone-name date))
          ((<= date (caar u/r))
           (let ((until/rules (car u/r)))
             (tz-rules-offset (seconds->date date) (cadr until/rules) 
                              (caddr until/rules)))) 
          (else
           (match-until/rules-helper date (cdr u/r)))))
  ...) 

Now we can combine the tz-daylight-saving-offset and tz-standard-offset to determine the actual offset for a particular date:

(define (tz-offset date tz)
  (+ (tz-standard-offset date tz)
     (tz-daylight-saving-offset date tz))) 

Now we can finally correctly calculate the actual offsets. Stay tuned.