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