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