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 if isinstance(from_sel, Pattern): 538 if not have_sel: 539 have_sel = from_sel.first = True 540 541 l.append(from_sel) 542 543 # Datetime value at same resolution. 544 545 if from_dt and from_dt.level == level: 546 from_dt = get_next(iter_dt) 547 548 # Get the next qualifier. 549 550 from_sel = get_next(iter_sel) 551 552 # Complete the list by adding remaining datetime enumerators. 553 554 while from_dt: 555 add_datetime_selector(from_dt, l) 556 from_dt = get_next(iter_dt) 557 558 return l 559 560 def can_restrict_selector(from_sel): 561 562 "Return whether 'from_sel' can be restricted using datetime information." 563 564 return not isinstance(from_sel, Pattern) and from_sel.qualifier != "BYDAY" 565 566 def add_initial_selector(from_sel, level, l): 567 568 """ 569 Take the selector 'from_sel' at the given resolution 'level', using it to 570 create an initial selector, adding it to the combined list 'l' if required. 571 572 Return whether a frequency selector has been introduced. 573 """ 574 575 if isinstance(from_sel, Enum) and level > 0: 576 parent_level = enum_parent_levels[level] 577 repeat = Pattern(parent_level, {"interval" : 1}, freq_levels[parent_level], first=True) 578 l.append(repeat) 579 return True 580 581 return False 582 583 def add_datetime_selector(from_dt, l): 584 585 """ 586 Take the selector 'from_dt' and add it to the list 'l' if it does not 587 conflict with any day-level qualifiers already in 'l'. 588 """ 589 590 if not l or from_dt.level != freq["DAILY"] or l[-1].level not in daylevels: 591 l.append(from_dt) 592 593 def get_multiple(qualifier): 594 595 "Return the time unit multiple for 'qualifier'." 596 597 return multiples.get(qualifier, 1) 598 599 # Datetime arithmetic. 600 601 def is_year_only(t): 602 603 "Return if 't' describes a year." 604 605 return len(t) == lengths[YEARS] 606 607 def is_month_only(t): 608 609 "Return if 't' describes a month within a year." 610 611 return len(t) == lengths[MONTHS] 612 613 def start_of_year(t): 614 615 "Return the start of the year referenced by 't'." 616 617 return (t[0], 1, 1) 618 619 def end_of_year(t): 620 621 "Return the end of the year referenced by 't'." 622 623 return (t[0], 12, 31) 624 625 def start_of_month(t): 626 627 "Return the start of the month referenced by 't'." 628 629 year, month = t[:2] 630 return (year, month, 1) 631 632 def end_of_month(t): 633 634 "Return the end of the month referenced by 't'." 635 636 year, month = t[:2] 637 return update(update((year, month, 1), (0, 1, 0)), (0, 0, -1)) 638 639 def day_in_year(t, number): 640 641 "Return the day in the year referenced by 't' with the given 'number'." 642 643 return to_tuple(date(*start_of_year(t)) + timedelta(number - 1)) 644 645 def get_year_length(t): 646 647 "Return the length of the year referenced by 't'." 648 649 first_day = date(*start_of_year(t)) 650 last_day = date(*end_of_year(t)) 651 return (last_day - first_day).days + 1 652 653 def get_weekday(t): 654 655 "Return the 1-based weekday for the month referenced by 't'." 656 657 year, month = t[:2] 658 return monthrange(year, month)[0] + 1 659 660 def get_ordered_weekdays(t): 661 662 """ 663 Return the 1-based weekday sequence describing the first week of the month 664 referenced by 't'. 665 """ 666 667 first = get_weekday(t) 668 return range(first, 8) + range(1, first) 669 670 def get_last_weekday_instance(weekday, first_day, last_day): 671 672 """ 673 Return the last instance number for 'weekday' within the period from 674 'first_day' to 'last_day' inclusive. 675 676 Here, 'weekday' is 1-based (starting on Monday), the returned limit is 677 1-based. 678 """ 679 680 weekday0 = get_first_day(first_day, weekday) 681 days = (date(*last_day) - weekday0).days 682 return days / 7 + 1 683 684 def precision(t, level, value=None): 685 686 """ 687 Return 't' trimmed in resolution to the indicated resolution 'level', 688 setting 'value' at the given resolution if indicated. 689 """ 690 691 pos = positions[level] 692 693 if value is None: 694 return t[:pos + 1] 695 else: 696 return t[:pos] + (value,) 697 698 def scale(interval, level): 699 700 """ 701 Scale the given 'interval' value in resolution to the indicated resolution 702 'level', returning a tuple with leading zero elements and 'interval' at the 703 stated position. 704 """ 705 706 pos = positions[level] 707 return (0,) * pos + (interval,) 708 709 def get_seconds(t): 710 711 "Convert the sub-day part of 't' into seconds." 712 713 t = t + (0,) * (6 - len(t)) 714 return (t[3] * 60 + t[4]) * 60 + t[5] 715 716 def update(t, step): 717 718 "Update 't' by 'step' at the resolution of 'step'." 719 720 i = len(step) 721 722 # Years only. 723 724 if i == 1: 725 return (t[0] + step[0],) + tuple(t[1:]) 726 727 # Years and months. 728 729 elif i == 2: 730 month = t[1] + step[1] 731 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 732 733 # Dates and datetimes. 734 735 else: 736 updated_for_months = update(t, step[:2]) 737 738 # Dates only. 739 740 if i == 3: 741 d = datetime(*updated_for_months) 742 s = timedelta(step[2]) 743 744 # Datetimes. 745 746 else: 747 d = datetime(*updated_for_months) 748 s = timedelta(step[2], get_seconds(step)) 749 750 return to_tuple(d + s)[:len(t)] 751 752 def to_tuple(d): 753 754 "Return date or datetime 'd' as a tuple." 755 756 if not isinstance(d, date): 757 return d 758 if isinstance(d, datetime): 759 n = 6 760 else: 761 n = 3 762 return d.timetuple()[:n] 763 764 def get_first_day(first_day, weekday): 765 766 """ 767 Return the first occurrence at or after 'first_day' of 'weekday' as a date 768 instance. 769 """ 770 771 first_day = date(*first_day) 772 first_weekday = first_day.isoweekday() 773 if first_weekday > weekday: 774 return first_day + timedelta(7 - first_weekday + weekday) 775 else: 776 return first_day + timedelta(weekday - first_weekday) 777 778 def get_last_day(last_day, weekday): 779 780 """ 781 Return the last occurrence at or before 'last_day' of 'weekday' as a date 782 instance. 783 """ 784 785 last_day = date(*last_day) 786 last_weekday = last_day.isoweekday() 787 if last_weekday < weekday: 788 return last_day - timedelta(last_weekday + 7 - weekday) 789 else: 790 return last_day - timedelta(last_weekday - weekday) 791 792 # Value expansion and sorting. 793 794 def sort_values(values, limit=None): 795 796 """ 797 Sort the given 'values' using 'limit' to determine the positions of negative 798 values. 799 """ 800 801 # Convert negative values to positive values according to the value limit. 802 803 if limit is not None: 804 l = map(lambda x, limit=limit: x < 0 and x + 1 + limit or x, values) 805 else: 806 l = values[:] 807 808 l.sort() 809 return l 810 811 def compare_weekday_selectors(x, y, weekdays): 812 813 """ 814 Compare 'x' and 'y' values of the form (weekday number, instance number) 815 using 'weekdays' to define an ordering of the weekday numbers. 816 """ 817 818 return cmp((x[1], weekdays.index(x[0])), (y[1], weekdays.index(y[0]))) 819 820 def sort_weekdays(values, first_day, last_day): 821 822 """ 823 Return a sorted copy of the given 'values', each having the form (weekday 824 number, instance number), where 'first_day' indicates the start of the 825 period in which these values apply, and where 'last_day' indicates the end 826 of the period. 827 """ 828 829 weekdays = get_ordered_weekdays(first_day) 830 831 # Expand the values to incorporate specific weekday instances. 832 833 l = [] 834 835 for weekday, index in values: 836 837 # Obtain the last instance number of the weekday in the period. 838 839 limit = get_last_weekday_instance(weekday, first_day, last_day) 840 841 # For specific instances, convert negative selections. 842 843 if index is not None: 844 l.append((weekday, index < 0 and index + 1 + limit or index)) 845 846 # For None, introduce selections for all instances of the weekday. 847 848 else: 849 index = 1 850 while index <= limit: 851 l.append((weekday, index)) 852 index += 1 853 854 # Sort the values so that the resulting dates are ordered. 855 856 fn = lambda x, y, weekdays=weekdays: compare_weekday_selectors(x, y, weekdays) 857 l.sort(cmp=fn) 858 return l 859 860 def convert_positions(setpos): 861 862 "Convert 'setpos' to 0-based indexes." 863 864 l = [] 865 if setpos: 866 for pos in setpos: 867 index = pos < 0 and pos or pos - 1 868 l.append(index) 869 return l 870 871 # Classes for producing instances from recurrence structures. 872 873 class Selector: 874 875 "A generic selector." 876 877 def __init__(self, level, args, qualifier, selecting=None): 878 879 """ 880 Initialise at the given 'level' a selector employing the given 'args' 881 defined in the interpretation of recurrence rule qualifiers, with the 882 'qualifier' being the name of the rule qualifier, and 'selecting' being 883 an optional selector used to find more specific instances from those 884 found by this selector. 885 """ 886 887 self.level = level 888 self.args = args or {} 889 self.qualifier = qualifier 890 self.selecting = selecting 891 892 def __repr__(self): 893 return "%s(%s, %r, %r)" % (self.__class__.__name__, 894 level_labels[self.level], 895 self.args, self.qualifier) 896 897 def select(self, start, end, inclusive=False): 898 899 """ 900 Return an iterator over instances starting at 'start' and continuing up 901 to but not including any at 'end' or later. 902 903 If 'inclusive' is specified, the selection of instances will include the 904 end of the search period if present in the results. 905 """ 906 907 start = to_tuple(start) 908 end = to_tuple(end) 909 return self.materialise_items(start, start, end, inclusive) 910 911 def materialise(self, start, end, inclusive=False): 912 913 """ 914 Starting at 'start', materialise instances up to but not including any 915 at 'end' or later. A list of instances is returned. 916 917 If 'inclusive' is specified, the selection of instances will include the 918 end of the search period if present in the results. 919 """ 920 921 return list(self.select(start, end, inclusive)) 922 923 def set_values(self, values): 924 self.args["values"] = values 925 926 class Pattern(Selector): 927 928 "A selector of time periods according to a repeating pattern." 929 930 def __init__(self, level, args, qualifier, selecting=None, first=False): 931 Selector.__init__(self, level, args, qualifier, selecting) 932 multiple = get_multiple(self.qualifier) 933 self.first = first 934 935 # Define the scale of a single period. 936 937 self.unit_step = scale(multiple, level) 938 self.update_step() 939 940 def update_step(self): 941 942 "Update the step between result periods." 943 944 multiple = get_multiple(self.qualifier) 945 interval = self.get_interval() 946 self.step = scale(interval * multiple, self.level) 947 948 def materialise_items(self, context, start, end, inclusive=False): 949 950 """ 951 Bounded by the given 'context', return periods within 'start' to 'end'. 952 953 If 'inclusive' is specified, the selection of periods will include those 954 starting at the end of the search period, if present in the results. 955 """ 956 957 # Employ the context as the current period if this is the first 958 # qualifier in the selection chain. 959 960 if self.first: 961 current = precision(context, self.level) 962 963 # Otherwise, obtain the first value at this resolution within the 964 # context period. 965 966 else: 967 current = precision(context, self.level, firstvalues[self.level]) 968 969 return PatternIterator(self, current, start, end, inclusive, 970 self.step, self.unit_step) 971 972 def get_interval(self): 973 return self.args.get("interval", 1) 974 975 def set_interval(self, interval): 976 self.args["interval"] = interval 977 self.update_step() 978 979 class Enum(Selector): 980 981 "A generic value selector." 982 983 def __init__(self, level, args, qualifier, selecting=None): 984 Selector.__init__(self, level, args, qualifier, selecting) 985 self.step = scale(1, level) 986 987 def materialise_items(self, context, start, end, inclusive=False): 988 return EnumIterator(self, context, start, end, inclusive, self.step, 989 self.get_values()) 990 991 def get_values(self, limit=None): 992 return sort_values(self.args["values"], limit) 993 994 class WeekDayFilter(Enum): 995 996 "A selector of instances specified in terms of day numbers." 997 998 def __init__(self, level, args, qualifier, selecting=None): 999 Selector.__init__(self, level, args, qualifier, selecting) 1000 self.step = scale(1, WEEKS) 1001 1002 def materialise_items(self, context, start, end, inclusive=False): 1003 1004 # Get weekdays in the year. 1005 1006 if is_year_only(context): 1007 first_day = start_of_year(context) 1008 last_day = end_of_year(context) 1009 1010 # Get weekdays in the month. 1011 1012 elif is_month_only(context): 1013 first_day = start_of_month(context) 1014 last_day = end_of_month(context) 1015 1016 # Get weekdays in the week. 1017 1018 else: 1019 current = context 1020 return WeekDayIterator(self, current, start, end, inclusive, self.step, 1021 self.get_weekdays()) 1022 1023 current = first_day 1024 values = sort_weekdays(self.args["values"], first_day, last_day) 1025 return WeekDayGeneralIterator(self, current, start, end, inclusive, 1026 self.step, values) 1027 1028 def get_values(self): 1029 1030 """ 1031 Return a sequence of (value, index) tuples selecting weekdays in the 1032 applicable period. Each value is a 1-based index representing a weekday. 1033 """ 1034 1035 return self.args["values"] 1036 1037 def get_weekdays(self): 1038 1039 "Return only the 1-based weekday indexes." 1040 1041 values = [] 1042 for value, index in self.args["values"]: 1043 values.append(value) 1044 return values 1045 1046 class MonthDayFilter(Enum): 1047 1048 "A selector of month days." 1049 1050 def materialise_items(self, context, start, end, inclusive=False): 1051 last_day = end_of_month(context)[2] 1052 return EnumIterator(self, context, start, end, inclusive, self.step, 1053 self.get_values(last_day)) 1054 1055 class YearDayFilter(Enum): 1056 1057 "A selector of days in years." 1058 1059 def materialise_items(self, context, start, end, inclusive=False): 1060 first_day = start_of_year(context) 1061 year_length = get_year_length(context) 1062 return YearDayFilterIterator(self, first_day, start, end, inclusive, self.step, 1063 self.get_values(year_length)) 1064 1065 class LimitSelector(Selector): 1066 1067 "A result set limit selector." 1068 1069 def materialise_items(self, context, start, end, inclusive=False): 1070 return LimitIterator(self, context, start, end, inclusive, self.get_limit()) 1071 1072 def get_limit(self): 1073 return self.args["values"][0] 1074 1075 def set_limit(self, limit): 1076 self.args["values"] = [limit] 1077 1078 class PositionSelector(Selector): 1079 1080 "A result set position selector." 1081 1082 def __init__(self, level, args, qualifier, selecting=None): 1083 Selector.__init__(self, level, args, qualifier, selecting) 1084 if level is not None: 1085 self.set_level(level) 1086 else: 1087 self.step = None 1088 1089 def set_level(self, level): 1090 self.level = level 1091 self.step = scale(1, self.level) 1092 1093 def materialise_items(self, context, start, end, inclusive=False): 1094 return PositionIterator(self, context, start, end, inclusive, self.step, 1095 self.get_positions()) 1096 1097 def get_positions(self): 1098 return convert_positions(sort_values(self.args["values"])) 1099 1100 def set_positions(self, positions): 1101 self.args["values"] = positions 1102 1103 class StartSelector(Selector): 1104 1105 "A selector ensuring that the start occurrence is included." 1106 1107 def materialise_items(self, context, start, end, inclusive=False): 1108 return StartIterator(self, context, start, end, inclusive, 1109 self.get_start()) 1110 1111 def get_start(self): 1112 return self.args["start"] 1113 1114 special_enum_levels = { 1115 "BYDAY" : WeekDayFilter, 1116 "BYMONTHDAY" : MonthDayFilter, 1117 "BYYEARDAY" : YearDayFilter, 1118 } 1119 1120 # Iterator classes. 1121 1122 class SelectorIterator: 1123 1124 "An iterator over selected data." 1125 1126 def __init__(self, selector, current, start, end, inclusive): 1127 1128 """ 1129 Define an iterator having the 'current' point in time, 'start' and 'end' 1130 limits, and whether the selection is 'inclusive'. 1131 """ 1132 1133 self.selector = selector 1134 self.current = current 1135 self.start = start 1136 self.end = end 1137 self.inclusive = inclusive 1138 1139 # Iterator over selections within this selection. 1140 1141 self.iterator = None 1142 1143 def __iter__(self): 1144 return self 1145 1146 def next_item(self, earliest, next): 1147 1148 """ 1149 Given the 'earliest' acceptable instance and the 'next' instance, return 1150 a list of result items. 1151 1152 Where no selection within the current instance occurs, the current 1153 instance will be returned as a result if the same or later than the 1154 earliest acceptable instance. 1155 """ 1156 1157 # Obtain an item from a selector operating within this selection. 1158 1159 selecting = self.selector.selecting 1160 1161 if selecting: 1162 1163 # Obtain an iterator for any selector within the current period. 1164 1165 if not self.iterator: 1166 self.iterator = selecting.materialise_items(self.current, 1167 earliest, next, self.inclusive) 1168 1169 # Attempt to obtain and return a value. 1170 1171 return self.iterator.next() 1172 1173 # Return items within this selection. 1174 1175 else: 1176 return self.current 1177 1178 def filter_by_period(self, result): 1179 1180 "Return whether 'result' occurs within the selection period." 1181 1182 return (self.inclusive and result <= self.end or result < self.end) and \ 1183 self.start <= result 1184 1185 def at_limit(self): 1186 1187 """ 1188 Obtain periods before the end. If inclusive and selecting in the final 1189 selector, obtain the period at the end. 1190 """ 1191 1192 inclusive = self.inclusive and not self.selector.selecting 1193 return not inclusive and self.current == self.end or \ 1194 self.current > self.end 1195 1196 class PatternIterator(SelectorIterator): 1197 1198 "An iterator for a general selection pattern." 1199 1200 def __init__(self, selector, current, start, end, inclusive, step, unit_step): 1201 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1202 self.step = step 1203 self.unit_step = unit_step 1204 1205 def next(self): 1206 1207 "Return the next value." 1208 1209 while not self.at_limit(): 1210 1211 # Increment the current datetime by the step for the next period. 1212 1213 next = update(self.current, self.step) 1214 1215 # Determine the end point of the current period. 1216 1217 current_end = update(self.current, self.unit_step) 1218 1219 # Obtain any period or periods within the bounds defined by the 1220 # current period and any contraining start and end points. 1221 1222 try: 1223 result = self.next_item(max(self.current, self.start), 1224 min(current_end, self.end)) 1225 1226 # Obtain the next period if not selecting within this period. 1227 1228 if not self.selector.selecting: 1229 self.current = next 1230 1231 # Filter out periods. 1232 1233 if self.filter_by_period(result): 1234 return result 1235 1236 # Move on to the next instance. 1237 1238 except StopIteration: 1239 self.current = next 1240 self.iterator = None 1241 1242 raise StopIteration 1243 1244 class WeekDayIterator(SelectorIterator): 1245 1246 "An iterator over weekday selections in week periods." 1247 1248 def __init__(self, selector, current, start, end, inclusive, step, values): 1249 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1250 self.step = step 1251 self.values = values 1252 1253 def next(self): 1254 1255 "Return the next value." 1256 1257 while not self.at_limit(): 1258 1259 # Increment the current datetime by the step for the next period. 1260 1261 next = update(self.current, self.step) 1262 1263 # Determine whether the day is one chosen. 1264 1265 if date(*self.current).isoweekday() in self.values: 1266 try: 1267 result = self.next_item(max(self.current, self.start), 1268 min(next, self.end)) 1269 1270 # Obtain the next period if not selecting within this period. 1271 1272 if not self.selector.selecting: 1273 self.current = next 1274 1275 return result 1276 1277 # Move on to the next instance. 1278 1279 except StopIteration: 1280 self.current = next 1281 self.iterator = None 1282 1283 else: 1284 self.current = next 1285 self.iterator = None 1286 1287 raise StopIteration 1288 1289 class EnumIterator(SelectorIterator): 1290 1291 "An iterator over specific value selections." 1292 1293 def __init__(self, selector, current, start, end, inclusive, step, values): 1294 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1295 self.step = step 1296 1297 # Derive selected periods from a base and the indicated values. 1298 1299 self.base = current 1300 1301 # Iterate over the indicated period values. 1302 1303 self.values = iter(values) 1304 self.value = None 1305 1306 def get_selected_period(self): 1307 1308 "Return the period indicated by the current value." 1309 1310 return precision(self.base, self.selector.level, self.value) 1311 1312 def next(self): 1313 1314 "Return the next value." 1315 1316 while True: 1317 1318 # Find each of the given selected values. 1319 1320 if not self.selector.selecting or self.value is None: 1321 self.value = self.values.next() 1322 1323 # Select a period for each value at the current resolution. 1324 1325 self.current = self.get_selected_period() 1326 next = update(self.current, self.step) 1327 1328 # To support setpos, only current and next bound the search, not 1329 # the period in addition. 1330 1331 try: 1332 return self.next_item(self.current, next) 1333 1334 # Move on to the next instance. 1335 1336 except StopIteration: 1337 self.value = None 1338 self.iterator = None 1339 1340 raise StopIteration 1341 1342 class WeekDayGeneralIterator(EnumIterator): 1343 1344 "An iterator over weekday selections in month and year periods." 1345 1346 def get_selected_period(self): 1347 1348 "Return the day indicated by the current day value." 1349 1350 value, index = self.value 1351 offset = timedelta(7 * (index - 1)) 1352 weekday0 = get_first_day(self.base, value) 1353 return precision(to_tuple(weekday0 + offset), DAYS) 1354 1355 class YearDayFilterIterator(EnumIterator): 1356 1357 "An iterator over day-in-year selections." 1358 1359 def get_selected_period(self): 1360 1361 "Return the day indicated by the current day value." 1362 1363 offset = timedelta(self.value - 1) 1364 return precision(to_tuple(date(*self.base) + offset), DAYS) 1365 1366 class LimitIterator(SelectorIterator): 1367 1368 "A result set limiting iterator." 1369 1370 def __init__(self, selector, context, start, end, inclusive, limit): 1371 SelectorIterator.__init__(self, selector, context, start, end, inclusive) 1372 self.limit = limit 1373 self.count = 0 1374 1375 def next(self): 1376 1377 "Return the next value." 1378 1379 if self.count < self.limit: 1380 self.count += 1 1381 result = self.next_item(self.start, self.end) 1382 return result 1383 1384 raise StopIteration 1385 1386 class PositionIterator(SelectorIterator): 1387 1388 "An iterator over results, selecting positions." 1389 1390 def __init__(self, selector, context, start, end, inclusive, step, positions): 1391 SelectorIterator.__init__(self, selector, context, start, end, inclusive) 1392 self.step = step 1393 1394 # Positions to select. 1395 1396 self.positions = positions 1397 1398 # Queue to hold values matching the negative position values. 1399 1400 self.queue_length = positions and positions[0] < 0 and abs(positions[0]) or 0 1401 self.queue = [] 1402 1403 # Result position. 1404 1405 self.resultpos = 0 1406 1407 def next(self): 1408 1409 "Return the next value." 1410 1411 while True: 1412 try: 1413 result = self.next_item(self.start, self.end) 1414 1415 # Positive positions can have their values released immediately. 1416 1417 selected = self.resultpos in self.positions 1418 self.resultpos += 1 1419 1420 if selected: 1421 return result 1422 1423 # Negative positions must be held until this iterator completes and 1424 # then be released. 1425 1426 if self.queue_length: 1427 self.queue.append(result) 1428 if len(self.queue) > self.queue_length: 1429 del self.queue[0] 1430 1431 except StopIteration: 1432 1433 # With a queue and positions, attempt to find the referenced 1434 # positions. 1435 1436 if self.queue and self.positions: 1437 index = self.positions[0] 1438 del self.positions[0] 1439 1440 # Only negative positions are used at this point. 1441 1442 if index < 0: 1443 try: 1444 return self.queue[index] 1445 except IndexError: 1446 pass 1447 1448 # With only positive positions remaining, signal the end of 1449 # the collection. 1450 1451 else: 1452 raise 1453 1454 # With no queue or positions remaining, signal the end of the 1455 # collection. 1456 1457 else: 1458 raise 1459 1460 class StartIterator(SelectorIterator): 1461 1462 "An iterator ensuring that the start occurrence is included." 1463 1464 def __init__(self, selector, current, start, end, inclusive, start_dt): 1465 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1466 self.waiting = start_dt 1467 1468 def next(self): 1469 1470 "Return the next value, initially the start period." 1471 1472 # Obtain the next item. 1473 1474 try: 1475 result = self.next_item(self.start, self.end) 1476 except StopIteration: 1477 1478 # With no more values, flush any waiting value. 1479 1480 if self.waiting is not None: 1481 result = self.waiting 1482 self.waiting = None 1483 return result 1484 else: 1485 raise 1486 1487 # Compare with any waiting value. 1488 1489 if self.waiting is not None: 1490 1491 # Produce the waiting value, queue the latest result. 1492 1493 if result != self.waiting: 1494 result, self.waiting = self.waiting, result 1495 1496 # Remove the waiting value if identical to the latest result. 1497 1498 else: 1499 self.waiting = None 1500 1501 return result 1502 1503 def connect_selectors(selectors): 1504 1505 """ 1506 Make the 'selectors' reference each other in a hierarchy so that 1507 materialising the principal selector causes the more specific ones to be 1508 employed in the operation. 1509 """ 1510 1511 current = selectors[0] 1512 1513 for selector in selectors[1:]: 1514 current.selecting = selector 1515 current = selector 1516 1517 return selectors[0] 1518 1519 # Public functions. 1520 1521 def get_rule(dt, rule): 1522 1523 """ 1524 Using the given initial datetime 'dt', interpret the 'rule' (a semicolon- 1525 separated collection of "key=value" strings), and return the resulting 1526 selector object. 1527 """ 1528 1529 selectors = get_selectors_for_rule(rule) 1530 return get_selector(dt, selectors) 1531 1532 def get_selector(dt, selectors): 1533 1534 """ 1535 Combine the initial datetime 'dt' with the given 'selectors', returning an 1536 object that can be used to select recurrences described by the 'selectors'. 1537 """ 1538 1539 dt = to_tuple(dt) 1540 selectors = insert_start_selector(selectors, dt) 1541 return connect_selectors(combine_datetime_with_selectors(dt, selectors)) 1542 1543 def get_selectors_for_rule(rule): 1544 1545 """ 1546 Return a list of selectors implementing 'rule', useful for "explaining" how 1547 a rule works. 1548 """ 1549 1550 if not isinstance(rule, tuple): 1551 rule = (rule or "").split(";") 1552 return make_selectors(get_qualifiers(rule)) 1553 1554 def get_selectors_from_selector(selector): 1555 1556 "Return the chain of selectors from 'selector', useful for debugging." 1557 1558 if selector.selecting: 1559 return [selector] + get_selectors_from_selector(selector.selecting) 1560 else: 1561 return [selector] 1562 1563 # vim: tabstop=4 expandtab shiftwidth=4