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