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