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