1 #!/usr/bin/env python 2 3 """ 4 Recurrence rule calculation. 5 6 Copyright (C) 2014, 2015, 2017 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 35 UNTIL defines a limit to the selection. 36 37 BY... qualifiers select instances within each outer selection instance according 38 to the recurrence of instances of the next highest resolution. For example, 39 BYDAY selects days in weeks. Thus, if no explicit week recurrence is indicated, 40 all weeks are selected within the selection of the next highest explicitly 41 specified resolution, whether this is months or years. 42 43 BYSETPOS in conjunction with BY... qualifiers permit the selection of specific 44 instances. 45 46 Within the FREQ resolution, BY... qualifiers refine selected instances. 47 48 Outside the FREQ resolution, BY... qualifiers select instances at the resolution 49 concerned. 50 51 Thus, FREQ and BY... qualifiers need to be ordered in terms of increasing 52 resolution (or decreasing scope). 53 """ 54 55 from calendar import monthrange 56 from datetime import date, datetime, timedelta 57 import operator 58 59 # Frequency levels, specified by FREQ in iCalendar. 60 61 freq_levels = ( 62 "YEARLY", 63 "MONTHLY", 64 "WEEKLY", 65 None, 66 None, 67 "DAILY", 68 "HOURLY", 69 "MINUTELY", 70 "SECONDLY" 71 ) 72 73 # Enumeration levels, employed by BY... qualifiers. 74 75 enum_levels = ( 76 None, 77 "BYMONTH", 78 "BYWEEKNO", 79 "BYYEARDAY", 80 "BYMONTHDAY", 81 "BYDAY", 82 "BYHOUR", 83 "BYMINUTE", 84 "BYSECOND" 85 ) 86 87 # Map from levels to lengths of datetime tuples. 88 89 lengths = [1, 2, 3, 3, 3, 3, 4, 5, 6] 90 positions = [l-1 for l in lengths] 91 92 # Map from qualifiers to interval units. Here, weeks are defined as 7 days. 93 94 units = {"WEEKLY" : 7} 95 96 # Make dictionaries mapping qualifiers to levels. 97 98 freq = dict([(level, i) for (i, level) in enumerate(freq_levels) if level]) 99 enum = dict([(level, i) for (i, level) in enumerate(enum_levels) if level]) 100 weekdays = dict([(weekday, i+1) for (i, weekday) in enumerate(["MO", "TU", "WE", "TH", "FR", "SA", "SU"])]) 101 102 # Functions for structuring the recurrences. 103 104 def get_next(it): 105 try: 106 return it.next() 107 except StopIteration: 108 return None 109 110 def get_parameters(values): 111 112 "Return parameters from the given list of 'values'." 113 114 d = {} 115 for value in values: 116 parts = value.split("=", 1) 117 if len(parts) < 2: 118 continue 119 key, value = parts 120 if key in ("COUNT", "BYSETPOS"): 121 d[key] = int(value) 122 else: 123 d[key] = value 124 return d 125 126 def get_qualifiers(values): 127 128 """ 129 Process the list of 'values' of the form "key=value", returning a list of 130 qualifiers of the form (qualifier name, args). 131 """ 132 133 qualifiers = [] 134 frequency = None 135 interval = 1 136 137 for value in values: 138 parts = value.split("=", 1) 139 if len(parts) < 2: 140 continue 141 key, value = parts 142 143 # Accept frequency indicators as qualifiers. 144 145 if key == "FREQ" and freq.has_key(value): 146 qualifier = frequency = (value, {}) 147 148 # Accept interval indicators for frequency qualifier parameterisation. 149 150 elif key == "INTERVAL": 151 interval = int(value) 152 continue 153 154 # Accept enumerators as qualifiers. 155 156 elif enum.has_key(key): 157 qualifier = (key, {"values" : get_qualifier_values(key, value)}) 158 159 # Ignore other items. 160 161 else: 162 continue 163 164 qualifiers.append(qualifier) 165 166 # Parameterise any frequency qualifier with the interval. 167 168 if frequency: 169 frequency[1]["interval"] = interval 170 171 return qualifiers 172 173 def get_qualifier_values(qualifier, value): 174 175 """ 176 For the given 'qualifier', process the 'value' string, returning a list of 177 suitable values. 178 """ 179 180 if qualifier != "BYDAY": 181 return map(int, value.split(",")) 182 183 values = [] 184 for part in value.split(","): 185 weekday = weekdays.get(part[-2:]) 186 if not weekday: 187 continue 188 index = part[:-2] 189 if index: 190 index = int(index) 191 else: 192 index = None 193 values.append((weekday, index)) 194 195 return values 196 197 def order_qualifiers(qualifiers): 198 199 "Return the 'qualifiers' in order of increasing resolution." 200 201 l = [] 202 203 for qualifier, args in qualifiers: 204 205 # Distinguish between enumerators, used to select particular periods, 206 # and frequencies, used to select repeating periods. 207 208 if enum.has_key(qualifier): 209 level = enum[qualifier] 210 if special_enum_levels.has_key(qualifier): 211 args["interval"] = 1 212 selector = special_enum_levels[qualifier] 213 else: 214 selector = Enum 215 else: 216 level = freq[qualifier] 217 selector = Pattern 218 219 l.append(selector(level, args, qualifier)) 220 221 l.sort(key=lambda x: x.level) 222 return l 223 224 def get_datetime_structure(datetime): 225 226 "Return the structure of 'datetime' for recurrence production." 227 228 l = [] 229 offset = 0 230 231 for level, value in enumerate(datetime): 232 233 # At the day number, adjust the frequency level offset to reference 234 # days (and then hours, minutes, seconds). 235 236 if level == 2: 237 offset = 3 238 239 l.append(Enum(level + offset, {"values" : [value]}, "DT")) 240 241 return l 242 243 def combine_datetime_with_qualifiers(datetime, qualifiers): 244 245 """ 246 Combine 'datetime' with 'qualifiers' to produce a structure for recurrence 247 production. 248 """ 249 250 iter_dt = iter(get_datetime_structure(datetime)) 251 iter_q = iter(order_qualifiers(qualifiers)) 252 253 l = [] 254 255 from_dt = get_next(iter_dt) 256 from_q = get_next(iter_q) 257 258 have_q = False 259 260 # The initial context for any qualifiers is taken from the first datetime 261 # value, which should be the year. 262 263 context = [] 264 context.append(from_dt.args["values"][0]) 265 266 # Consume from both lists, merging entries. 267 268 while from_dt and from_q: 269 _level = from_dt.level 270 level = from_q.level 271 272 # Datetime value at wider resolution. Use the datetime value to expand 273 # the context within which qualifiers will operate. 274 275 if _level < level: 276 from_dt = get_next(iter_dt) 277 context.append(from_dt.args["values"][0]) 278 279 # Qualifier at wider or same resolution as datetime value. 280 281 else: 282 # Without any previous qualifier, introduce a special qualifier to 283 # provide context for this qualifier. 284 285 if not have_q: 286 add_initial_qualifier(from_q, level, context, l) 287 have_q = True 288 289 # Associate the datetime context with the qualifier and add it to 290 # the combined list. 291 292 from_q.context = tuple(context) 293 l.append(from_q) 294 295 # Datetime value at same resolution. Expand the context using the 296 # value. 297 298 if _level == level: 299 from_dt = get_next(iter_dt) 300 if from_dt: 301 context.append(from_dt.args["values"][0]) 302 303 # Get the next qualifier. 304 305 from_q = get_next(iter_q) 306 307 # Complete the list by adding remaining datetime enumerators. 308 309 while from_dt: 310 l.append(from_dt) 311 from_dt = get_next(iter_dt) 312 313 # Complete the list by adding remaining qualifiers. 314 315 while from_q: 316 if not have_q: 317 add_initial_qualifier(from_q, level, context, l) 318 have_q = True 319 320 # Associate the datetime context with the qualifier and add it to the 321 # combined list. 322 323 from_q.context = tuple(context) 324 l.append(from_q) 325 326 # Get the next qualifier. 327 328 from_q = get_next(iter_q) 329 330 return l 331 332 def add_initial_qualifier(from_q, level, context, l): 333 334 """ 335 Take the first qualifier 'from_q' at the given resolution 'level', using it 336 to create an initial qualifier providing appropriate context, using the 337 given 'context', adding it to the combined list 'l' if required. 338 """ 339 340 if isinstance(from_q, Enum) and level > 0: 341 repeat = Pattern(level - 1, {"interval" : 1}, None) 342 repeat.context = tuple(context) 343 l.append(repeat) 344 345 # Datetime arithmetic. 346 347 def combine(t1, t2): 348 349 """ 350 Combine tuples 't1' and 't2', returning a copy of 't1' filled with values 351 from 't2' in positions where 0 appeared in 't1'. 352 """ 353 354 return tuple(map(lambda x, y: x or y, t1, t2)) 355 356 def scale(interval, pos): 357 358 """ 359 Scale the given 'interval' value to the indicated position 'pos', returning 360 a tuple with leading zero elements and 'interval' at the stated position. 361 """ 362 363 return (0,) * pos + (interval,) 364 365 def get_seconds(t): 366 367 "Convert the sub-day part of 't' into seconds." 368 369 t = t + (0,) * (6 - len(t)) 370 return (t[3] * 60 + t[4]) * 60 + t[5] 371 372 def update(t, step): 373 374 "Update 't' by 'step' at the resolution of 'step'." 375 376 i = len(step) 377 378 # Years only. 379 380 if i == 1: 381 return (t[0] + step[0],) + tuple(t[1:]) 382 383 # Years and months. 384 385 elif i == 2: 386 month = t[1] + step[1] 387 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 388 389 # Dates and datetimes. 390 391 else: 392 updated_for_months = update(t, step[:2]) 393 394 # Dates only. 395 396 if i == 3: 397 d = datetime(*updated_for_months) 398 s = timedelta(step[2]) 399 400 # Datetimes. 401 402 else: 403 d = datetime(*updated_for_months) 404 s = timedelta(step[2], get_seconds(step)) 405 406 return to_tuple(d + s, len(t)) 407 408 def to_tuple(d, n=None): 409 410 "Return 'd' as a tuple, optionally trimming the result to 'n' positions." 411 412 if not isinstance(d, date): 413 return d 414 if n is None: 415 if isinstance(d, datetime): 416 n = 6 417 else: 418 n = 3 419 return d.timetuple()[:n] 420 421 def get_first_day(first_day, weekday): 422 423 "Return the first occurrence at or after 'first_day' of 'weekday'." 424 425 first_day = date(*first_day) 426 first_weekday = first_day.isoweekday() 427 if first_weekday > weekday: 428 return first_day + timedelta(7 - first_weekday + weekday) 429 else: 430 return first_day + timedelta(weekday - first_weekday) 431 432 def get_last_day(last_day, weekday): 433 434 "Return the last occurrence at or before 'last_day' of 'weekday'." 435 436 last_day = date(*last_day) 437 last_weekday = last_day.isoweekday() 438 if last_weekday < weekday: 439 return last_day - timedelta(last_weekday + 7 - weekday) 440 else: 441 return last_day - timedelta(last_weekday - weekday) 442 443 # Classes for producing instances from recurrence structures. 444 445 class Selector: 446 447 "A generic selector." 448 449 def __init__(self, level, args, qualifier, selecting=None): 450 451 """ 452 Initialise at the given 'level' a selector employing the given 'args' 453 defined in the interpretation of recurrence rule qualifiers, with the 454 'qualifier' being the name of the rule qualifier, and 'selecting' being 455 an optional selector used to find more specific instances from those 456 found by this selector. 457 """ 458 459 self.level = level 460 self.args = args 461 self.qualifier = qualifier 462 self.selecting = selecting 463 464 # Define an empty context to be overridden. 465 466 self.context = () 467 468 # Define the index of values from datetimes involved with this selector. 469 470 self.pos = positions[level] 471 472 def __repr__(self): 473 return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.level, self.args, self.qualifier, self.context) 474 475 def materialise(self, start, end, count=None, setpos=None, inclusive=False): 476 477 """ 478 Starting at 'start', materialise instances up to but not including any 479 at 'end' or later, returning at most 'count' if specified, and returning 480 only the occurrences indicated by 'setpos' if specified. A list of 481 instances is returned. 482 483 If 'inclusive' is specified, the selection of instances will include the 484 end of the search period if present in the results. 485 """ 486 487 start = to_tuple(start) 488 end = to_tuple(end) 489 counter = count and [0, count] 490 results = self.materialise_items(self.context, start, end, counter, setpos, inclusive) 491 results.sort() 492 return results[:count] 493 494 def materialise_item(self, current, earliest, next, counter, setpos=None, inclusive=False): 495 496 """ 497 Given the 'current' instance, the 'earliest' acceptable instance, the 498 'next' instance, an instance 'counter', and the optional 'setpos' 499 criteria, return a list of result items. Where no selection within the 500 current instance occurs, the current instance will be returned as a 501 result if the same or later than the earliest acceptable instance. 502 """ 503 504 if self.selecting: 505 return self.selecting.materialise_items(current, earliest, next, counter, setpos, inclusive) 506 elif earliest <= current: 507 return [current] 508 else: 509 return [] 510 511 def convert_positions(self, setpos): 512 513 "Convert 'setpos' to 0-based indexes." 514 515 l = [] 516 for pos in setpos: 517 lower = pos < 0 and pos or pos - 1 518 upper = pos > 0 and pos or pos < -1 and pos + 1 or None 519 l.append((lower, upper)) 520 return l 521 522 def select_positions(self, results, setpos): 523 524 "Select in 'results' the 1-based positions given by 'setpos'." 525 526 results.sort() 527 l = [] 528 for lower, upper in self.convert_positions(setpos): 529 l += results[lower:upper] 530 return l 531 532 def filter_by_period(self, results, start, end, inclusive): 533 534 """ 535 Filter 'results' so that only those at or after 'start' and before 'end' 536 are returned. 537 538 If 'inclusive' is specified, the selection of instances will include the 539 end of the search period if present in the results. 540 """ 541 542 l = [] 543 for result in results: 544 if start <= result and (inclusive and result <= end or result < end): 545 l.append(result) 546 return l 547 548 class Pattern(Selector): 549 550 "A selector of time periods according to a repeating pattern." 551 552 def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): 553 554 """ 555 Bounded by the given 'context', return periods within 'start' to 'end', 556 updating the 'counter', selecting only the indexes specified by 'setpos' 557 (if given). 558 559 If 'inclusive' is specified, the selection of periods will include those 560 starting at the end of the search period, if present in the results. 561 """ 562 563 # Obtain the pattern context's value at the appropriate level. 564 565 first = scale(self.context[self.pos], self.pos) 566 567 # Define the step between result periods. 568 569 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 570 step = scale(interval, self.pos) 571 572 # Define the scale of a single period. 573 574 unit_interval = units.get(self.qualifier, 1) 575 unit_step = scale(unit_interval, self.pos) 576 577 # Combine supplied context details with the pattern context. This should 578 # provide additional resolution information that may be missing from the 579 # supplied context. For example, the outer selector may indicate a month 580 # context, but this selector may need day information. 581 582 current = combine(context, first) 583 results = [] 584 585 # Obtain periods before the end (and also at the end if inclusive), 586 # provided that any limit imposed by the counter has not been exceeded. 587 588 while (inclusive and current <= end or current < end) and \ 589 (counter is None or counter[0] < counter[1]): 590 591 # Increment the current datetime by the step for the next period. 592 593 next = update(current, step) 594 595 # Determine the end point of the current period. 596 597 current_end = update(current, unit_step) 598 599 # Obtain any period or periods within the bounds defined by the 600 # current period and any contraining start and end points, plus 601 # counter, setpos and inclusive details. 602 603 interval_results = self.materialise_item(current, max(current, start), min(current_end, end), counter, setpos, inclusive) 604 605 # Update the counter with the number of identified results. 606 607 if counter is not None: 608 counter[0] += len(interval_results) 609 610 # Accumulate the results. 611 612 results += interval_results 613 614 # Visit the next instance. 615 616 current = next 617 618 return results 619 620 class WeekDayFilter(Selector): 621 622 "A selector of instances specified in terms of day numbers." 623 624 def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): 625 step = scale(1, 2) 626 results = [] 627 628 # Get weekdays in the year. 629 630 if len(context) == 1: 631 first_day = (context[0], 1, 1) 632 last_day = (context[0], 12, 31) 633 634 # Get weekdays in the month. 635 636 elif len(context) == 2: 637 first_day = (context[0], context[1], 1) 638 last_day = update((context[0], context[1], 1), (0, 1, 0)) 639 last_day = update(last_day, (0, 0, -1)) 640 641 # Get weekdays in the week. 642 643 else: 644 current = context 645 values = [value for (value, index) in self.args["values"]] 646 647 while (inclusive and current <= end or current < end): 648 next = update(current, step) 649 if date(*current).isoweekday() in values: 650 results += self.materialise_item(current, max(current, start), min(next, end), counter, inclusive=inclusive) 651 current = next 652 653 if setpos: 654 return self.select_positions(results, setpos) 655 else: 656 return results 657 658 # Find each of the given days. 659 660 for value, index in self.args["values"]: 661 if index is not None: 662 offset = timedelta(7 * (abs(index) - 1)) 663 664 if index < 0: 665 current = to_tuple(get_last_day(last_day, value) - offset, 3) 666 else: 667 current = to_tuple(get_first_day(first_day, value) + offset, 3) 668 669 next = update(current, step) 670 671 # To support setpos, only current and next bound the search, not 672 # the period in addition. 673 674 results += self.materialise_item(current, current, next, counter, inclusive=inclusive) 675 676 else: 677 if index < 0: 678 current = to_tuple(get_last_day(last_day, value), 3) 679 direction = operator.sub 680 else: 681 current = to_tuple(get_first_day(first_day, value), 3) 682 direction = operator.add 683 684 while first_day <= current <= last_day: 685 next = update(current, step) 686 687 # To support setpos, only current and next bound the search, not 688 # the period in addition. 689 690 results += self.materialise_item(current, current, next, counter, inclusive=inclusive) 691 current = to_tuple(direction(date(*current), timedelta(7)), 3) 692 693 # Extract selected positions and remove out-of-period instances. 694 695 if setpos: 696 results = self.select_positions(results, setpos) 697 698 return self.filter_by_period(results, start, end, inclusive) 699 700 class Enum(Selector): 701 def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): 702 step = scale(1, self.pos) 703 results = [] 704 for value in self.args["values"]: 705 current = combine(context, scale(value, self.pos)) 706 next = update(current, step) 707 708 # To support setpos, only current and next bound the search, not 709 # the period in addition. 710 711 results += self.materialise_item(current, current, next, counter, setpos, inclusive) 712 713 # Extract selected positions and remove out-of-period instances. 714 715 if setpos: 716 results = self.select_positions(results, setpos) 717 718 return self.filter_by_period(results, start, end, inclusive) 719 720 class MonthDayFilter(Enum): 721 def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): 722 last_day = monthrange(context[0], context[1])[1] 723 step = scale(1, self.pos) 724 results = [] 725 for value in self.args["values"]: 726 if value < 0: 727 value = last_day + 1 + value 728 current = combine(context, scale(value, self.pos)) 729 next = update(current, step) 730 731 # To support setpos, only current and next bound the search, not 732 # the period in addition. 733 734 results += self.materialise_item(current, current, next, counter, inclusive=inclusive) 735 736 # Extract selected positions and remove out-of-period instances. 737 738 if setpos: 739 results = self.select_positions(results, setpos) 740 741 return self.filter_by_period(results, start, end, inclusive) 742 743 class YearDayFilter(Enum): 744 def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): 745 first_day = date(context[0], 1, 1) 746 next_first_day = date(context[0] + 1, 1, 1) 747 year_length = (next_first_day - first_day).days 748 step = scale(1, self.pos) 749 results = [] 750 for value in self.args["values"]: 751 if value < 0: 752 value = year_length + 1 + value 753 current = to_tuple(first_day + timedelta(value - 1), 3) 754 next = update(current, step) 755 756 # To support setpos, only current and next bound the search, not 757 # the period in addition. 758 759 results += self.materialise_item(current, current, next, counter, inclusive=inclusive) 760 761 # Extract selected positions and remove out-of-period instances. 762 763 if setpos: 764 results = self.select_positions(results, setpos) 765 766 return self.filter_by_period(results, start, end, inclusive) 767 768 special_enum_levels = { 769 "BYDAY" : WeekDayFilter, 770 "BYMONTHDAY" : MonthDayFilter, 771 "BYYEARDAY" : YearDayFilter, 772 } 773 774 # Public functions. 775 776 def connect_selectors(selectors): 777 778 """ 779 Make the 'selectors' reference each other in a hierarchy so that 780 materialising the principal selector causes the more specific ones to be 781 employed in the operation. 782 """ 783 784 current = selectors[0] 785 for selector in selectors[1:]: 786 current.selecting = selector 787 current = selector 788 return selectors[0] 789 790 def get_selector(dt, qualifiers): 791 792 """ 793 Combine the initial datetime 'dt' with the given 'qualifiers', returning an 794 object that can be used to select recurrences described by the 'qualifiers'. 795 """ 796 797 dt = to_tuple(dt) 798 return connect_selectors(combine_datetime_with_qualifiers(dt, qualifiers)) 799 800 def get_rule(dt, rule): 801 802 """ 803 Using the given initial datetime 'dt', interpret the 'rule' (a semicolon- 804 separated collection of "key=value" strings), and return the resulting 805 selector object. 806 """ 807 808 if not isinstance(rule, tuple): 809 rule = rule.split(";") 810 qualifiers = get_qualifiers(rule) 811 return get_selector(dt, qualifiers) 812 813 # vim: tabstop=4 expandtab shiftwidth=4