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