Function: icalendar-recur-refine-byyearday

icalendar-recur-refine-byyearday is a byte-compiled function defined in icalendar-recur.el.gz.

Signature

(icalendar-recur-refine-byyearday INTERVAL YEARDAYS &optional VTIMEZONE)

Documentation

Resolve INTERVAL into a list of subintervals matching YEARDAYS.

YEARDAYS should be a list of values from a recurrence rule's BYYEARDAY=... clause; see icalendar-recur for the possible values.

Source Code

;; Defined in /usr/src/emacs/lisp/calendar/icalendar-recur.el.gz
;; Refining intervals into subintervals
;;
;; For a given interval, the various BY*=... clauses in a recurrence
;; rule specify the recurrences in that interval.
;;
;; RFC5545 unfortunately has an overly-complicated conceptual model for
;; how recurrences are to be calculated which is based on "expanding" or
;; "limiting" the recurrence set for each successive clause.  This model
;; is difficult to think about and implement, and the text of the
;; standard is ambiguous.  I did not succeed in producing a working
;; implementation based on the description in the standard, and the
;; existing implementations don't seem to agree on how it's to be
;; implemented anyway.
;;
;; Fortunately, RFC8984 (JSCalendar) is a forthcoming standard which
;; attempts to resolve the ambiguities while being semantically
;; backward-compatible with RFC5545.  It provides a much cleaner
;; conceptual model: the recurrence set is generated by starting with a
;; list of candidates, which consist of every second in (what is here
;; called) an interval, and then filtering out any candidates which do
;; not match the rule's clauses.  The most straightforward implementation
;; of this model, however, is unusably slow in typical cases.  Consider
;; for example the case of calculating the onset of daylight savings
;; time in a given year: the interval is a year long, so it consists of
;; over 31 million seconds.  Although it's easy to generate Lisp
;; timestamps for each of those seconds, filtering them through the
;; various BY* clauses means decoding each of those timestamps, which
;; means doing a fairly expensive computation over 31 million times, and
;; then throwing away the result in all but one case.  When I implemented
;; this model, I was not patient enough to sit through the calculations
;; for even MONTHLY rules (which on my laptop took minutes).
;;
;; So instead of implementing RFC8984's model directly, the strategy
;; here is to do something equivalent but much more efficient: rather
;; than thinking of an interval as consisting of a set of successive
;; seconds, we think of it as described by its bounds; and for each BY*
;; clause, we *refine* the interval into subintervals by computing the
;; bounds of each subinterval corresponding to the value(s) in that
;; clause.  For example, in a YEARLY rule, the initial interval is one
;; year long, say all of 2025.  If it has a "BYMONTH=4,10" clause, then
;; we refine this interval into two subintervals, each one month long:
;; one for April 2025 and one for October 2025.  This is much more
;; efficient in the typical case, because the number of bounds which
;; describe the final set of subintervals is usually *much* smaller than
;; the number of seconds in the original interval.
;;
;; The following functions are responsible for computing these
;; refinements.  The main entry point here is
;; `icalendar-recur-refine-from-clauses', which takes care of
;; successively refining the interval both by the explicit values in the
;; rule's clauses and by the implicit values in DTSTART.  (There, too,
;; RFC8984 is helpful: it gives a much more explicit description of how
;; the information in DTSTART interacts with the BY* clauses to further
;; refine the subintervals.)

(defun icr:refine-byyearday (interval yeardays &optional vtimezone)
  "Resolve INTERVAL into a list of subintervals matching YEARDAYS.

YEARDAYS should be a list of values from a recurrence rule's
BYYEARDAY=... clause; see `icalendar-recur' for the possible values."
  (let* ((sorted-ydays (sort yeardays
                             :key (lambda (a) (if (< 0 a) a (+ 366 a)))))
         (interval-start (icr:interval-low interval))
         (curr-year (decoded-time-year interval-start))
         (interval-end (icr:interval-high interval))
         (end-year (decoded-time-year interval-end))
         (subintervals nil))
    (while curr-year
      ;; For each year in the interval...
      (dolist (n sorted-ydays)
        ;; ...the subinterval is one day long on the nth yearday
        (let* ((nthday (calendar-date-from-day-of-year curr-year n))
               (low (ical:make-date-time :year curr-year
                                         :month (calendar-extract-month nthday)
                                         :day (calendar-extract-day nthday)
                                         :hour 0 :minute 0 :second 0
                                         :tz vtimezone))
               (high (ical:date/time-add low :day 1 vtimezone)))
          ;; "Clip" the subinterval bounds if they fall outside the
          ;; interval.  Careful!  This clipping can lead to high <= low,
          ;; so need to check it is still the case that low < high
          ;; before pushing the subinterval
          (when (ical:date/time< low interval-start)
            (setq low interval-start))
          (when (ical:date/time< interval-end high)
            (setq high interval-end))
          (when (and (ical:date-time<= interval-start low)
                     (ical:date-time< low high)
                     (ical:date-time<= high interval-end))
            (push (icr:make-interval low high) subintervals))))
      (setq curr-year (1+ curr-year))
      (when (<= end-year curr-year)
        ;; we're done:
        (setq curr-year nil)))
    (nreverse subintervals)))