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 collections import OrderedDict 57 from datetime import date, datetime, timedelta 58 import operator 59 60 # Frequency levels, specified by FREQ in iCalendar. 61 # Enumeration levels, employed by BY... qualifiers. 62 # Labels, employed in string representations of selectors. 63 # Datetime tuple lengths. 64 # The first/lowest values at each resolution. 65 # Parent resolutions, employed for repetition at a lower resolution than selected. 66 67 resolutions = ( 68 # Frequency # Enumeration # Label # Length # First # Parent 69 ("YEARLY", None, "YEARS", 1, 0, None), # nothing beyond years 70 ("MONTHLY", "BYMONTH", "MONTHS", 2, 1, 0), # months -> years 71 ("WEEKLY", "BYWEEKNO", "WEEKS", 3, 1, 1), # weeks -> months 72 (None, "BYYEARDAY", "YEARDAYS", 3, 1, 0), # yeardays -> years 73 (None, "BYMONTHDAY", "MONTHDAYS", 3, 1, 1), # monthdays -> months 74 ("DAILY", "BYDAY", "DAYS", 3, 1, 2), # weekdays -> weeks 75 ("HOURLY", "BYHOUR", "HOURS", 4, 0, 5), # hours -> days 76 ("MINUTELY", "BYMINUTE", "MINUTES", 5, 0, 6), # minutes -> hours 77 ("SECONDLY", "BYSECOND", "SECONDS", 6, 0, 7), # seconds -> minutes 78 ) 79 80 freq_levels = map(lambda x: x[0], resolutions) 81 enum_levels = map(lambda x: x[1], resolutions) 82 level_labels = map(lambda x: x[2], resolutions) 83 lengths = map(lambda x: x[3], resolutions) 84 positions = map(lambda x: x[3] - 1, resolutions) 85 firstvalues = map(lambda x: x[4], resolutions) 86 enum_parent_levels = map(lambda x: x[5], resolutions) 87 88 # Add labels corresponding to negative indexes. 89 90 level_labels += ("COUNT", "UNTIL", "DTSTART") 91 92 # Symbols corresponding to resolution levels. 93 94 YEARS, MONTHS, WEEKS, DAYS, HOURS, MINUTES, SECONDS = 0, 1, 2, 5, 6, 7, 8 95 96 # Special levels for day frequency qualifiers. 97 98 YEARDAYS, MONTHDAYS = 3, 4 99 100 # Special levels used by non-qualifier-originating selectors. 101 102 COUNT, UNTIL, DTSTART, BYSETPOS = -3, -2, -1, None 103 104 # Levels defining days. 105 106 daylevels = map(lambda t: t[0], filter(lambda t: t[1] == 3, enumerate(lengths))) 107 108 # Map from qualifiers to interval multiples. Here, weeks are defined as 7 days. 109 110 multiples = {"WEEKLY" : 7} 111 112 # Make dictionaries mapping qualifiers to levels. 113 114 freq = {} 115 for i, level in enumerate(freq_levels): 116 if level: 117 freq[level] = i 118 119 enum = {} 120 for i, level in enumerate(enum_levels): 121 if level: 122 enum[level] = i 123 124 # Weekdays: name -> 1-based value 125 126 weekday_values = ["MO", "TU", "WE", "TH", "FR", "SA", "SU"] 127 128 weekdays = OrderedDict() 129 for i, weekday in enumerate(weekday_values): 130 weekdays[weekday] = i + 1 131 132 # Functions for structuring the recurrences. 133 134 def get_next(it): 135 136 "Return the next value from iterator 'it' or None if no more values exist." 137 138 try: 139 return it.next() 140 except StopIteration: 141 return None 142 143 def get_parameters(values): 144 145 "Return parameters from the given list of 'values'." 146 147 d = {} 148 if not values: 149 return d 150 151 for value in values: 152 try: 153 key, value = value.split("=", 1) 154 d[key] = value 155 except ValueError: 156 continue 157 return d 158 159 def get_qualifiers(values): 160 161 """ 162 Process the list of 'values' of the form "key=value", returning a list of 163 qualifiers of the form (qualifier name, args). 164 """ 165 166 qualifiers = [] 167 frequency = None 168 interval = 1 169 keys = set() 170 171 for value in values: 172 173 # Ignore qualifiers without values. 174 175 try: 176 key, value = value.split("=", 1) 177 except ValueError: 178 continue 179 180 # Ignore duplicate qualifiers. 181 182 if key in keys: 183 continue 184 185 keys.add(key) 186 187 # Accept frequency indicators as qualifiers. 188 189 if key == "FREQ" and freq.has_key(value): 190 qualifier = frequency = (value, {}) 191 192 # Accept interval indicators for frequency qualifier parameterisation. 193 194 elif key == "INTERVAL": 195 interval = max(1, int(value)) 196 continue 197 198 # Accept result set selection, truncation and enumerators as qualifiers. 199 200 elif key in ("BYSETPOS", "COUNT") or enum.has_key(key): 201 values = get_qualifier_values(key, value) 202 203 # Ignore bad qualifier values. 204 205 if not values: 206 continue 207 208 qualifier = (key, {"values" : values}) 209 210 # Accept until datetimes. 211 # NOTE: This should be a UTC datetime unless DTSTART is a date or 212 # NOTE: floating datetime. 213 214 elif key == "UNTIL": 215 try: 216 # YYYYMMDD 217 218 if len(value) == 8: 219 end = map(int, (value[:4], value[4:6], value[6:])) 220 221 # YYYYMMDDTHHMMSS[Z] 222 223 elif len(value) in (15, 16): 224 end = map(int, (value[:4], value[4:6], value[6:8], value[9:11], value[11:13], value[13:15])) 225 226 else: 227 continue 228 229 qualifier = (key, {"end" : tuple(end)}) 230 231 except ValueError: 232 continue 233 234 # Ignore other items. 235 236 else: 237 continue 238 239 qualifiers.append(qualifier) 240 241 # Parameterise any frequency qualifier with the interval. 242 243 if frequency: 244 frequency[1]["interval"] = interval 245 246 return qualifiers 247 248 def get_qualifier_values(qualifier, value): 249 250 """ 251 For the given 'qualifier', process the 'value' string, returning a list of 252 suitable values. 253 """ 254 255 values = [] 256 257 for v in value.split(","): 258 try: 259 # For non-weekday selection, obtain a list of numbers, each in a tuple. 260 261 if qualifier != "BYDAY": 262 to_check = (int(v),) 263 264 # For weekday selection, obtain a list of tuples containing the weekday 265 # and instance number. 266 267 else: 268 # Split the two-letter weekday code from the preceding text. 269 270 index, weekday = v[:-2], v[-2:] 271 to_check = (weekday, int_or_empty(index)) 272 273 except ValueError: 274 return None 275 276 checked = check_values(qualifier, to_check) 277 278 if not checked: 279 return None 280 281 # Get single values for non-weekday details. 282 283 if qualifier != "BYDAY": 284 checked = checked[0] 285 286 values.append(checked) 287 288 return values 289 290 def int_or_empty(value): 291 292 "Return 'value' as an integer or None if null. Raises ValueError." 293 294 if value: 295 return int(value) 296 else: 297 return None 298 299 def make_selectors(qualifiers): 300 301 """ 302 Obtain 'qualifiers' in order of increasing resolution, producing and 303 returning selector objects corresponding to the qualifiers. 304 """ 305 306 l = [] 307 308 # Obtain selectors for the qualifiers. 309 310 for qualifier, args in qualifiers: 311 selector = new_selector(qualifier, args) 312 l.append(selector) 313 314 return sort_selectors(l) 315 316 def new_selector(qualifier, args=None): 317 318 "Return a selector for 'qualifier' and 'args'." 319 320 # Distinguish between enumerators, used to select particular periods, 321 # and frequencies, used to select repeating periods. 322 323 if enum.has_key(qualifier): 324 selector = special_enum_levels.get(qualifier, Enum) 325 return selector(enum[qualifier], args, qualifier) 326 327 # Create a selector that must be updated with the maximum resolution. 328 329 elif qualifier == "BYSETPOS": 330 return PositionSelector(BYSETPOS, args, "BYSETPOS") 331 332 elif qualifier == "COUNT": 333 return LimitSelector(COUNT, args, "COUNT") 334 335 elif qualifier == "UNTIL": 336 return UntilSelector(UNTIL, args, "UNTIL") 337 338 else: 339 return Pattern(freq[qualifier], args, qualifier) 340 341 def insert_start_selector(selectors, dt): 342 343 "Return a copy of 'selectors' incorporating 'dt'." 344 345 selectors = selectors + [StartSelector(DTSTART, {"start" : dt}, "DTSTART")] 346 selectors.sort(key=selector_sort_key) 347 return selectors 348 349 def sort_selectors(selectors): 350 351 "Sort 'selectors' in order of increasing resolution." 352 353 if not selectors: 354 return selectors 355 356 max_level = max(map(lambda selector: selector.level or 0, selectors)) 357 358 # Update the result set selector at the maximum resolution. 359 360 for selector in selectors: 361 if isinstance(selector, PositionSelector): 362 selector.set_level(max_level) 363 364 selectors.sort(key=selector_sort_key) 365 return selectors 366 367 def selector_sort_key(selector): 368 369 "Produce a sort key for 'selector'." 370 371 # Make BYSETPOS sort earlier than the enumeration it modifies. 372 373 if selector.qualifier == "BYSETPOS": 374 sublevel = 0 375 376 # Other BY... qualifiers sort earlier than selectors at the same resolution 377 # even though such things as "FREQ=HOURLY;BYHOUR=10" do not make much sense. 378 379 elif selector.qualifier.startswith("BY"): 380 sublevel = 1 381 else: 382 sublevel = 2 383 384 return (selector.level, sublevel) 385 386 def get_value_ranges(qualifier): 387 388 """ 389 Return value ranges for 'qualifier'. Each range is either given by a tuple 390 indicating the inclusive start and end values or by a list enumerating the 391 values. 392 """ 393 394 # Provide ranges for the numeric value of each qualifier. 395 396 if qualifier == "BYMONTH": 397 return [(-12, -1), (1, 12)], 398 elif qualifier == "BYWEEKNO": 399 return [(-53, -1), (1, 53)], 400 elif qualifier == "BYYEARDAY": 401 return [(-366, -1), (1, 366)], 402 elif qualifier == "BYMONTHDAY": 403 return [(-31, -1), (1, 31)], 404 elif qualifier == "BYHOUR": 405 return [(0, 23)], 406 elif qualifier == "BYMINUTE": 407 return [(0, 59)], 408 elif qualifier == "BYSECOND": 409 return [(0, 60)], 410 411 # Provide ranges for the weekday value and index. 412 413 elif qualifier == "BYDAY": 414 return [weekdays], [(-53, -1), (1, 53), None] 415 416 return None 417 418 def check_values(qualifier, values): 419 420 """ 421 Check for 'qualifier' the given 'values', returning checked values that may 422 be converted or updated. 423 """ 424 425 ranges = get_value_ranges(qualifier) 426 427 if not ranges: 428 return values 429 430 # Match each value against each range specification. 431 432 checked = [] 433 434 for v, value_ranges in zip(values, ranges): 435 436 # Return None if no match occurred for the value. 437 438 try: 439 checked.append(check_value_in_ranges(v, value_ranges)) 440 except ValueError: 441 return None 442 443 # Return the checked values. 444 445 return checked 446 447 def check_value_in_ranges(value, value_ranges): 448 449 """ 450 Check the given 'value' against the given 'value_ranges'. Return the 451 checked value, possibly converted or updated, or raise ValueError if the 452 value was not suitable. 453 """ 454 455 if not value_ranges: 456 return value 457 458 for value_range in value_ranges: 459 460 # Test actual ranges. 461 462 if isinstance(value_range, tuple): 463 start, end = value_range 464 if start <= value <= end: 465 return value 466 467 # Test enumerations. 468 469 elif isinstance(value_range, list): 470 if value in value_range: 471 return value 472 473 # Test mappings. 474 475 elif isinstance(value_range, dict): 476 if value_range.has_key(value): 477 return value_range[value] 478 479 # Test value matches. 480 481 elif value == value_range: 482 return value 483 484 raise ValueError, value 485 486 def get_datetime_structure(datetime): 487 488 "Return the structure of 'datetime' for recurrence production." 489 490 l = [] 491 offset = 0 492 493 for pos, value in enumerate(datetime): 494 495 # At the day number, adjust the frequency level offset to reference 496 # days (and then hours, minutes, seconds). 497 498 if pos == 2: 499 offset = 3 500 501 l.append(Enum(pos + offset, {"values" : [value]}, "DT")) 502 503 return l 504 505 def combine_datetime_with_selectors(datetime, selectors): 506 507 """ 508 Combine 'datetime' with 'selectors' to produce a structure for recurrence 509 production. 510 511 Initial datetime values appearing at broader resolutions than any qualifiers 512 are ignored, since their details will be used when materialising the 513 results. 514 515 Qualifiers are accumulated in order to define a selection. Datetime values 516 occurring at the same resolution as qualifiers are ignored. 517 518 Any remaining datetime values are introduced as enumerators, provided that 519 they do not conflict with qualifiers. For example, specific day values 520 conflict with day selectors and weekly qualifiers. 521 522 The purpose of the remaining datetime values is to define a result within 523 a period selected by the most precise qualifier. For example, the selection 524 of a day and month in a year recurrence. 525 """ 526 527 iter_dt = iter(get_datetime_structure(datetime)) 528 iter_sel = iter(selectors) 529 530 l = [] 531 532 from_dt = get_next(iter_dt) 533 from_sel = get_next(iter_sel) 534 have_sel = False 535 held_dt = [] 536 537 # Consume from both lists, merging entries. 538 539 while from_sel: 540 level = from_sel.level 541 542 # Datetime value at wider resolution. 543 544 if from_dt and from_dt.level < level: 545 held_dt.append(from_dt) 546 from_dt = get_next(iter_dt) 547 548 # Qualifier at wider or same resolution as datetime value. 549 550 else: 551 if not have_sel: 552 have_sel = add_initial_selector(from_sel, level, l) 553 554 # Introduce any held datetime values, if appropriate. 555 556 elif can_restrict_selector(from_sel): 557 for from_held_dt in held_dt: 558 add_datetime_selector(from_held_dt, l) 559 560 held_dt = [] 561 562 # Add the qualifier to the combined list. 563 564 if isinstance(from_sel, Pattern): 565 if not have_sel: 566 have_sel = from_sel.first = True 567 568 l.append(from_sel) 569 570 # Datetime value at same resolution. 571 572 if from_dt and from_dt.level == level: 573 from_dt = get_next(iter_dt) 574 575 # Get the next qualifier. 576 577 from_sel = get_next(iter_sel) 578 579 # Complete the list by adding remaining datetime enumerators. 580 581 while from_dt: 582 add_datetime_selector(from_dt, l) 583 from_dt = get_next(iter_dt) 584 585 return l 586 587 def can_restrict_selector(from_sel): 588 589 "Return whether 'from_sel' can be restricted using datetime information." 590 591 return not isinstance(from_sel, Pattern) and from_sel.qualifier != "BYDAY" 592 593 def add_initial_selector(from_sel, level, l): 594 595 """ 596 Take the selector 'from_sel' at the given resolution 'level', using it to 597 create an initial selector, adding it to the combined list 'l' if required. 598 599 Return whether a frequency selector has been introduced. 600 """ 601 602 if isinstance(from_sel, Enum) and level > 0: 603 parent_level = enum_parent_levels[level] 604 repeat = Pattern(parent_level, {"interval" : 1}, freq_levels[parent_level], first=True) 605 l.append(repeat) 606 return True 607 608 return False 609 610 def add_datetime_selector(from_dt, l): 611 612 """ 613 Take the selector 'from_dt' and add it to the list 'l' if it does not 614 conflict with any day-level qualifiers already in 'l'. 615 """ 616 617 if not l or from_dt.level != freq["DAILY"] or l[-1].level not in daylevels: 618 l.append(from_dt) 619 620 def get_multiple(qualifier): 621 622 "Return the time unit multiple for 'qualifier'." 623 624 return multiples.get(qualifier, 1) 625 626 # Datetime arithmetic. 627 628 def is_year_only(t): 629 630 "Return if 't' describes a year." 631 632 return len(t) == lengths[YEARS] 633 634 def is_month_only(t): 635 636 "Return if 't' describes a month within a year." 637 638 return len(t) == lengths[MONTHS] 639 640 def start_of_year(t): 641 642 "Return the start of the year referenced by 't'." 643 644 return (t[0], 1, 1) 645 646 def end_of_year(t): 647 648 "Return the end of the year referenced by 't'." 649 650 return (t[0], 12, 31) 651 652 def start_of_month(t): 653 654 "Return the start of the month referenced by 't'." 655 656 year, month = t[:2] 657 return (year, month, 1) 658 659 def end_of_month(t): 660 661 "Return the end of the month referenced by 't'." 662 663 year, month = t[:2] 664 return update(update((year, month, 1), (0, 1, 0)), (0, 0, -1)) 665 666 def day_in_year(t, number): 667 668 "Return the day in the year referenced by 't' with the given 'number'." 669 670 return to_tuple(date(*start_of_year(t)) + timedelta(number - 1)) 671 672 def get_year_length(t): 673 674 "Return the length of the year referenced by 't'." 675 676 first_day = date(*start_of_year(t)) 677 last_day = date(*end_of_year(t)) 678 return (last_day - first_day).days + 1 679 680 def get_weekday(t): 681 682 "Return the 1-based weekday for the month referenced by 't'." 683 684 year, month = t[:2] 685 return monthrange(year, month)[0] + 1 686 687 def get_ordered_weekdays(t): 688 689 """ 690 Return the 1-based weekday sequence describing the first week of the month 691 referenced by 't'. 692 """ 693 694 first = get_weekday(t) 695 return range(first, 8) + range(1, first) 696 697 def get_last_weekday_instance(weekday, first_day, last_day): 698 699 """ 700 Return the last instance number for 'weekday' within the period from 701 'first_day' to 'last_day' inclusive. 702 703 Here, 'weekday' is 1-based (starting on Monday), the returned limit is 704 1-based. 705 """ 706 707 weekday0 = get_first_day(first_day, weekday) 708 days = (date(*last_day) - weekday0).days 709 return days / 7 + 1 710 711 def constrain_to_month(t): 712 713 "Return 't' corrected to ensure that the day number is within the month." 714 715 year, month, day = t[:3] 716 time = t[3:] 717 max_day = monthrange(year, month)[1] 718 day = min(max_day, day) 719 return tuple((year, month) + (day,) + time) 720 721 def within_month(t): 722 723 """ 724 Return whether 't' is within the permissible day range of the given month, 725 if 't' describes a day or datetime. Otherwise, return a true value for years 726 and months. 727 """ 728 729 if len(t) < 3: 730 return True 731 732 year, month, day = t[:3] 733 max_day = monthrange(year, month)[1] 734 return day <= max_day 735 736 def limit_value(t, level): 737 738 "Return 't' trimmed in resolution to the indicated resolution 'level'." 739 740 pos = positions[level] 741 return t[:pos + 1] 742 743 def make_value(t, level, value): 744 745 """ 746 Return 't' trimmed in resolution to the indicated resolution 'level', 747 extended by setting 'value' at the given resolution. 748 """ 749 750 pos = positions[level] 751 return t[:pos] + (value,) 752 753 def scale(interval, level): 754 755 """ 756 Scale the given 'interval' value in resolution to the indicated resolution 757 'level', returning a tuple with leading zero elements and 'interval' at the 758 stated position. 759 """ 760 761 pos = positions[level] 762 return (0,) * pos + (interval,) 763 764 def get_seconds(t): 765 766 "Convert the sub-day part of 't' into seconds." 767 768 t = t + (0,) * (6 - len(t)) 769 return (t[3] * 60 + t[4]) * 60 + t[5] 770 771 def update(t, step): 772 773 "Update 't' by 'step' at the resolution of 'step'." 774 775 i = len(step) 776 777 # Years only. 778 779 if i == 1: 780 return (t[0] + step[0],) + tuple(t[1:]) 781 782 # Years and months. 783 784 elif i == 2: 785 month = t[1] + step[1] 786 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 787 788 # Dates and datetimes. 789 790 else: 791 updated_for_months = constrain_to_month(update(t, step[:2])) 792 d = datetime(*updated_for_months) 793 794 # Dates only. 795 796 if i == 3: 797 s = timedelta(step[2]) 798 799 # Datetimes. 800 801 else: 802 s = timedelta(step[2], get_seconds(step)) 803 804 return to_tuple(d + s)[:len(t)] 805 806 def to_tuple(d): 807 808 "Return date or datetime 'd' as a tuple." 809 810 if not isinstance(d, date): 811 return d 812 if isinstance(d, datetime): 813 n = 6 814 else: 815 n = 3 816 return d.timetuple()[:n] 817 818 def get_first_day(first_day, weekday): 819 820 """ 821 Return the first occurrence at or after 'first_day' of 'weekday' as a date 822 instance. 823 """ 824 825 first_day = date(*first_day) 826 first_weekday = first_day.isoweekday() 827 if first_weekday > weekday: 828 return first_day + timedelta(7 - first_weekday + weekday) 829 else: 830 return first_day + timedelta(weekday - first_weekday) 831 832 def get_last_day(last_day, weekday): 833 834 """ 835 Return the last occurrence at or before 'last_day' of 'weekday' as a date 836 instance. 837 """ 838 839 last_day = date(*last_day) 840 last_weekday = last_day.isoweekday() 841 if last_weekday < weekday: 842 return last_day - timedelta(last_weekday + 7 - weekday) 843 else: 844 return last_day - timedelta(last_weekday - weekday) 845 846 # Value expansion and sorting. 847 848 def sort_values(values, limit=None): 849 850 """ 851 Sort the given 'values' using 'limit' to determine the positions of negative 852 values. 853 """ 854 855 # Convert negative values to positive values according to the value limit. 856 857 if limit is not None: 858 l = map(lambda x, limit=limit: x < 0 and x + 1 + limit or x, values) 859 else: 860 l = values[:] 861 862 l.sort() 863 return l 864 865 def compare_weekday_selectors(x, y, weekdays): 866 867 """ 868 Compare 'x' and 'y' values of the form (weekday number, instance number) 869 using 'weekdays' to define an ordering of the weekday numbers. 870 """ 871 872 return cmp((x[1], weekdays.index(x[0])), (y[1], weekdays.index(y[0]))) 873 874 def sort_weekdays(values, first_day, last_day): 875 876 """ 877 Return a sorted copy of the given 'values', each having the form (weekday 878 number, instance number), where 'first_day' indicates the start of the 879 period in which these values apply, and where 'last_day' indicates the end 880 of the period. 881 """ 882 883 weekdays = get_ordered_weekdays(first_day) 884 885 # Expand the values to incorporate specific weekday instances. 886 887 l = [] 888 889 for weekday, index in values: 890 891 # Obtain the last instance number of the weekday in the period. 892 893 limit = get_last_weekday_instance(weekday, first_day, last_day) 894 895 # For specific instances, convert negative selections. 896 897 if index is not None: 898 l.append((weekday, index < 0 and index + 1 + limit or index)) 899 900 # For None, introduce selections for all instances of the weekday. 901 902 else: 903 index = 1 904 while index <= limit: 905 l.append((weekday, index)) 906 index += 1 907 908 # Sort the values so that the resulting dates are ordered. 909 910 fn = lambda x, y, weekdays=weekdays: compare_weekday_selectors(x, y, weekdays) 911 l.sort(cmp=fn) 912 return l 913 914 def convert_positions(setpos): 915 916 "Convert 'setpos' to 0-based indexes." 917 918 l = [] 919 if setpos: 920 for pos in setpos: 921 index = pos < 0 and pos or pos - 1 922 l.append(index) 923 return l 924 925 # Classes for producing instances from recurrence structures. 926 927 class Selector: 928 929 "A generic selector." 930 931 def __init__(self, level, args, qualifier, selecting=None): 932 933 """ 934 Initialise at the given 'level' a selector employing the given 'args' 935 defined in the interpretation of recurrence rule qualifiers, with the 936 'qualifier' being the name of the rule qualifier, and 'selecting' being 937 an optional selector used to find more specific instances from those 938 found by this selector. 939 """ 940 941 self.level = level 942 self.args = args or {} 943 self.qualifier = qualifier 944 self.selecting = selecting 945 946 def __repr__(self): 947 return "%s(%s, %r, %r)" % (self.__class__.__name__, 948 level_labels[self.level], 949 self.args, self.qualifier) 950 951 def select(self, start, end, inclusive=False): 952 953 """ 954 Return an iterator over instances starting at 'start' and continuing up 955 to but not including any at 'end' or later. 956 957 If 'inclusive' is specified, the selection of instances will include the 958 end of the search period if present in the results. 959 """ 960 961 start = to_tuple(start) 962 end = to_tuple(end) 963 return self.materialise_items(start, start, end, inclusive) 964 965 def materialise(self, start, end, inclusive=False): 966 967 """ 968 Starting at 'start', materialise instances up to but not including any 969 at 'end' or later. A list of instances is returned. 970 971 If 'inclusive' is specified, the selection of instances will include the 972 end of the search period if present in the results. 973 """ 974 975 return list(self.select(start, end, inclusive)) 976 977 def set_values(self, values): 978 self.args["values"] = values 979 980 # Copying and comparison support. 981 982 def as_tuple(self): 983 return self.level, self.args, self.qualifier, self.selecting 984 985 def copy(self): 986 return self.__class__(*self.as_tuple()) 987 988 def __cmp__(self, other): 989 return cmp(self.as_tuple(), other and other.as_tuple()) 990 991 class Pattern(Selector): 992 993 "A selector of time periods according to a repeating pattern." 994 995 def __init__(self, level, args, qualifier, selecting=None, first=False): 996 Selector.__init__(self, level, args, qualifier, selecting) 997 multiple = get_multiple(self.qualifier) 998 self.first = first 999 1000 # Define the scale of a single period. 1001 1002 self.unit_step = scale(multiple, level) 1003 self.update_step() 1004 1005 def update_step(self): 1006 1007 "Update the step between result periods." 1008 1009 multiple = get_multiple(self.qualifier) 1010 interval = self.get_interval() 1011 self.step = scale(interval * multiple, self.level) 1012 1013 def materialise_items(self, context, start, end, inclusive=False): 1014 1015 """ 1016 Bounded by the given 'context', return periods within 'start' to 'end'. 1017 1018 If 'inclusive' is specified, the selection of periods will include those 1019 starting at the end of the search period, if present in the results. 1020 """ 1021 1022 # Employ the context as the current period if this is the first 1023 # qualifier in the selection chain. 1024 1025 if self.first: 1026 current = limit_value(context, self.level) 1027 1028 # Otherwise, obtain the first value at this resolution within the 1029 # context period. 1030 1031 else: 1032 current = make_value(context, self.level, firstvalues[self.level]) 1033 1034 return PatternIterator(self, current, start, end, inclusive, 1035 self.step, self.unit_step) 1036 1037 def get_interval(self): 1038 return self.args.get("interval", 1) 1039 1040 def set_interval(self, interval): 1041 self.args["interval"] = interval 1042 self.update_step() 1043 1044 # Copying and comparison support. 1045 1046 def as_tuple(self): 1047 return self.level, self.args, self.qualifier, self.selecting, self.first 1048 1049 class Enum(Selector): 1050 1051 "A generic value selector." 1052 1053 def __init__(self, level, args, qualifier, selecting=None): 1054 Selector.__init__(self, level, args, qualifier, selecting) 1055 self.step = scale(1, level) 1056 1057 def materialise_items(self, context, start, end, inclusive=False): 1058 return EnumIterator(self, context, start, end, inclusive, self.step, 1059 self.get_values()) 1060 1061 def get_values(self, limit=None): 1062 return sort_values(self.args["values"], limit) 1063 1064 class WeekDayFilter(Enum): 1065 1066 "A selector of instances specified in terms of day numbers." 1067 1068 def __init__(self, level, args, qualifier, selecting=None): 1069 Selector.__init__(self, level, args, qualifier, selecting) 1070 self.step = scale(1, WEEKS) 1071 1072 def materialise_items(self, context, start, end, inclusive=False): 1073 1074 # Get weekdays in the year. 1075 1076 if is_year_only(context): 1077 first_day = start_of_year(context) 1078 last_day = end_of_year(context) 1079 1080 # Get weekdays in the month. 1081 1082 elif is_month_only(context): 1083 first_day = start_of_month(context) 1084 last_day = end_of_month(context) 1085 1086 # Get weekdays in the week. 1087 1088 else: 1089 current = context 1090 return WeekDayIterator(self, current, start, end, inclusive, self.step, 1091 self.get_weekdays()) 1092 1093 current = first_day 1094 values = sort_weekdays(self.args["values"], first_day, last_day) 1095 return WeekDayGeneralIterator(self, current, start, end, inclusive, 1096 self.step, values) 1097 1098 def get_values(self): 1099 1100 """ 1101 Return a sequence of (value, index) tuples selecting weekdays in the 1102 applicable period. Each value is a 1-based index representing a weekday. 1103 """ 1104 1105 return self.args["values"] 1106 1107 def get_weekdays(self): 1108 1109 "Return only the 1-based weekday indexes." 1110 1111 values = [] 1112 for value, index in self.args["values"]: 1113 values.append(value) 1114 return values 1115 1116 class MonthDayFilter(Enum): 1117 1118 "A selector of month days." 1119 1120 def materialise_items(self, context, start, end, inclusive=False): 1121 last_day = end_of_month(context)[2] 1122 return EnumIterator(self, context, start, end, inclusive, self.step, 1123 self.get_values(last_day)) 1124 1125 class YearDayFilter(Enum): 1126 1127 "A selector of days in years." 1128 1129 def materialise_items(self, context, start, end, inclusive=False): 1130 first_day = start_of_year(context) 1131 year_length = get_year_length(context) 1132 return YearDayFilterIterator(self, first_day, start, end, inclusive, self.step, 1133 self.get_values(year_length)) 1134 1135 class LimitSelector(Selector): 1136 1137 "A result set limit selector." 1138 1139 def materialise_items(self, context, start, end, inclusive=False): 1140 return LimitIterator(self, context, start, end, inclusive, self.get_limit()) 1141 1142 def get_limit(self): 1143 return self.args["values"][0] 1144 1145 def set_limit(self, limit): 1146 self.args["values"] = [limit] 1147 1148 class PositionSelector(Selector): 1149 1150 "A result set position selector." 1151 1152 def __init__(self, level, args, qualifier, selecting=None): 1153 Selector.__init__(self, level, args, qualifier, selecting) 1154 if level is not None: 1155 self.set_level(level) 1156 else: 1157 self.step = None 1158 1159 def set_level(self, level): 1160 self.level = level 1161 self.step = scale(1, self.level) 1162 1163 def materialise_items(self, context, start, end, inclusive=False): 1164 return PositionIterator(self, context, start, end, inclusive, self.step, 1165 self.get_positions()) 1166 1167 def get_positions(self): 1168 return convert_positions(sort_values(self.args["values"])) 1169 1170 def set_positions(self, positions): 1171 self.args["values"] = positions 1172 1173 class StartSelector(Selector): 1174 1175 "A selector ensuring that the start occurrence is included." 1176 1177 def materialise_items(self, context, start, end, inclusive=False): 1178 return StartIterator(self, context, start, end, inclusive, 1179 self.get_start()) 1180 1181 def get_start(self): 1182 return self.args["start"] 1183 1184 class UntilSelector(Selector): 1185 1186 "A selector ensuring that the until datetime is not passed." 1187 1188 def materialise_items(self, context, start, end, inclusive=False): 1189 return UntilIterator(self, context, start, end, inclusive, 1190 self.get_end()) 1191 1192 def get_end(self): 1193 return self.args["end"] 1194 1195 special_enum_levels = { 1196 "BYDAY" : WeekDayFilter, 1197 "BYMONTHDAY" : MonthDayFilter, 1198 "BYYEARDAY" : YearDayFilter, 1199 } 1200 1201 # Iterator classes. 1202 1203 class SelectorIterator: 1204 1205 "An iterator over selected data." 1206 1207 def __init__(self, selector, current, start, end, inclusive): 1208 1209 """ 1210 Define an iterator having the 'current' point in time, 'start' and 'end' 1211 limits, and whether the selection is 'inclusive'. 1212 """ 1213 1214 self.selector = selector 1215 self.current = current 1216 self.start = start 1217 self.end = end 1218 self.inclusive = inclusive 1219 1220 # Iterator over selections within this selection. 1221 1222 self.iterator = None 1223 1224 def __iter__(self): 1225 return self 1226 1227 def next_item(self, earliest, next): 1228 1229 """ 1230 Given the 'earliest' acceptable instance and the 'next' instance, return 1231 a list of result items. 1232 1233 Where no selection within the current instance occurs, the current 1234 instance will be returned as a result if the same or later than the 1235 earliest acceptable instance. 1236 """ 1237 1238 # Obtain an item from a selector operating within this selection. 1239 1240 selecting = self.selector.selecting 1241 1242 if selecting: 1243 1244 # Obtain an iterator for any selector within the current period. 1245 1246 if not self.iterator: 1247 self.iterator = selecting.materialise_items(self.current, 1248 earliest, next, self.inclusive) 1249 1250 # Attempt to obtain and return a value. 1251 1252 return self.iterator.next() 1253 1254 # Return items within this selection. 1255 1256 else: 1257 return self.current 1258 1259 def filter_by_period(self, result): 1260 1261 "Return whether 'result' occurs within the selection period." 1262 1263 return (self.inclusive and result <= self.end or result < self.end) and \ 1264 self.start <= result 1265 1266 def at_limit(self): 1267 1268 """ 1269 Obtain periods before the end. If inclusive and selecting in the final 1270 selector, obtain the period at the end. 1271 """ 1272 1273 inclusive = self.inclusive and not self.selector.selecting 1274 return not inclusive and self.current == self.end or \ 1275 self.current > self.end 1276 1277 class PatternIterator(SelectorIterator): 1278 1279 "An iterator for a general selection pattern." 1280 1281 def __init__(self, selector, current, start, end, inclusive, step, unit_step): 1282 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1283 self.step = step 1284 self.unit_step = unit_step 1285 1286 def next(self): 1287 1288 "Return the next value." 1289 1290 while not self.at_limit(): 1291 1292 # Increment the current datetime by the step for the next period. 1293 1294 next = update(self.current, self.step) 1295 1296 # Determine the end point of the current period. 1297 1298 current_end = update(self.current, self.unit_step) 1299 1300 # Obtain any period or periods within the bounds defined by the 1301 # current period and any contraining start and end points. 1302 1303 try: 1304 result = self.next_item(max(self.current, self.start), 1305 min(current_end, self.end)) 1306 1307 # Obtain the next period if not selecting within this period. 1308 1309 if not self.selector.selecting: 1310 self.current = next 1311 1312 # Filter out periods. 1313 1314 if self.filter_by_period(result): 1315 return result 1316 1317 # Move on to the next instance. 1318 1319 except StopIteration: 1320 self.current = next 1321 self.iterator = None 1322 1323 raise StopIteration 1324 1325 class WeekDayIterator(SelectorIterator): 1326 1327 "An iterator over weekday selections in week periods." 1328 1329 def __init__(self, selector, current, start, end, inclusive, step, values): 1330 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1331 self.step = step 1332 self.values = values 1333 1334 def next(self): 1335 1336 "Return the next value." 1337 1338 while not self.at_limit(): 1339 1340 # Increment the current datetime by the step for the next period. 1341 1342 next = update(self.current, self.step) 1343 1344 # Determine whether the day is one chosen. 1345 1346 if date(*self.current).isoweekday() in self.values: 1347 try: 1348 result = self.next_item(max(self.current, self.start), 1349 min(next, self.end)) 1350 1351 # Obtain the next period if not selecting within this period. 1352 1353 if not self.selector.selecting: 1354 self.current = next 1355 1356 return result 1357 1358 # Move on to the next instance. 1359 1360 except StopIteration: 1361 self.current = next 1362 self.iterator = None 1363 1364 else: 1365 self.current = next 1366 self.iterator = None 1367 1368 raise StopIteration 1369 1370 class EnumIterator(SelectorIterator): 1371 1372 "An iterator over specific value selections." 1373 1374 def __init__(self, selector, current, start, end, inclusive, step, values): 1375 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1376 self.step = step 1377 1378 # Derive selected periods from a base and the indicated values. 1379 1380 self.base = current 1381 1382 # Iterate over the indicated period values. 1383 1384 self.values = iter(values) 1385 self.value = None 1386 1387 def get_selected_period(self): 1388 1389 "Return the period indicated by the current value." 1390 1391 t = make_value(self.base, self.selector.level, self.value) 1392 1393 if not within_month(t): 1394 raise StopIteration 1395 1396 return t 1397 1398 def next(self): 1399 1400 "Return the next value." 1401 1402 while True: 1403 1404 # Find each of the given selected values. 1405 1406 if not self.selector.selecting or self.value is None: 1407 self.value = self.values.next() 1408 1409 try: 1410 # Select a period for each value at the current resolution. 1411 1412 self.current = self.get_selected_period() 1413 next = update(self.current, self.step) 1414 1415 # To support setpos, only current and next bound the search, not 1416 # the period in addition. 1417 1418 return self.next_item(self.current, next) 1419 1420 # Move on to the next instance. 1421 1422 except StopIteration: 1423 self.value = None 1424 self.iterator = None 1425 1426 raise StopIteration 1427 1428 class WeekDayGeneralIterator(EnumIterator): 1429 1430 "An iterator over weekday selections in month and year periods." 1431 1432 def get_selected_period(self): 1433 1434 "Return the day indicated by the current day value." 1435 1436 value, index = self.value 1437 offset = timedelta(7 * (index - 1)) 1438 weekday0 = get_first_day(self.base, value) 1439 return limit_value(to_tuple(weekday0 + offset), DAYS) 1440 1441 class YearDayFilterIterator(EnumIterator): 1442 1443 "An iterator over day-in-year selections." 1444 1445 def get_selected_period(self): 1446 1447 "Return the day indicated by the current day value." 1448 1449 offset = timedelta(self.value - 1) 1450 return limit_value(to_tuple(date(*self.base) + offset), DAYS) 1451 1452 class LimitIterator(SelectorIterator): 1453 1454 "A result set limiting iterator." 1455 1456 def __init__(self, selector, context, start, end, inclusive, limit): 1457 SelectorIterator.__init__(self, selector, context, start, end, inclusive) 1458 self.limit = limit 1459 self.count = 0 1460 1461 def next(self): 1462 1463 "Return the next value." 1464 1465 if self.count < self.limit: 1466 self.count += 1 1467 result = self.next_item(self.start, self.end) 1468 return result 1469 1470 raise StopIteration 1471 1472 class PositionIterator(SelectorIterator): 1473 1474 "An iterator over results, selecting positions." 1475 1476 def __init__(self, selector, context, start, end, inclusive, step, positions): 1477 SelectorIterator.__init__(self, selector, context, start, end, inclusive) 1478 self.step = step 1479 1480 # Positions to select. 1481 1482 self.positions = positions 1483 1484 # Queue to hold values matching the negative position values. 1485 1486 self.queue_length = positions and positions[0] < 0 and abs(positions[0]) or 0 1487 self.queue = [] 1488 1489 # Result position. 1490 1491 self.resultpos = 0 1492 1493 def next(self): 1494 1495 "Return the next value." 1496 1497 while True: 1498 try: 1499 result = self.next_item(self.start, self.end) 1500 1501 # Positive positions can have their values released immediately. 1502 1503 selected = self.resultpos in self.positions 1504 self.resultpos += 1 1505 1506 if selected: 1507 return result 1508 1509 # Negative positions must be held until this iterator completes and 1510 # then be released. 1511 1512 if self.queue_length: 1513 self.queue.append(result) 1514 if len(self.queue) > self.queue_length: 1515 del self.queue[0] 1516 1517 except StopIteration: 1518 1519 # With a queue and positions, attempt to find the referenced 1520 # positions. 1521 1522 if self.queue and self.positions: 1523 index = self.positions[0] 1524 del self.positions[0] 1525 1526 # Only negative positions are used at this point. 1527 1528 if index < 0: 1529 try: 1530 return self.queue[index] 1531 except IndexError: 1532 pass 1533 1534 # With only positive positions remaining, signal the end of 1535 # the collection. 1536 1537 else: 1538 raise 1539 1540 # With no queue or positions remaining, signal the end of the 1541 # collection. 1542 1543 else: 1544 raise 1545 1546 class StartIterator(SelectorIterator): 1547 1548 "An iterator ensuring that the start occurrence is included." 1549 1550 def __init__(self, selector, current, start, end, inclusive, start_dt): 1551 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1552 self.waiting = start_dt 1553 1554 def next(self): 1555 1556 "Return the next value, initially the start period." 1557 1558 # Obtain the next item. 1559 1560 try: 1561 result = self.next_item(self.start, self.end) 1562 except StopIteration: 1563 1564 # With no more values, flush any waiting value. 1565 1566 if self.waiting is not None: 1567 result = self.waiting 1568 self.waiting = None 1569 return result 1570 else: 1571 raise 1572 1573 # Compare with any waiting value. 1574 1575 if self.waiting is not None: 1576 1577 # Produce the waiting value, queue the latest result. 1578 1579 if result != self.waiting: 1580 result, self.waiting = self.waiting, result 1581 1582 # Remove the waiting value if identical to the latest result. 1583 1584 else: 1585 self.waiting = None 1586 1587 return result 1588 1589 class UntilIterator(SelectorIterator): 1590 1591 "An iterator ensuring that the until datetime is not passed." 1592 1593 def __init__(self, selector, current, start, end, inclusive, until): 1594 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1595 self.until = until 1596 1597 def next(self): 1598 1599 "Return the next value, stopping if it is beyond the until limit." 1600 1601 while True: 1602 current = self.next_item(self.start, self.end) 1603 if current >= self.until: 1604 break 1605 return current 1606 1607 raise StopIteration 1608 1609 def connect_selectors(selectors): 1610 1611 """ 1612 Make the 'selectors' reference each other in a hierarchy so that 1613 materialising the principal selector causes the more specific ones to be 1614 employed in the operation. 1615 """ 1616 1617 current = selectors[0] 1618 1619 for selector in selectors[1:]: 1620 current.selecting = selector 1621 current = selector 1622 1623 return selectors[0] 1624 1625 # Public functions. 1626 1627 def get_rule(dt, rule): 1628 1629 """ 1630 Using the given initial datetime 'dt', interpret the 'rule' (a semicolon- 1631 separated collection of "key=value" strings), and return the resulting 1632 selector object. 1633 """ 1634 1635 selectors = get_selectors_for_rule(rule) 1636 return get_selector(dt, selectors) 1637 1638 def get_selector(dt, selectors): 1639 1640 """ 1641 Combine the initial datetime 'dt' with the given 'selectors', returning an 1642 object that can be used to select recurrences described by the 'selectors'. 1643 """ 1644 1645 dt = to_tuple(dt) 1646 selectors = insert_start_selector(selectors, dt) 1647 return connect_selectors(combine_datetime_with_selectors(dt, selectors)) 1648 1649 def get_selectors_for_rule(rule): 1650 1651 """ 1652 Return a list of selectors implementing 'rule', useful for "explaining" how 1653 a rule works. 1654 """ 1655 1656 if not isinstance(rule, tuple): 1657 rule = (rule or "").split(";") 1658 return make_selectors(get_qualifiers(rule)) 1659 1660 def get_selectors_from_selector(selector): 1661 1662 "Return the chain of selectors from 'selector', useful for debugging." 1663 1664 if selector.selecting: 1665 return [selector] + get_selectors_from_selector(selector.selecting) 1666 else: 1667 return [selector] 1668 1669 # vim: tabstop=4 expandtab shiftwidth=4