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