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