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 895 multiple = get_multiple(self.qualifier) 896 interval = self.get_interval() 897 898 # Define the step between result periods. 899 900 self.step = scale(interval * multiple, level) 901 902 # Define the scale of a single period. 903 904 self.unit_step = scale(multiple, level) 905 906 def materialise_items(self, context, start, end, inclusive=False): 907 908 """ 909 Bounded by the given 'context', return periods within 'start' to 'end'. 910 911 If 'inclusive' is specified, the selection of periods will include those 912 starting at the end of the search period, if present in the results. 913 """ 914 915 # Employ the context as the current period if this is the first 916 # qualifier in the selection chain. 917 918 if self.first: 919 current = precision(context, self.level) 920 921 # Otherwise, obtain the first value at this resolution within the 922 # context period. 923 924 else: 925 current = precision(context, self.level, firstvalues[self.level]) 926 927 return PatternIterator(self, current, start, end, inclusive, 928 self.step, self.unit_step) 929 930 def get_interval(self): 931 return self.args.get("interval", 1) 932 933 def set_interval(self, interval): 934 self.args["interval"] = interval 935 936 class WeekDayFilter(Selector): 937 938 "A selector of instances specified in terms of day numbers." 939 940 def __init__(self, level, args, qualifier, selecting=None, first=False): 941 Selector.__init__(self, level, args, qualifier, selecting, first) 942 self.step = scale(1, WEEKS) 943 944 def materialise_items(self, context, start, end, inclusive=False): 945 946 # Get weekdays in the year. 947 948 if is_year_only(context): 949 first_day = start_of_year(context) 950 last_day = end_of_year(context) 951 952 # Get weekdays in the month. 953 954 elif is_month_only(context): 955 first_day = start_of_month(context) 956 last_day = end_of_month(context) 957 958 # Get weekdays in the week. 959 960 else: 961 current = context 962 return WeekDayIterator(self, current, start, end, inclusive, self.step, 963 self.get_weekdays()) 964 965 current = first_day 966 values = sort_weekdays(self.args["values"], first_day, last_day) 967 return WeekDayGeneralIterator(self, current, start, end, inclusive, 968 self.step, values) 969 970 def get_values(self): 971 972 """ 973 Return a sequence of (value, index) tuples selecting weekdays in the 974 applicable period. Each value is a 1-based index representing a weekday. 975 """ 976 977 return self.args["values"] 978 979 def get_weekdays(self): 980 981 "Return only the 1-based weekday indexes." 982 983 values = [] 984 for value, index in self.args["values"]: 985 values.append(value) 986 return values 987 988 class Enum(Selector): 989 990 "A generic value selector." 991 992 def __init__(self, level, args, qualifier, selecting=None, first=False): 993 Selector.__init__(self, level, args, qualifier, selecting, first) 994 self.step = scale(1, level) 995 996 def materialise_items(self, context, start, end, inclusive=False): 997 return EnumIterator(self, context, start, end, inclusive, self.step, 998 self.get_values()) 999 1000 def get_values(self, limit=None): 1001 return sort_values(self.args["values"], limit) 1002 1003 class MonthDayFilter(Enum): 1004 1005 "A selector of month days." 1006 1007 def materialise_items(self, context, start, end, inclusive=False): 1008 last_day = end_of_month(context)[2] 1009 return EnumIterator(self, context, start, end, inclusive, self.step, 1010 self.get_values(last_day)) 1011 1012 class YearDayFilter(Enum): 1013 1014 "A selector of days in years." 1015 1016 def materialise_items(self, context, start, end, inclusive=False): 1017 first_day = start_of_year(context) 1018 year_length = get_year_length(context) 1019 return YearDayFilterIterator(self, first_day, start, end, inclusive, self.step, 1020 self.get_values(year_length)) 1021 1022 class LimitSelector(Selector): 1023 1024 "A result set limit selector." 1025 1026 def materialise_items(self, context, start, end, inclusive=False): 1027 return LimitIterator(self, context, start, end, inclusive, self.get_limit()) 1028 1029 def get_limit(self): 1030 return self.args["values"][0] 1031 1032 def set_limit(self, limit): 1033 self.args["values"] = [limit] 1034 1035 class PositionSelector(Selector): 1036 1037 "A result set position selector." 1038 1039 def __init__(self, level, args, qualifier, selecting=None, first=False): 1040 Selector.__init__(self, level, args, qualifier, selecting, first) 1041 self.step = scale(1, level) 1042 1043 def materialise_items(self, context, start, end, inclusive=False): 1044 return PositionIterator(self, context, start, end, inclusive, self.step, 1045 self.get_positions()) 1046 1047 def get_positions(self): 1048 return convert_positions(sort_values(self.args["values"])) 1049 1050 def set_positions(self, positions): 1051 self.args["values"] = positions 1052 1053 class StartSelector(Selector): 1054 1055 "A selector ensuring that the start occurrence is included." 1056 1057 def materialise_items(self, context, start, end, inclusive=False): 1058 return StartIterator(self, context, start, end, inclusive, 1059 self.get_start()) 1060 1061 def get_start(self): 1062 return self.args["start"] 1063 1064 special_enum_levels = { 1065 "BYDAY" : WeekDayFilter, 1066 "BYMONTHDAY" : MonthDayFilter, 1067 "BYYEARDAY" : YearDayFilter, 1068 } 1069 1070 # Iterator classes. 1071 1072 class SelectorIterator: 1073 1074 "An iterator over selected data." 1075 1076 def __init__(self, selector, current, start, end, inclusive): 1077 1078 """ 1079 Define an iterator having the 'current' point in time, 'start' and 'end' 1080 limits, and whether the selection is 'inclusive'. 1081 """ 1082 1083 self.selector = selector 1084 self.current = current 1085 self.start = start 1086 self.end = end 1087 self.inclusive = inclusive 1088 1089 # Iterator over selections within this selection. 1090 1091 self.iterator = None 1092 1093 def __iter__(self): 1094 return self 1095 1096 def next_item(self, earliest, next): 1097 1098 """ 1099 Given the 'earliest' acceptable instance and the 'next' instance, return 1100 a list of result items. 1101 1102 Where no selection within the current instance occurs, the current 1103 instance will be returned as a result if the same or later than the 1104 earliest acceptable instance. 1105 """ 1106 1107 # Obtain an item from a selector operating within this selection. 1108 1109 selecting = self.selector.selecting 1110 1111 if selecting: 1112 1113 # Obtain an iterator for any selector within the current period. 1114 1115 if not self.iterator: 1116 self.iterator = selecting.materialise_items(self.current, 1117 earliest, next, self.inclusive) 1118 1119 # Attempt to obtain and return a value. 1120 1121 return self.iterator.next() 1122 1123 # Return items within this selection. 1124 1125 else: 1126 return self.current 1127 1128 def filter_by_period(self, result): 1129 1130 "Return whether 'result' occurs within the selection period." 1131 1132 return (self.inclusive and result <= self.end or result < self.end) and \ 1133 self.start <= result 1134 1135 def at_limit(self): 1136 1137 "Obtain periods before the end (and also at the end if inclusive)." 1138 1139 return not self.inclusive and self.current == self.end or \ 1140 self.current > self.end 1141 1142 class PatternIterator(SelectorIterator): 1143 1144 "An iterator for a general selection pattern." 1145 1146 def __init__(self, selector, current, start, end, inclusive, step, unit_step): 1147 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1148 self.step = step 1149 self.unit_step = unit_step 1150 1151 def next(self): 1152 1153 "Return the next value." 1154 1155 while not self.at_limit(): 1156 1157 # Increment the current datetime by the step for the next period. 1158 1159 next = update(self.current, self.step) 1160 1161 # Determine the end point of the current period. 1162 1163 current_end = update(self.current, self.unit_step) 1164 1165 # Obtain any period or periods within the bounds defined by the 1166 # current period and any contraining start and end points. 1167 1168 try: 1169 result = self.next_item(max(self.current, self.start), 1170 min(current_end, self.end)) 1171 1172 # Obtain the next period if not selecting within this period. 1173 1174 if not self.selector.selecting: 1175 self.current = next 1176 1177 # Filter out periods. 1178 1179 if self.filter_by_period(result): 1180 return result 1181 1182 # Move on to the next instance. 1183 1184 except StopIteration: 1185 self.current = next 1186 self.iterator = None 1187 1188 raise StopIteration 1189 1190 class WeekDayIterator(SelectorIterator): 1191 1192 "An iterator over weekday selections in week periods." 1193 1194 def __init__(self, selector, current, start, end, inclusive, step, values): 1195 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1196 self.step = step 1197 self.values = values 1198 1199 def next(self): 1200 1201 "Return the next value." 1202 1203 while not self.at_limit(): 1204 1205 # Increment the current datetime by the step for the next period. 1206 1207 next = update(self.current, self.step) 1208 1209 # Determine whether the day is one chosen. 1210 1211 if date(*self.current).isoweekday() in self.values: 1212 try: 1213 result = self.next_item(max(self.current, self.start), 1214 min(next, self.end)) 1215 1216 # Obtain the next period if not selecting within this period. 1217 1218 if not self.selector.selecting: 1219 self.current = next 1220 1221 return result 1222 1223 # Move on to the next instance. 1224 1225 except StopIteration: 1226 self.current = next 1227 self.iterator = None 1228 1229 else: 1230 self.current = next 1231 self.iterator = None 1232 1233 raise StopIteration 1234 1235 class EnumIterator(SelectorIterator): 1236 1237 "An iterator over specific value selections." 1238 1239 def __init__(self, selector, current, start, end, inclusive, step, values): 1240 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1241 self.step = step 1242 1243 # Derive selected periods from a base and the indicated values. 1244 1245 self.base = current 1246 1247 # Iterate over the indicated period values. 1248 1249 self.values = iter(values) 1250 self.value = None 1251 1252 def get_selected_period(self): 1253 1254 "Return the period indicated by the current value." 1255 1256 return precision(self.base, self.selector.level, self.value) 1257 1258 def next(self): 1259 1260 "Return the next value." 1261 1262 while True: 1263 1264 # Find each of the given selected values. 1265 1266 if not self.selector.selecting or self.value is None: 1267 self.value = self.values.next() 1268 1269 # Select a period for each value at the current resolution. 1270 1271 self.current = self.get_selected_period() 1272 next = update(self.current, self.step) 1273 1274 # To support setpos, only current and next bound the search, not 1275 # the period in addition. 1276 1277 try: 1278 return self.next_item(self.current, next) 1279 1280 # Move on to the next instance. 1281 1282 except StopIteration: 1283 self.value = None 1284 self.iterator = None 1285 1286 raise StopIteration 1287 1288 class WeekDayGeneralIterator(EnumIterator): 1289 1290 "An iterator over weekday selections in month and year periods." 1291 1292 def get_selected_period(self): 1293 1294 "Return the day indicated by the current day value." 1295 1296 value, index = self.value 1297 offset = timedelta(7 * (index - 1)) 1298 weekday0 = get_first_day(self.base, value) 1299 return precision(to_tuple(weekday0 + offset), DAYS) 1300 1301 class YearDayFilterIterator(EnumIterator): 1302 1303 "An iterator over day-in-year selections." 1304 1305 def get_selected_period(self): 1306 1307 "Return the day indicated by the current day value." 1308 1309 offset = timedelta(self.value - 1) 1310 return precision(to_tuple(date(*self.base) + offset), DAYS) 1311 1312 class LimitIterator(SelectorIterator): 1313 1314 "A result set limiting iterator." 1315 1316 def __init__(self, selector, context, start, end, inclusive, limit): 1317 SelectorIterator.__init__(self, selector, context, start, end, inclusive) 1318 self.limit = limit 1319 self.count = 0 1320 1321 def next(self): 1322 1323 "Return the next value." 1324 1325 if self.count < self.limit: 1326 self.count += 1 1327 result = self.next_item(self.start, self.end) 1328 return result 1329 1330 raise StopIteration 1331 1332 class PositionIterator(SelectorIterator): 1333 1334 "An iterator over results, selecting positions." 1335 1336 def __init__(self, selector, context, start, end, inclusive, step, positions): 1337 SelectorIterator.__init__(self, selector, context, start, end, inclusive) 1338 self.step = step 1339 1340 # Positions to select. 1341 1342 self.positions = positions 1343 1344 # Queue to hold values matching the negative position values. 1345 1346 self.queue_length = positions and positions[0] < 0 and abs(positions[0]) or 0 1347 self.queue = [] 1348 1349 # Result position. 1350 1351 self.resultpos = 0 1352 1353 def next(self): 1354 1355 "Return the next value." 1356 1357 while True: 1358 try: 1359 result = self.next_item(self.start, self.end) 1360 1361 # Positive positions can have their values released immediately. 1362 1363 selected = self.resultpos in self.positions 1364 self.resultpos += 1 1365 1366 if selected: 1367 return result 1368 1369 # Negative positions must be held until this iterator completes and 1370 # then be released. 1371 1372 if self.queue_length: 1373 self.queue.append(result) 1374 if len(self.queue) > self.queue_length: 1375 del self.queue[0] 1376 1377 except StopIteration: 1378 1379 # With a queue and positions, attempt to find the referenced 1380 # positions. 1381 1382 if self.queue and self.positions: 1383 index = self.positions[0] 1384 del self.positions[0] 1385 1386 # Only negative positions are used at this point. 1387 1388 if index < 0: 1389 try: 1390 return self.queue[index] 1391 except IndexError: 1392 pass 1393 1394 # With only positive positions remaining, signal the end of 1395 # the collection. 1396 1397 else: 1398 raise 1399 1400 # With no queue or positions remaining, signal the end of the 1401 # collection. 1402 1403 else: 1404 raise 1405 1406 class StartIterator(SelectorIterator): 1407 1408 "An iterator ensuring that the start occurrence is included." 1409 1410 def __init__(self, selector, current, start, end, inclusive, start_dt): 1411 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1412 self.waiting = start_dt 1413 1414 def next(self): 1415 1416 "Return the next value, initially the start period." 1417 1418 while not self.at_limit(): 1419 result = self.next_item(self.start, self.end) 1420 1421 # Compare with any waiting value. 1422 1423 if self.waiting: 1424 1425 # Produce the waiting value, queue the latest result. 1426 1427 if result != self.waiting: 1428 result, self.waiting = self.waiting, result 1429 1430 # Remove the waiting value if identical to the latest result. 1431 1432 else: 1433 self.waiting = None 1434 1435 return result 1436 1437 raise StopIteration 1438 1439 def connect_selectors(selectors): 1440 1441 """ 1442 Make the 'selectors' reference each other in a hierarchy so that 1443 materialising the principal selector causes the more specific ones to be 1444 employed in the operation. 1445 """ 1446 1447 current = selectors[0] 1448 current.first = first = True 1449 1450 for selector in selectors[1:]: 1451 current.selecting = selector 1452 1453 # Allow selectors within the limit selector to act as if they are first 1454 # in the chain and will operate using the supplied datetime context. 1455 1456 first = isinstance(current, (LimitSelector, StartSelector)) 1457 1458 current = selector 1459 current.first = first 1460 1461 return selectors[0] 1462 1463 # Public functions. 1464 1465 def get_rule(dt, rule): 1466 1467 """ 1468 Using the given initial datetime 'dt', interpret the 'rule' (a semicolon- 1469 separated collection of "key=value" strings), and return the resulting 1470 selector object. 1471 """ 1472 1473 selectors = get_selectors_for_rule(rule) 1474 return get_selector(dt, selectors) 1475 1476 def get_selector(dt, selectors): 1477 1478 """ 1479 Combine the initial datetime 'dt' with the given 'selectors', returning an 1480 object that can be used to select recurrences described by the 'selectors'. 1481 """ 1482 1483 dt = to_tuple(dt) 1484 selectors = insert_start_selector(selectors, dt) 1485 return connect_selectors(combine_datetime_with_selectors(dt, selectors)) 1486 1487 def get_selectors_for_rule(rule): 1488 1489 """ 1490 Return a list of selectors implementing 'rule', useful for "explaining" how 1491 a rule works. 1492 """ 1493 1494 if not isinstance(rule, tuple): 1495 rule = (rule or "").split(";") 1496 return make_selectors(get_qualifiers(rule)) 1497 1498 # vim: tabstop=4 expandtab shiftwidth=4