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