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 None, 65 None, 66 "DAILY", 67 "HOURLY", 68 "MINUTELY", 69 "SECONDLY" 70 ) 71 72 # Enumeration levels, employed by BY... qualifiers. 73 74 enum_levels = ( 75 None, 76 "BYMONTH", 77 "BYWEEKNO", 78 "BYYEARDAY", 79 "BYMONTHDAY", 80 "BYDAY", 81 "BYHOUR", 82 "BYMINUTE", 83 "BYSECOND" 84 ) 85 86 # Map from levels to lengths of datetime tuples. 87 88 lengths = [1, 2, 3, 3, 3, 3, 4, 5, 6] 89 positions = [l-1 for l in lengths] 90 91 # Map from qualifiers to interval units. Here, weeks are defined as 7 days. 92 93 units = {"WEEKLY" : 7} 94 95 # Make dictionaries mapping qualifiers to levels. 96 97 freq = dict([(level, i) for (i, level) in enumerate(freq_levels) if level]) 98 enum = dict([(level, i) for (i, level) in enumerate(enum_levels) if level]) 99 weekdays = dict([(weekday, i+1) for (i, weekday) in enumerate(["MO", "TU", "WE", "TH", "FR", "SA", "SU"])]) 100 101 # Functions for structuring the recurrences. 102 103 def get_next(it): 104 try: 105 return it.next() 106 except StopIteration: 107 return None 108 109 def get_parameters(values): 110 111 "Return parameters from the given list of 'values'." 112 113 d = {} 114 for value in values: 115 parts = value.split("=", 1) 116 if len(parts) < 2: 117 continue 118 key, value = parts 119 if key in ("COUNT", "BYSETPOS"): 120 d[key] = int(value) 121 return d 122 123 def get_qualifiers(values): 124 125 """ 126 Process the list of 'values' of the form "key=value", returning a list of 127 qualifiers. 128 """ 129 130 qualifiers = [] 131 frequency = None 132 interval = 1 133 134 for value in values: 135 parts = value.split("=", 1) 136 if len(parts) < 2: 137 continue 138 key, value = parts 139 if key == "FREQ" and freq.has_key(value): 140 qualifier = frequency = (value, {}) 141 elif key == "INTERVAL": 142 interval = int(value) 143 continue 144 elif enum.has_key(key): 145 qualifier = (key, {"values" : get_qualifier_values(key, value)}) 146 else: 147 continue 148 149 qualifiers.append(qualifier) 150 151 if frequency: 152 frequency[1]["interval"] = interval 153 154 return qualifiers 155 156 def get_qualifier_values(qualifier, value): 157 158 """ 159 For the given 'qualifier', process the 'value' string, returning a list of 160 suitable values. 161 """ 162 163 if qualifier != "BYDAY": 164 return map(int, value.split(",")) 165 166 values = [] 167 for part in value.split(","): 168 weekday = weekdays.get(part[-2:]) 169 if not weekday: 170 continue 171 index = part[:-2] 172 if index: 173 index = int(index) 174 else: 175 index = None 176 values.append((weekday, index)) 177 178 return values 179 180 def order_qualifiers(qualifiers): 181 182 "Return the 'qualifiers' in order of increasing resolution." 183 184 l = [] 185 186 for qualifier, args in qualifiers: 187 if enum.has_key(qualifier): 188 level = enum[qualifier] 189 if special_enum_levels.has_key(qualifier): 190 args["interval"] = 1 191 selector = special_enum_levels[qualifier] 192 else: 193 selector = Enum 194 else: 195 level = freq[qualifier] 196 selector = Pattern 197 198 l.append(selector(level, args, qualifier)) 199 200 l.sort(key=lambda x: x.level) 201 return l 202 203 def get_datetime_structure(datetime): 204 205 "Return the structure of 'datetime' for recurrence production." 206 207 l = [] 208 offset = 0 209 for level, value in enumerate(datetime): 210 if level == 2: 211 offset = 3 212 l.append(Enum(level + offset, {"values" : [value]}, "DT")) 213 return l 214 215 def combine_datetime_with_qualifiers(datetime, qualifiers): 216 217 """ 218 Combine 'datetime' with 'qualifiers' to produce a structure for recurrence 219 production. 220 """ 221 222 iter_dt = iter(get_datetime_structure(datetime)) 223 iter_q = iter(order_qualifiers(qualifiers)) 224 225 l = [] 226 227 from_dt = get_next(iter_dt) 228 from_q = get_next(iter_q) 229 230 have_q = False 231 context = [] 232 context.append(from_dt.args["values"][0]) 233 234 # Consume from both lists, merging entries. 235 236 while from_dt and from_q: 237 _level = from_dt.level 238 level = from_q.level 239 240 # Datetime value at wider resolution. 241 242 if _level < level: 243 from_dt = get_next(iter_dt) 244 context.append(from_dt.args["values"][0]) 245 246 # Qualifier at wider or same resolution as datetime value. 247 248 else: 249 if not have_q: 250 if isinstance(from_q, Enum) and level > 0: 251 repeat = Pattern(level - 1, {"interval" : 1}, None) 252 repeat.context = tuple(context) 253 l.append(repeat) 254 have_q = True 255 256 from_q.context = tuple(context) 257 l.append(from_q) 258 from_q = get_next(iter_q) 259 260 if _level == level: 261 from_dt = get_next(iter_dt) 262 context.append(from_dt.args["values"][0]) 263 264 # Complete the list. 265 266 while from_dt: 267 l.append(from_dt) 268 from_dt = get_next(iter_dt) 269 270 while from_q: 271 if not have_q: 272 if isinstance(from_q, Enum) and level > 0: 273 repeat = Pattern(level - 1, {"interval" : 1}, None) 274 repeat.context = tuple(context) 275 l.append(repeat) 276 have_q = True 277 278 from_q.context = tuple(context) 279 l.append(from_q) 280 from_q = get_next(iter_q) 281 282 return l 283 284 # Datetime arithmetic. 285 286 def combine(t1, t2): 287 return tuple(map(lambda x, y: x or y, t1, t2)) 288 289 def scale(interval, pos): 290 return (0,) * pos + (interval,) 291 292 def get_seconds(t): 293 294 "Convert the sub-day part of 't' into seconds." 295 296 t = t + (0,) * (6 - len(t)) 297 return (t[3] * 60 + t[4]) * 60 + t[5] 298 299 def update(t, step): 300 301 "Update 't' by 'step' at the resolution of 'step'." 302 303 i = len(step) 304 305 # Years only. 306 307 if i == 1: 308 return (t[0] + step[0],) + tuple(t[1:]) 309 310 # Years and months. 311 312 elif i == 2: 313 month = t[1] + step[1] 314 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 315 316 # Dates and datetimes. 317 318 else: 319 updated_for_months = update(t, step[:2]) 320 321 # Dates only. 322 323 if i == 3: 324 d = datetime(*updated_for_months) 325 s = timedelta(step[2]) 326 327 # Datetimes. 328 329 else: 330 d = datetime(*updated_for_months) 331 s = timedelta(step[2], get_seconds(step)) 332 333 return to_tuple(d + s, len(t)) 334 335 def to_tuple(d, n=None): 336 if not isinstance(d, date): 337 return d 338 if n is None: 339 if isinstance(d, datetime): 340 n = 6 341 else: 342 n = 3 343 return d.timetuple()[:n] 344 345 def get_first_day(first_day, weekday): 346 first_day = date(*first_day) 347 first_weekday = first_day.isoweekday() 348 if first_weekday > weekday: 349 return first_day + timedelta(7 - first_weekday + weekday) 350 else: 351 return first_day + timedelta(weekday - first_weekday) 352 353 def get_last_day(last_day, weekday): 354 last_day = date(*last_day) 355 last_weekday = last_day.isoweekday() 356 if last_weekday < weekday: 357 return last_day - timedelta(last_weekday + 7 - weekday) 358 else: 359 return last_day - timedelta(last_weekday - weekday) 360 361 # Classes for producing instances from recurrence structures. 362 363 class Selector: 364 def __init__(self, level, args, qualifier, selecting=None): 365 self.level = level 366 self.pos = positions[level] 367 self.args = args 368 self.qualifier = qualifier 369 self.context = () 370 self.selecting = selecting 371 372 def __repr__(self): 373 return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.level, self.args, self.qualifier, self.context) 374 375 def materialise(self, start, end, count=None, setpos=None): 376 start = to_tuple(start) 377 end = to_tuple(end) 378 counter = count and [0, count] 379 results = self.materialise_items(self.context, start, end, counter, setpos) 380 results.sort() 381 return results[:count] 382 383 def materialise_item(self, current, last, next, counter, setpos=None): 384 if self.selecting: 385 return self.selecting.materialise_items(current, last, next, counter, setpos) 386 elif last <= current: 387 return [current] 388 else: 389 return [] 390 391 def convert_positions(self, setpos): 392 l = [] 393 for pos in setpos: 394 lower = pos < 0 and pos or pos - 1 395 upper = pos > 0 and pos or pos < -1 and pos + 1 or None 396 l.append((lower, upper)) 397 return l 398 399 def select_positions(self, results, setpos): 400 results.sort() 401 l = [] 402 for lower, upper in self.convert_positions(setpos): 403 l += results[lower:upper] 404 return l 405 406 def filter_by_period(self, results, start, end): 407 l = [] 408 for result in results: 409 if start <= result < end: 410 l.append(result) 411 return l 412 413 class Pattern(Selector): 414 def materialise_items(self, context, start, end, counter, setpos=None): 415 first = scale(self.context[self.pos], self.pos) 416 417 # Define the step between items. 418 419 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 420 step = scale(interval, self.pos) 421 422 # Define the scale of a single item. 423 424 unit_interval = units.get(self.qualifier, 1) 425 unit_step = scale(unit_interval, self.pos) 426 427 current = combine(context, first) 428 results = [] 429 430 while current < end and (counter is None or counter[0] < counter[1]): 431 next = update(current, step) 432 current_end = update(current, unit_step) 433 interval_results = self.materialise_item(current, max(current, start), min(current_end, end), counter, setpos) 434 if counter is not None: 435 counter[0] += len(interval_results) 436 results += interval_results 437 current = next 438 439 return results 440 441 class WeekDayFilter(Selector): 442 def materialise_items(self, context, start, end, counter, setpos=None): 443 step = scale(1, 2) 444 results = [] 445 446 # Get weekdays in the year. 447 448 if len(context) == 1: 449 first_day = (context[0], 1, 1) 450 last_day = (context[0], 12, 31) 451 452 # Get weekdays in the month. 453 454 elif len(context) == 2: 455 first_day = (context[0], context[1], 1) 456 last_day = update((context[0], context[1], 1), (0, 1, 0)) 457 last_day = update(last_day, (0, 0, -1)) 458 459 # Get weekdays in the week. 460 461 else: 462 current = context 463 values = [value for (value, index) in self.args["values"]] 464 465 while current < end: 466 next = update(current, step) 467 if date(*current).isoweekday() in values: 468 results += self.materialise_item(current, max(current, start), min(next, end), counter) 469 current = next 470 471 if setpos: 472 return self.select_positions(results, setpos) 473 else: 474 return results 475 476 # Find each of the given days. 477 478 for value, index in self.args["values"]: 479 if index is not None: 480 offset = timedelta(7 * (abs(index) - 1)) 481 482 if index < 0: 483 current = to_tuple(get_last_day(last_day, value) - offset, 3) 484 else: 485 current = to_tuple(get_first_day(first_day, value) + offset, 3) 486 487 next = update(current, step) 488 489 # To support setpos, only current and next bound the search, not 490 # the period in addition. 491 492 results += self.materialise_item(current, current, next, counter) 493 494 else: 495 if index < 0: 496 current = to_tuple(get_last_day(last_day, value), 3) 497 direction = operator.sub 498 else: 499 current = to_tuple(get_first_day(first_day, value), 3) 500 direction = operator.add 501 502 while first_day <= current <= last_day: 503 next = update(current, step) 504 505 # To support setpos, only current and next bound the search, not 506 # the period in addition. 507 508 results += self.materialise_item(current, current, next, counter) 509 current = to_tuple(direction(date(*current), timedelta(7)), 3) 510 511 # Extract selected positions and remove out-of-period instances. 512 513 if setpos: 514 results = self.select_positions(results, setpos) 515 516 return self.filter_by_period(results, start, end) 517 518 class Enum(Selector): 519 def materialise_items(self, context, start, end, counter, setpos=None): 520 step = scale(1, self.pos) 521 results = [] 522 for value in self.args["values"]: 523 current = combine(context, scale(value, self.pos)) 524 next = update(current, step) 525 526 # To support setpos, only current and next bound the search, not 527 # the period in addition. 528 529 results += self.materialise_item(current, current, next, counter, setpos) 530 531 # Extract selected positions and remove out-of-period instances. 532 533 if setpos: 534 results = self.select_positions(results, setpos) 535 536 return self.filter_by_period(results, start, end) 537 538 class MonthDayFilter(Enum): 539 def materialise_items(self, context, start, end, counter, setpos=None): 540 last_day = monthrange(context[0], context[1])[1] 541 step = scale(1, self.pos) 542 results = [] 543 for value in self.args["values"]: 544 if value < 0: 545 value = last_day + 1 + value 546 current = combine(context, scale(value, self.pos)) 547 next = update(current, step) 548 549 # To support setpos, only current and next bound the search, not 550 # the period in addition. 551 552 results += self.materialise_item(current, current, next, counter) 553 554 # Extract selected positions and remove out-of-period instances. 555 556 if setpos: 557 results = self.select_positions(results, setpos) 558 559 return self.filter_by_period(results, start, end) 560 561 class YearDayFilter(Enum): 562 def materialise_items(self, context, start, end, counter, setpos=None): 563 first_day = date(context[0], 1, 1) 564 next_first_day = date(context[0] + 1, 1, 1) 565 year_length = (next_first_day - first_day).days 566 step = scale(1, self.pos) 567 results = [] 568 for value in self.args["values"]: 569 if value < 0: 570 value = year_length + 1 + value 571 current = to_tuple(first_day + timedelta(value - 1), 3) 572 next = update(current, step) 573 574 # To support setpos, only current and next bound the search, not 575 # the period in addition. 576 577 results += self.materialise_item(current, current, next, counter) 578 579 # Extract selected positions and remove out-of-period instances. 580 581 if setpos: 582 results = self.select_positions(results, setpos) 583 584 return self.filter_by_period(results, start, end) 585 586 special_enum_levels = { 587 "BYDAY" : WeekDayFilter, 588 "BYMONTHDAY" : MonthDayFilter, 589 "BYYEARDAY" : YearDayFilter, 590 } 591 592 # Public functions. 593 594 def connect_selectors(selectors): 595 current = selectors[0] 596 for selector in selectors[1:]: 597 current.selecting = selector 598 current = selector 599 return selectors[0] 600 601 def get_selector(dt, qualifiers): 602 dt = to_tuple(dt) 603 return connect_selectors(combine_datetime_with_qualifiers(dt, qualifiers)) 604 605 def get_rule(dt, rule): 606 607 """ 608 Using the given initial datetime 'dt', interpret the 'rule' (a semicolon- 609 separated collection of "key=value" strings), and return the resulting 610 selector object. 611 """ 612 613 qualifiers = get_qualifiers(rule.split(";")) 614 return get_selector(dt, qualifiers) 615 616 # vim: tabstop=4 expandtab shiftwidth=4