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