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