1 #!/usr/bin/env python 2 3 """ 4 Recurrence rule calculation. 5 6 Copyright (C) 2014 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 21 ---- 22 23 References: 24 25 RFC 5545: Internet Calendaring and Scheduling Core Object Specification 26 (iCalendar) 27 http://tools.ietf.org/html/rfc5545 28 29 ---- 30 31 FREQ defines the selection resolution. 32 DTSTART defines the start of the selection. 33 INTERVAL defines the step of the selection. 34 COUNT defines a number of instances; UNTIL defines a limit to the selection. 35 36 BY... qualifiers select instances within each outer selection instance according 37 to the recurrence of instances of the next highest resolution. For example, 38 BYDAY selects days in weeks. Thus, if no explicit week recurrence is indicated, 39 all weeks are selected within the selection of the next highest explicitly 40 specified resolution, whether this is months or years. 41 42 BYSETPOS in conjunction with BY... qualifiers permit the selection of specific 43 instances. 44 45 Within the FREQ resolution, BY... qualifiers refine selected instances. 46 47 Outside the FREQ resolution, BY... qualifiers select instances at the resolution 48 concerned. 49 50 Thus, FREQ and BY... qualifiers need to be ordered in terms of increasing 51 resolution (or decreasing scope). 52 """ 53 54 from calendar import monthrange 55 from datetime import date, datetime, timedelta 56 import operator 57 58 # Frequency levels, specified by FREQ in iCalendar. 59 60 freq_levels = ( 61 "YEARLY", 62 "MONTHLY", 63 "WEEKLY", 64 "DAILY", 65 "HOURLY", 66 "MINUTELY", 67 "SECONDLY" 68 ) 69 70 # Enumeration levels, employed by BY... qualifiers. 71 72 enum_levels = ( 73 None, 74 ("BYMONTH",), 75 ("BYWEEKNO",), 76 ("BYDAY", "BYMONTHDAY", "BYYEARDAY"), 77 ("BYHOUR",), 78 ("BYMINUTE",), 79 ("BYSECOND",) 80 ) 81 82 # Map from levels to lengths of datetime tuples. 83 84 lengths = [1, 2, 3, 3, 4, 5, 6] 85 positions = [l-1 for l in lengths] 86 87 # Map from qualifiers to interval units. Here, weeks are defined as 7 days. 88 89 units = {"WEEKLY" : 7} 90 91 # Make dictionaries mapping qualifiers to levels. 92 93 freq = dict([(level, i) for (i, level) in enumerate(freq_levels)]) 94 enum = dict([(level, i) for (i, levels) in enumerate(enum_levels) if levels for level in levels]) 95 96 # Functions for structuring the recurrences. 97 98 def get_next(it): 99 try: 100 return it.next() 101 except StopIteration: 102 return None 103 104 def order_qualifiers(qualifiers): 105 106 "Return the 'qualifiers' in order of increasing resolution." 107 108 l = [] 109 110 for qualifier, args in qualifiers: 111 if enum.has_key(qualifier): 112 level = enum[qualifier] 113 if special_enum_levels.has_key(qualifier): 114 args["interval"] = 1 115 selector = special_enum_levels[qualifier] 116 else: 117 selector = Enum 118 else: 119 level = freq[qualifier] 120 selector = Pattern 121 122 l.append(selector(level, args, qualifier)) 123 124 l.sort(key=lambda x: x.level) 125 return l 126 127 def get_datetime_structure(datetime): 128 129 "Return the structure of 'datetime' for recurrence production." 130 131 l = [] 132 offset = 0 133 for level, value in enumerate(datetime): 134 if level == 2: 135 offset = 1 136 l.append(Enum(level + offset, {"values" : [value]}, "DT")) 137 return l 138 139 def combine_datetime_with_qualifiers(datetime, qualifiers): 140 141 """ 142 Combine 'datetime' with 'qualifiers' to produce a structure for recurrence 143 production. 144 """ 145 146 iter_dt = iter(get_datetime_structure(datetime)) 147 iter_q = iter(order_qualifiers(qualifiers)) 148 149 l = [] 150 151 from_dt = get_next(iter_dt) 152 from_q = get_next(iter_q) 153 154 have_q = False 155 context = [] 156 context.append(from_dt.args["values"][0]) 157 158 # Consume from both lists, merging entries. 159 160 while from_dt and from_q: 161 _level = from_dt.level 162 level = from_q.level 163 164 # Datetime value at wider resolution. 165 166 if _level < level: 167 from_dt = get_next(iter_dt) 168 context.append(from_dt.args["values"][0]) 169 170 # Qualifier at wider or same resolution as datetime value. 171 172 else: 173 if not have_q: 174 if isinstance(from_q, Enum) and level > 0: 175 repeat = Pattern(level - 1, {"interval" : 1}, "REPEAT") 176 repeat.context = tuple(context) 177 l.append(repeat) 178 have_q = True 179 180 from_q.context = tuple(context) 181 l.append(from_q) 182 from_q = get_next(iter_q) 183 184 if _level == level: 185 from_dt = get_next(iter_dt) 186 context.append(from_dt.args["values"][0]) 187 188 # Complete the list. 189 190 while from_dt: 191 l.append(from_dt) 192 from_dt = get_next(iter_dt) 193 194 while from_q: 195 if not have_q: 196 if isinstance(from_q, Enum) and level > 0: 197 repeat = Pattern(level - 1, {"interval" : 1}, "REPEAT") 198 repeat.context = tuple(context) 199 l.append(repeat) 200 have_q = True 201 202 from_q.context = tuple(context) 203 l.append(from_q) 204 from_q = get_next(iter_q) 205 206 return l 207 208 # Datetime arithmetic. 209 210 def combine(t1, t2): 211 return tuple(map(lambda x, y: x or y, t1, t2)) 212 213 def scale(interval, pos): 214 return (0,) * pos + (interval,) 215 216 def get_seconds(t): 217 218 "Convert the sub-day part of 't' into seconds." 219 220 t = t + (0,) * (6 - len(t)) 221 return (t[3] * 60 + t[4]) * 60 + t[5] 222 223 def update(t, step): 224 225 "Update 't' by 'step' at the resolution of 'step'." 226 227 i = len(step) 228 229 # Years only. 230 231 if i == 1: 232 return (t[0] + step[0],) + tuple(t[1:]) 233 234 # Years and months. 235 236 elif i == 2: 237 month = t[1] + step[1] 238 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 239 240 # Dates and datetimes. 241 242 else: 243 updated_for_months = update(t, step[:2]) 244 245 # Dates only. 246 247 if i == 3: 248 d = datetime(*updated_for_months) 249 s = timedelta(step[2]) 250 251 # Datetimes. 252 253 else: 254 d = datetime(*updated_for_months) 255 s = timedelta(step[2], get_seconds(step)) 256 257 return to_tuple(d + s, len(t)) 258 259 def to_tuple(d, n): 260 return d.timetuple()[:n] 261 262 def get_first_day(first_day, weekday): 263 first_day = date(*first_day) 264 first_weekday = first_day.isoweekday() 265 if first_weekday > weekday: 266 return first_day + timedelta(7 - first_weekday + weekday) 267 else: 268 return first_day + timedelta(weekday - first_weekday) 269 270 def get_last_day(last_day, weekday): 271 last_day = date(*last_day) 272 last_weekday = last_day.isoweekday() 273 if last_weekday < weekday: 274 return last_day - timedelta(last_weekday + 7 - weekday) 275 else: 276 return last_day - timedelta(last_weekday - weekday) 277 278 # Classes for producing instances from recurrence structures. 279 280 class Selector: 281 def __init__(self, level, args, qualifier, selecting=None): 282 self.level = level 283 self.pos = positions[level] 284 self.args = args 285 self.qualifier = qualifier 286 self.context = () 287 self.selecting = selecting 288 289 def __repr__(self): 290 return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.level, self.args, self.qualifier, self.context) 291 292 def materialise(self, start, end, count=None): 293 counter = count and [0, count] 294 results = self.materialise_items(self.context, start, end, counter) 295 results.sort() 296 return results[:count] 297 298 def materialise_item(self, current, last, next, counter): 299 if counter is None or counter[0] < counter[1]: 300 if self.selecting: 301 return self.selecting.materialise_items(current, last, next, counter) 302 elif last <= current: 303 if counter is not None: 304 counter[0] += 1 305 return [current] 306 return [] 307 308 class Pattern(Selector): 309 def materialise_items(self, context, start, end, counter): 310 first = scale(self.context[self.pos], self.pos) 311 312 # Define the step between items. 313 314 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 315 step = scale(interval, self.pos) 316 317 # Define the scale of a single item. 318 319 unit_interval = units.get(self.qualifier, 1) 320 unit_step = scale(unit_interval, self.pos) 321 322 current = combine(context, first) 323 results = [] 324 325 while current < end and (counter is None or counter[0] < counter[1]): 326 next = update(current, step) 327 current_end = update(current, unit_step) 328 results += self.materialise_item(current, max(current, start), min(current_end, end), counter) 329 current = next 330 331 return results 332 333 class WeekDayFilter(Selector): 334 def materialise_items(self, context, start, end, counter): 335 step = scale(1, 2) 336 results = [] 337 338 # Get weekdays in the year. 339 340 if len(context) == 1: 341 first_day = (context[0], 1, 1) 342 last_day = (context[0], 12, 31) 343 344 # Get weekdays in the month. 345 346 elif len(context) == 2: 347 first_day = (context[0], context[1], 1) 348 last_day = update((context[0], context[1], 1), (0, 1, 0)) 349 last_day = update(last_day, (0, 0, -1)) 350 351 # Get weekdays in the week. 352 353 else: 354 current = context 355 values = [value for (value, index) in self.args["values"]] 356 357 while current < end and (counter is None or counter[0] < counter[1]): 358 next = update(current, step) 359 if date(*current).isoweekday() in values: 360 results += self.materialise_item(current, max(current, start), min(next, end), counter) 361 current = next 362 return results 363 364 # Find each of the given days. 365 366 for value, index in self.args["values"]: 367 if index is not None: 368 offset = timedelta(7 * (abs(index) - 1)) 369 370 if index < 0: 371 current = to_tuple(get_last_day(last_day, value) - offset, 3) 372 else: 373 current = to_tuple(get_first_day(first_day, value) + offset, 3) 374 375 if current < end: 376 next = update(current, step) 377 results += self.materialise_item(current, max(current, start), min(next, end), counter) 378 379 else: 380 if index < 0: 381 current = to_tuple(get_last_day(last_day, value), 3) 382 direction = operator.sub 383 else: 384 current = to_tuple(get_first_day(first_day, value), 3) 385 direction = operator.add 386 387 while first_day <= current <= last_day: 388 if current < end: 389 next = update(current, step) 390 results += self.materialise_item(current, max(current, start), min(next, end), counter) 391 current = to_tuple(direction(date(*current), timedelta(7)), 3) 392 393 return results 394 395 class Enum(Selector): 396 def materialise_items(self, context, start, end, counter): 397 step = scale(1, self.pos) 398 results = [] 399 for value in self.args["values"]: 400 current = combine(context, scale(value, self.pos)) 401 if current < end: 402 next = update(current, step) 403 results += self.materialise_item(current, max(current, start), min(next, end), counter) 404 return results 405 406 class MonthDayFilter(Enum): 407 def materialise_items(self, context, start, end, counter): 408 last_day = monthrange(context[0], context[1])[1] 409 step = scale(1, self.pos) 410 results = [] 411 for value in self.args["values"]: 412 if value < 0: 413 value = last_day + 1 + value 414 current = combine(context, scale(value, self.pos)) 415 if current < end: 416 next = update(current, step) 417 results += self.materialise_item(current, max(current, start), min(next, end), counter) 418 return results 419 420 class YearDayFilter(Enum): 421 def materialise_items(self, context, start, end, counter): 422 first_day = date(context[0], 1, 1) 423 next_first_day = date(context[0] + 1, 1, 1) 424 year_length = (next_first_day - first_day).days 425 step = scale(1, self.pos) 426 results = [] 427 for value in self.args["values"]: 428 if value < 0: 429 value = year_length + 1 + value 430 current = to_tuple(first_day + timedelta(value - 1), 3) 431 if current < end: 432 next = update(current, step) 433 results += self.materialise_item(current, max(current, start), min(next, end), counter) 434 return results 435 436 def process(selectors): 437 current = selectors[0] 438 for selector in selectors[1:]: 439 current.selecting = selector 440 current = selector 441 return selectors[0] 442 443 special_enum_levels = { 444 "BYDAY" : WeekDayFilter, 445 "BYMONTHDAY" : MonthDayFilter, 446 "BYYEARDAY" : YearDayFilter, 447 } 448 449 # vim: tabstop=4 expandtab shiftwidth=4