1 #!/usr/bin/env python 2 3 """ 4 Recurrence rule calculation. 5 6 Copyright (C) 2014, 2015 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 of the form (qualifier name, args). 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 288 """ 289 Combine tuples 't1' and 't2', returning a copy of 't1' filled with values 290 from 't2' in positions where 0 appeared in 't1'. 291 """ 292 293 return tuple(map(lambda x, y: x or y, t1, t2)) 294 295 def scale(interval, pos): 296 297 """ 298 Scale the given 'interval' value to the indicated position 'pos', returning 299 a tuple with leading zero elements and 'interval' at the stated position. 300 """ 301 302 return (0,) * pos + (interval,) 303 304 def get_seconds(t): 305 306 "Convert the sub-day part of 't' into seconds." 307 308 t = t + (0,) * (6 - len(t)) 309 return (t[3] * 60 + t[4]) * 60 + t[5] 310 311 def update(t, step): 312 313 "Update 't' by 'step' at the resolution of 'step'." 314 315 i = len(step) 316 317 # Years only. 318 319 if i == 1: 320 return (t[0] + step[0],) + tuple(t[1:]) 321 322 # Years and months. 323 324 elif i == 2: 325 month = t[1] + step[1] 326 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 327 328 # Dates and datetimes. 329 330 else: 331 updated_for_months = update(t, step[:2]) 332 333 # Dates only. 334 335 if i == 3: 336 d = datetime(*updated_for_months) 337 s = timedelta(step[2]) 338 339 # Datetimes. 340 341 else: 342 d = datetime(*updated_for_months) 343 s = timedelta(step[2], get_seconds(step)) 344 345 return to_tuple(d + s, len(t)) 346 347 def to_tuple(d, n=None): 348 349 "Return 'd' as a tuple, optionally trimming the result to 'n' positions." 350 351 if not isinstance(d, date): 352 return d 353 if n is None: 354 if isinstance(d, datetime): 355 n = 6 356 else: 357 n = 3 358 return d.timetuple()[:n] 359 360 def get_first_day(first_day, weekday): 361 362 "Return the first occurrence at or after 'first_day' of 'weekday'." 363 364 first_day = date(*first_day) 365 first_weekday = first_day.isoweekday() 366 if first_weekday > weekday: 367 return first_day + timedelta(7 - first_weekday + weekday) 368 else: 369 return first_day + timedelta(weekday - first_weekday) 370 371 def get_last_day(last_day, weekday): 372 373 "Return the last occurrence at or before 'last_day' of 'weekday'." 374 375 last_day = date(*last_day) 376 last_weekday = last_day.isoweekday() 377 if last_weekday < weekday: 378 return last_day - timedelta(last_weekday + 7 - weekday) 379 else: 380 return last_day - timedelta(last_weekday - weekday) 381 382 # Classes for producing instances from recurrence structures. 383 384 class Selector: 385 386 "A generic selector." 387 388 def __init__(self, level, args, qualifier, selecting=None): 389 390 """ 391 Initialise at the given 'level' a selector employing the given 'args' 392 defined in the interpretation of recurrence rule qualifiers, with the 393 'qualifier' being the name of the rule qualifier, and 'selecting' being 394 an optional selector used to find more specific instances from those 395 found by this selector. 396 """ 397 398 self.level = level 399 self.pos = positions[level] 400 self.args = args 401 self.qualifier = qualifier 402 self.context = () 403 self.selecting = selecting 404 405 def __repr__(self): 406 return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.level, self.args, self.qualifier, self.context) 407 408 def materialise(self, start, end, count=None, setpos=None): 409 410 """ 411 Starting at 'start', materialise instances up to but not including any 412 at 'end' or later, returning at most 'count' if specified, and returning 413 only the occurrences indicated by 'setpos' if specified. A list of 414 instances is returned. 415 """ 416 417 start = to_tuple(start) 418 end = to_tuple(end) 419 counter = count and [0, count] 420 results = self.materialise_items(self.context, start, end, counter, setpos) 421 results.sort() 422 return results[:count] 423 424 def materialise_item(self, current, earliest, next, counter, setpos=None): 425 426 """ 427 Given the 'current' instance, the 'earliest' acceptable instance, the 428 'next' instance, an instance 'counter', and the optional 'setpos' 429 criteria, return a list of result items. Where no selection within the 430 current instance occurs, the current instance will be returned as a 431 result if the same or later than the earliest acceptable instance. 432 """ 433 434 if self.selecting: 435 return self.selecting.materialise_items(current, earliest, next, counter, setpos) 436 elif earliest <= current: 437 return [current] 438 else: 439 return [] 440 441 def convert_positions(self, setpos): 442 443 "Convert 'setpos' to 0-based indexes." 444 445 l = [] 446 for pos in setpos: 447 lower = pos < 0 and pos or pos - 1 448 upper = pos > 0 and pos or pos < -1 and pos + 1 or None 449 l.append((lower, upper)) 450 return l 451 452 def select_positions(self, results, setpos): 453 454 "Select in 'results' the 1-based positions given by 'setpos'." 455 456 results.sort() 457 l = [] 458 for lower, upper in self.convert_positions(setpos): 459 l += results[lower:upper] 460 return l 461 462 def filter_by_period(self, results, start, end): 463 464 """ 465 Filter 'results' so that only those at or after 'start' and before 'end' 466 are returned. 467 """ 468 469 l = [] 470 for result in results: 471 if start <= result < end: 472 l.append(result) 473 return l 474 475 class Pattern(Selector): 476 477 "A selector of instances according to a repeating pattern." 478 479 def materialise_items(self, context, start, end, counter, setpos=None): 480 first = scale(self.context[self.pos], self.pos) 481 482 # Define the step between items. 483 484 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 485 step = scale(interval, self.pos) 486 487 # Define the scale of a single item. 488 489 unit_interval = units.get(self.qualifier, 1) 490 unit_step = scale(unit_interval, self.pos) 491 492 current = combine(context, first) 493 results = [] 494 495 while current < end and (counter is None or counter[0] < counter[1]): 496 next = update(current, step) 497 current_end = update(current, unit_step) 498 interval_results = self.materialise_item(current, max(current, start), min(current_end, end), counter, setpos) 499 if counter is not None: 500 counter[0] += len(interval_results) 501 results += interval_results 502 current = next 503 504 return results 505 506 class WeekDayFilter(Selector): 507 508 "A selector of instances specified in terms of day numbers." 509 510 def materialise_items(self, context, start, end, counter, setpos=None): 511 step = scale(1, 2) 512 results = [] 513 514 # Get weekdays in the year. 515 516 if len(context) == 1: 517 first_day = (context[0], 1, 1) 518 last_day = (context[0], 12, 31) 519 520 # Get weekdays in the month. 521 522 elif len(context) == 2: 523 first_day = (context[0], context[1], 1) 524 last_day = update((context[0], context[1], 1), (0, 1, 0)) 525 last_day = update(last_day, (0, 0, -1)) 526 527 # Get weekdays in the week. 528 529 else: 530 current = context 531 values = [value for (value, index) in self.args["values"]] 532 533 while current < end: 534 next = update(current, step) 535 if date(*current).isoweekday() in values: 536 results += self.materialise_item(current, max(current, start), min(next, end), counter) 537 current = next 538 539 if setpos: 540 return self.select_positions(results, setpos) 541 else: 542 return results 543 544 # Find each of the given days. 545 546 for value, index in self.args["values"]: 547 if index is not None: 548 offset = timedelta(7 * (abs(index) - 1)) 549 550 if index < 0: 551 current = to_tuple(get_last_day(last_day, value) - offset, 3) 552 else: 553 current = to_tuple(get_first_day(first_day, value) + offset, 3) 554 555 next = update(current, step) 556 557 # To support setpos, only current and next bound the search, not 558 # the period in addition. 559 560 results += self.materialise_item(current, current, next, counter) 561 562 else: 563 if index < 0: 564 current = to_tuple(get_last_day(last_day, value), 3) 565 direction = operator.sub 566 else: 567 current = to_tuple(get_first_day(first_day, value), 3) 568 direction = operator.add 569 570 while first_day <= current <= last_day: 571 next = update(current, step) 572 573 # To support setpos, only current and next bound the search, not 574 # the period in addition. 575 576 results += self.materialise_item(current, current, next, counter) 577 current = to_tuple(direction(date(*current), timedelta(7)), 3) 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 class Enum(Selector): 587 def materialise_items(self, context, start, end, counter, setpos=None): 588 step = scale(1, self.pos) 589 results = [] 590 for value in self.args["values"]: 591 current = combine(context, scale(value, self.pos)) 592 next = update(current, step) 593 594 # To support setpos, only current and next bound the search, not 595 # the period in addition. 596 597 results += self.materialise_item(current, current, next, counter, setpos) 598 599 # Extract selected positions and remove out-of-period instances. 600 601 if setpos: 602 results = self.select_positions(results, setpos) 603 604 return self.filter_by_period(results, start, end) 605 606 class MonthDayFilter(Enum): 607 def materialise_items(self, context, start, end, counter, setpos=None): 608 last_day = monthrange(context[0], context[1])[1] 609 step = scale(1, self.pos) 610 results = [] 611 for value in self.args["values"]: 612 if value < 0: 613 value = last_day + 1 + value 614 current = combine(context, scale(value, self.pos)) 615 next = update(current, step) 616 617 # To support setpos, only current and next bound the search, not 618 # the period in addition. 619 620 results += self.materialise_item(current, current, next, counter) 621 622 # Extract selected positions and remove out-of-period instances. 623 624 if setpos: 625 results = self.select_positions(results, setpos) 626 627 return self.filter_by_period(results, start, end) 628 629 class YearDayFilter(Enum): 630 def materialise_items(self, context, start, end, counter, setpos=None): 631 first_day = date(context[0], 1, 1) 632 next_first_day = date(context[0] + 1, 1, 1) 633 year_length = (next_first_day - first_day).days 634 step = scale(1, self.pos) 635 results = [] 636 for value in self.args["values"]: 637 if value < 0: 638 value = year_length + 1 + value 639 current = to_tuple(first_day + timedelta(value - 1), 3) 640 next = update(current, step) 641 642 # To support setpos, only current and next bound the search, not 643 # the period in addition. 644 645 results += self.materialise_item(current, current, next, counter) 646 647 # Extract selected positions and remove out-of-period instances. 648 649 if setpos: 650 results = self.select_positions(results, setpos) 651 652 return self.filter_by_period(results, start, end) 653 654 special_enum_levels = { 655 "BYDAY" : WeekDayFilter, 656 "BYMONTHDAY" : MonthDayFilter, 657 "BYYEARDAY" : YearDayFilter, 658 } 659 660 # Public functions. 661 662 def connect_selectors(selectors): 663 664 """ 665 Make the 'selectors' reference each other in a hierarchy so that 666 materialising the principal selector causes the more specific ones to be 667 employed in the operation. 668 """ 669 670 current = selectors[0] 671 for selector in selectors[1:]: 672 current.selecting = selector 673 current = selector 674 return selectors[0] 675 676 def get_selector(dt, qualifiers): 677 678 """ 679 Combine the initial datetime 'dt' with the given 'qualifiers', returning an 680 object that can be used to select recurrences described by the 'qualifiers'. 681 """ 682 683 dt = to_tuple(dt) 684 return connect_selectors(combine_datetime_with_qualifiers(dt, qualifiers)) 685 686 def get_rule(dt, rule): 687 688 """ 689 Using the given initial datetime 'dt', interpret the 'rule' (a semicolon- 690 separated collection of "key=value" strings), and return the resulting 691 selector object. 692 """ 693 694 if not isinstance(rule, tuple): 695 rule = rule.split(";") 696 qualifiers = get_qualifiers(rule) 697 return get_selector(dt, qualifiers) 698 699 # vim: tabstop=4 expandtab shiftwidth=4