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 if not checked: 255 return None 256 257 # Get single values for non-weekday details. 258 259 if qualifier != "BYDAY": 260 checked = checked[0] 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 values 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 if not value_ranges: 429 return value 430 431 for value_range in value_ranges: 432 433 # Test actual ranges. 434 435 if isinstance(value_range, tuple): 436 start, end = value_range 437 if start <= value <= end: 438 return value 439 440 # Test enumerations. 441 442 elif isinstance(value_range, list): 443 if value in value_range: 444 return value 445 446 # Test mappings. 447 448 elif isinstance(value_range, dict): 449 if value_range.has_key(value): 450 return value_range[value] 451 452 # Test value matches. 453 454 elif value == value_range: 455 return value 456 457 raise ValueError, value 458 459 def get_datetime_structure(datetime): 460 461 "Return the structure of 'datetime' for recurrence production." 462 463 l = [] 464 offset = 0 465 466 for pos, value in enumerate(datetime): 467 468 # At the day number, adjust the frequency level offset to reference 469 # days (and then hours, minutes, seconds). 470 471 if pos == 2: 472 offset = 3 473 474 l.append(Enum(pos + offset, {"values" : [value]}, "DT")) 475 476 return l 477 478 def combine_datetime_with_selectors(datetime, selectors): 479 480 """ 481 Combine 'datetime' with 'selectors' to produce a structure for recurrence 482 production. 483 484 Initial datetime values appearing at broader resolutions than any qualifiers 485 are ignored, since their details will be used when materialising the 486 results. 487 488 Qualifiers are accumulated in order to define a selection. Datetime values 489 occurring at the same resolution as qualifiers are ignored. 490 491 Any remaining datetime values are introduced as enumerators, provided that 492 they do not conflict with qualifiers. For example, specific day values 493 conflict with day selectors and weekly qualifiers. 494 495 The purpose of the remaining datetime values is to define a result within 496 a period selected by the most precise qualifier. For example, the selection 497 of a day and month in a year recurrence. 498 """ 499 500 iter_dt = iter(get_datetime_structure(datetime)) 501 iter_sel = iter(selectors) 502 503 l = [] 504 505 from_dt = get_next(iter_dt) 506 from_sel = get_next(iter_sel) 507 have_sel = False 508 held_dt = [] 509 510 # Consume from both lists, merging entries. 511 512 while from_sel: 513 level = from_sel.level 514 515 # Datetime value at wider resolution. 516 517 if from_dt and from_dt.level < level: 518 held_dt.append(from_dt) 519 from_dt = get_next(iter_dt) 520 521 # Qualifier at wider or same resolution as datetime value. 522 523 else: 524 if not have_sel: 525 have_sel = add_initial_selector(from_sel, level, l) 526 527 # Introduce any held datetime values, if appropriate. 528 529 elif can_restrict_selector(from_sel): 530 for from_held_dt in held_dt: 531 add_datetime_selector(from_held_dt, l) 532 533 held_dt = [] 534 535 # Add the qualifier to the combined list. 536 537 if isinstance(from_sel, Pattern): 538 if not have_sel: 539 have_sel = from_sel.first = True 540 541 l.append(from_sel) 542 543 # Datetime value at same resolution. 544 545 if from_dt and from_dt.level == level: 546 from_dt = get_next(iter_dt) 547 548 # Get the next qualifier. 549 550 from_sel = get_next(iter_sel) 551 552 # Complete the list by adding remaining datetime enumerators. 553 554 while from_dt: 555 add_datetime_selector(from_dt, l) 556 from_dt = get_next(iter_dt) 557 558 return l 559 560 def can_restrict_selector(from_sel): 561 562 "Return whether 'from_sel' can be restricted using datetime information." 563 564 return not isinstance(from_sel, Pattern) and from_sel.qualifier != "BYDAY" 565 566 def add_initial_selector(from_sel, level, l): 567 568 """ 569 Take the selector 'from_sel' at the given resolution 'level', using it to 570 create an initial selector, adding it to the combined list 'l' if required. 571 572 Return whether a frequency selector has been introduced. 573 """ 574 575 if isinstance(from_sel, Enum) and level > 0: 576 parent_level = enum_parent_levels[level] 577 repeat = Pattern(parent_level, {"interval" : 1}, freq_levels[parent_level], first=True) 578 l.append(repeat) 579 return True 580 581 return False 582 583 def add_datetime_selector(from_dt, l): 584 585 """ 586 Take the selector 'from_dt' and add it to the list 'l' if it does not 587 conflict with any day-level qualifiers already in 'l'. 588 """ 589 590 if not l or from_dt.level != freq["DAILY"] or l[-1].level not in daylevels: 591 l.append(from_dt) 592 593 def get_multiple(qualifier): 594 595 "Return the time unit multiple for 'qualifier'." 596 597 return multiples.get(qualifier, 1) 598 599 # Datetime arithmetic. 600 601 def is_year_only(t): 602 603 "Return if 't' describes a year." 604 605 return len(t) == lengths[YEARS] 606 607 def is_month_only(t): 608 609 "Return if 't' describes a month within a year." 610 611 return len(t) == lengths[MONTHS] 612 613 def start_of_year(t): 614 615 "Return the start of the year referenced by 't'." 616 617 return (t[0], 1, 1) 618 619 def end_of_year(t): 620 621 "Return the end of the year referenced by 't'." 622 623 return (t[0], 12, 31) 624 625 def start_of_month(t): 626 627 "Return the start of the month referenced by 't'." 628 629 year, month = t[:2] 630 return (year, month, 1) 631 632 def end_of_month(t): 633 634 "Return the end of the month referenced by 't'." 635 636 year, month = t[:2] 637 return update(update((year, month, 1), (0, 1, 0)), (0, 0, -1)) 638 639 def day_in_year(t, number): 640 641 "Return the day in the year referenced by 't' with the given 'number'." 642 643 return to_tuple(date(*start_of_year(t)) + timedelta(number - 1)) 644 645 def get_year_length(t): 646 647 "Return the length of the year referenced by 't'." 648 649 first_day = date(*start_of_year(t)) 650 last_day = date(*end_of_year(t)) 651 return (last_day - first_day).days + 1 652 653 def get_weekday(t): 654 655 "Return the 1-based weekday for the month referenced by 't'." 656 657 year, month = t[:2] 658 return monthrange(year, month)[0] + 1 659 660 def get_ordered_weekdays(t): 661 662 """ 663 Return the 1-based weekday sequence describing the first week of the month 664 referenced by 't'. 665 """ 666 667 first = get_weekday(t) 668 return range(first, 8) + range(1, first) 669 670 def get_last_weekday_instance(weekday, first_day, last_day): 671 672 """ 673 Return the last instance number for 'weekday' within the period from 674 'first_day' to 'last_day' inclusive. 675 676 Here, 'weekday' is 1-based (starting on Monday), the returned limit is 677 1-based. 678 """ 679 680 weekday0 = get_first_day(first_day, weekday) 681 days = (date(*last_day) - weekday0).days 682 return days / 7 + 1 683 684 def constrain_to_month(t): 685 686 "Return 't' corrected to ensure that the day number is within the month." 687 688 year, month, day = t[:3] 689 time = t[3:] 690 max_day = monthrange(year, month)[1] 691 day = min(max_day, day) 692 return tuple((year, month) + (day,) + time) 693 694 def within_month(t): 695 696 """ 697 Return whether 't' is within the permissible day range of the given month, 698 if 't' describes a day or datetime. Otherwise, return a true value for years 699 and months. 700 """ 701 702 if len(t) < 3: 703 return True 704 705 year, month, day = t[:3] 706 max_day = monthrange(year, month)[1] 707 return day <= max_day 708 709 def limit_value(t, level): 710 711 "Return 't' trimmed in resolution to the indicated resolution 'level'." 712 713 pos = positions[level] 714 return t[:pos + 1] 715 716 def make_value(t, level, value): 717 718 """ 719 Return 't' trimmed in resolution to the indicated resolution 'level', 720 extended by setting 'value' at the given resolution. 721 """ 722 723 pos = positions[level] 724 return t[:pos] + (value,) 725 726 def scale(interval, level): 727 728 """ 729 Scale the given 'interval' value in resolution to the indicated resolution 730 'level', returning a tuple with leading zero elements and 'interval' at the 731 stated position. 732 """ 733 734 pos = positions[level] 735 return (0,) * pos + (interval,) 736 737 def get_seconds(t): 738 739 "Convert the sub-day part of 't' into seconds." 740 741 t = t + (0,) * (6 - len(t)) 742 return (t[3] * 60 + t[4]) * 60 + t[5] 743 744 def update(t, step): 745 746 "Update 't' by 'step' at the resolution of 'step'." 747 748 i = len(step) 749 750 # Years only. 751 752 if i == 1: 753 return (t[0] + step[0],) + tuple(t[1:]) 754 755 # Years and months. 756 757 elif i == 2: 758 month = t[1] + step[1] 759 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 760 761 # Dates and datetimes. 762 763 else: 764 updated_for_months = constrain_to_month(update(t, step[:2])) 765 d = datetime(*updated_for_months) 766 767 # Dates only. 768 769 if i == 3: 770 s = timedelta(step[2]) 771 772 # Datetimes. 773 774 else: 775 s = timedelta(step[2], get_seconds(step)) 776 777 return to_tuple(d + s)[:len(t)] 778 779 def to_tuple(d): 780 781 "Return date or datetime 'd' as a tuple." 782 783 if not isinstance(d, date): 784 return d 785 if isinstance(d, datetime): 786 n = 6 787 else: 788 n = 3 789 return d.timetuple()[:n] 790 791 def get_first_day(first_day, weekday): 792 793 """ 794 Return the first occurrence at or after 'first_day' of 'weekday' as a date 795 instance. 796 """ 797 798 first_day = date(*first_day) 799 first_weekday = first_day.isoweekday() 800 if first_weekday > weekday: 801 return first_day + timedelta(7 - first_weekday + weekday) 802 else: 803 return first_day + timedelta(weekday - first_weekday) 804 805 def get_last_day(last_day, weekday): 806 807 """ 808 Return the last occurrence at or before 'last_day' of 'weekday' as a date 809 instance. 810 """ 811 812 last_day = date(*last_day) 813 last_weekday = last_day.isoweekday() 814 if last_weekday < weekday: 815 return last_day - timedelta(last_weekday + 7 - weekday) 816 else: 817 return last_day - timedelta(last_weekday - weekday) 818 819 # Value expansion and sorting. 820 821 def sort_values(values, limit=None): 822 823 """ 824 Sort the given 'values' using 'limit' to determine the positions of negative 825 values. 826 """ 827 828 # Convert negative values to positive values according to the value limit. 829 830 if limit is not None: 831 l = map(lambda x, limit=limit: x < 0 and x + 1 + limit or x, values) 832 else: 833 l = values[:] 834 835 l.sort() 836 return l 837 838 def compare_weekday_selectors(x, y, weekdays): 839 840 """ 841 Compare 'x' and 'y' values of the form (weekday number, instance number) 842 using 'weekdays' to define an ordering of the weekday numbers. 843 """ 844 845 return cmp((x[1], weekdays.index(x[0])), (y[1], weekdays.index(y[0]))) 846 847 def sort_weekdays(values, first_day, last_day): 848 849 """ 850 Return a sorted copy of the given 'values', each having the form (weekday 851 number, instance number), where 'first_day' indicates the start of the 852 period in which these values apply, and where 'last_day' indicates the end 853 of the period. 854 """ 855 856 weekdays = get_ordered_weekdays(first_day) 857 858 # Expand the values to incorporate specific weekday instances. 859 860 l = [] 861 862 for weekday, index in values: 863 864 # Obtain the last instance number of the weekday in the period. 865 866 limit = get_last_weekday_instance(weekday, first_day, last_day) 867 868 # For specific instances, convert negative selections. 869 870 if index is not None: 871 l.append((weekday, index < 0 and index + 1 + limit or index)) 872 873 # For None, introduce selections for all instances of the weekday. 874 875 else: 876 index = 1 877 while index <= limit: 878 l.append((weekday, index)) 879 index += 1 880 881 # Sort the values so that the resulting dates are ordered. 882 883 fn = lambda x, y, weekdays=weekdays: compare_weekday_selectors(x, y, weekdays) 884 l.sort(cmp=fn) 885 return l 886 887 def convert_positions(setpos): 888 889 "Convert 'setpos' to 0-based indexes." 890 891 l = [] 892 if setpos: 893 for pos in setpos: 894 index = pos < 0 and pos or pos - 1 895 l.append(index) 896 return l 897 898 # Classes for producing instances from recurrence structures. 899 900 class Selector: 901 902 "A generic selector." 903 904 def __init__(self, level, args, qualifier, selecting=None): 905 906 """ 907 Initialise at the given 'level' a selector employing the given 'args' 908 defined in the interpretation of recurrence rule qualifiers, with the 909 'qualifier' being the name of the rule qualifier, and 'selecting' being 910 an optional selector used to find more specific instances from those 911 found by this selector. 912 """ 913 914 self.level = level 915 self.args = args or {} 916 self.qualifier = qualifier 917 self.selecting = selecting 918 919 def __repr__(self): 920 return "%s(%s, %r, %r)" % (self.__class__.__name__, 921 level_labels[self.level], 922 self.args, self.qualifier) 923 924 def select(self, start, end, inclusive=False): 925 926 """ 927 Return an iterator over instances starting at 'start' and continuing up 928 to but not including any at 'end' or later. 929 930 If 'inclusive' is specified, the selection of instances will include the 931 end of the search period if present in the results. 932 """ 933 934 start = to_tuple(start) 935 end = to_tuple(end) 936 return self.materialise_items(start, start, end, inclusive) 937 938 def materialise(self, start, end, inclusive=False): 939 940 """ 941 Starting at 'start', materialise instances up to but not including any 942 at 'end' or later. A list of instances is returned. 943 944 If 'inclusive' is specified, the selection of instances will include the 945 end of the search period if present in the results. 946 """ 947 948 return list(self.select(start, end, inclusive)) 949 950 def set_values(self, values): 951 self.args["values"] = values 952 953 # Copying and comparison support. 954 955 def as_tuple(self): 956 return self.level, self.args, self.qualifier, self.selecting 957 958 def copy(self): 959 return self.__class__(*self.as_tuple()) 960 961 def __cmp__(self, other): 962 return cmp(self.as_tuple(), other and other.as_tuple()) 963 964 class Pattern(Selector): 965 966 "A selector of time periods according to a repeating pattern." 967 968 def __init__(self, level, args, qualifier, selecting=None, first=False): 969 Selector.__init__(self, level, args, qualifier, selecting) 970 multiple = get_multiple(self.qualifier) 971 self.first = first 972 973 # Define the scale of a single period. 974 975 self.unit_step = scale(multiple, level) 976 self.update_step() 977 978 def update_step(self): 979 980 "Update the step between result periods." 981 982 multiple = get_multiple(self.qualifier) 983 interval = self.get_interval() 984 self.step = scale(interval * multiple, self.level) 985 986 def materialise_items(self, context, start, end, inclusive=False): 987 988 """ 989 Bounded by the given 'context', return periods within 'start' to 'end'. 990 991 If 'inclusive' is specified, the selection of periods will include those 992 starting at the end of the search period, if present in the results. 993 """ 994 995 # Employ the context as the current period if this is the first 996 # qualifier in the selection chain. 997 998 if self.first: 999 current = limit_value(context, self.level) 1000 1001 # Otherwise, obtain the first value at this resolution within the 1002 # context period. 1003 1004 else: 1005 current = make_value(context, self.level, firstvalues[self.level]) 1006 1007 return PatternIterator(self, current, start, end, inclusive, 1008 self.step, self.unit_step) 1009 1010 def get_interval(self): 1011 return self.args.get("interval", 1) 1012 1013 def set_interval(self, interval): 1014 self.args["interval"] = interval 1015 self.update_step() 1016 1017 # Copying and comparison support. 1018 1019 def as_tuple(self): 1020 return self.level, self.args, self.qualifier, self.selecting, self.first 1021 1022 class Enum(Selector): 1023 1024 "A generic value selector." 1025 1026 def __init__(self, level, args, qualifier, selecting=None): 1027 Selector.__init__(self, level, args, qualifier, selecting) 1028 self.step = scale(1, level) 1029 1030 def materialise_items(self, context, start, end, inclusive=False): 1031 return EnumIterator(self, context, start, end, inclusive, self.step, 1032 self.get_values()) 1033 1034 def get_values(self, limit=None): 1035 return sort_values(self.args["values"], limit) 1036 1037 class WeekDayFilter(Enum): 1038 1039 "A selector of instances specified in terms of day numbers." 1040 1041 def __init__(self, level, args, qualifier, selecting=None): 1042 Selector.__init__(self, level, args, qualifier, selecting) 1043 self.step = scale(1, WEEKS) 1044 1045 def materialise_items(self, context, start, end, inclusive=False): 1046 1047 # Get weekdays in the year. 1048 1049 if is_year_only(context): 1050 first_day = start_of_year(context) 1051 last_day = end_of_year(context) 1052 1053 # Get weekdays in the month. 1054 1055 elif is_month_only(context): 1056 first_day = start_of_month(context) 1057 last_day = end_of_month(context) 1058 1059 # Get weekdays in the week. 1060 1061 else: 1062 current = context 1063 return WeekDayIterator(self, current, start, end, inclusive, self.step, 1064 self.get_weekdays()) 1065 1066 current = first_day 1067 values = sort_weekdays(self.args["values"], first_day, last_day) 1068 return WeekDayGeneralIterator(self, current, start, end, inclusive, 1069 self.step, values) 1070 1071 def get_values(self): 1072 1073 """ 1074 Return a sequence of (value, index) tuples selecting weekdays in the 1075 applicable period. Each value is a 1-based index representing a weekday. 1076 """ 1077 1078 return self.args["values"] 1079 1080 def get_weekdays(self): 1081 1082 "Return only the 1-based weekday indexes." 1083 1084 values = [] 1085 for value, index in self.args["values"]: 1086 values.append(value) 1087 return values 1088 1089 class MonthDayFilter(Enum): 1090 1091 "A selector of month days." 1092 1093 def materialise_items(self, context, start, end, inclusive=False): 1094 last_day = end_of_month(context)[2] 1095 return EnumIterator(self, context, start, end, inclusive, self.step, 1096 self.get_values(last_day)) 1097 1098 class YearDayFilter(Enum): 1099 1100 "A selector of days in years." 1101 1102 def materialise_items(self, context, start, end, inclusive=False): 1103 first_day = start_of_year(context) 1104 year_length = get_year_length(context) 1105 return YearDayFilterIterator(self, first_day, start, end, inclusive, self.step, 1106 self.get_values(year_length)) 1107 1108 class LimitSelector(Selector): 1109 1110 "A result set limit selector." 1111 1112 def materialise_items(self, context, start, end, inclusive=False): 1113 return LimitIterator(self, context, start, end, inclusive, self.get_limit()) 1114 1115 def get_limit(self): 1116 return self.args["values"][0] 1117 1118 def set_limit(self, limit): 1119 self.args["values"] = [limit] 1120 1121 class PositionSelector(Selector): 1122 1123 "A result set position selector." 1124 1125 def __init__(self, level, args, qualifier, selecting=None): 1126 Selector.__init__(self, level, args, qualifier, selecting) 1127 if level is not None: 1128 self.set_level(level) 1129 else: 1130 self.step = None 1131 1132 def set_level(self, level): 1133 self.level = level 1134 self.step = scale(1, self.level) 1135 1136 def materialise_items(self, context, start, end, inclusive=False): 1137 return PositionIterator(self, context, start, end, inclusive, self.step, 1138 self.get_positions()) 1139 1140 def get_positions(self): 1141 return convert_positions(sort_values(self.args["values"])) 1142 1143 def set_positions(self, positions): 1144 self.args["values"] = positions 1145 1146 class StartSelector(Selector): 1147 1148 "A selector ensuring that the start occurrence is included." 1149 1150 def materialise_items(self, context, start, end, inclusive=False): 1151 return StartIterator(self, context, start, end, inclusive, 1152 self.get_start()) 1153 1154 def get_start(self): 1155 return self.args["start"] 1156 1157 special_enum_levels = { 1158 "BYDAY" : WeekDayFilter, 1159 "BYMONTHDAY" : MonthDayFilter, 1160 "BYYEARDAY" : YearDayFilter, 1161 } 1162 1163 # Iterator classes. 1164 1165 class SelectorIterator: 1166 1167 "An iterator over selected data." 1168 1169 def __init__(self, selector, current, start, end, inclusive): 1170 1171 """ 1172 Define an iterator having the 'current' point in time, 'start' and 'end' 1173 limits, and whether the selection is 'inclusive'. 1174 """ 1175 1176 self.selector = selector 1177 self.current = current 1178 self.start = start 1179 self.end = end 1180 self.inclusive = inclusive 1181 1182 # Iterator over selections within this selection. 1183 1184 self.iterator = None 1185 1186 def __iter__(self): 1187 return self 1188 1189 def next_item(self, earliest, next): 1190 1191 """ 1192 Given the 'earliest' acceptable instance and the 'next' instance, return 1193 a list of result items. 1194 1195 Where no selection within the current instance occurs, the current 1196 instance will be returned as a result if the same or later than the 1197 earliest acceptable instance. 1198 """ 1199 1200 # Obtain an item from a selector operating within this selection. 1201 1202 selecting = self.selector.selecting 1203 1204 if selecting: 1205 1206 # Obtain an iterator for any selector within the current period. 1207 1208 if not self.iterator: 1209 self.iterator = selecting.materialise_items(self.current, 1210 earliest, next, self.inclusive) 1211 1212 # Attempt to obtain and return a value. 1213 1214 return self.iterator.next() 1215 1216 # Return items within this selection. 1217 1218 else: 1219 return self.current 1220 1221 def filter_by_period(self, result): 1222 1223 "Return whether 'result' occurs within the selection period." 1224 1225 return (self.inclusive and result <= self.end or result < self.end) and \ 1226 self.start <= result 1227 1228 def at_limit(self): 1229 1230 """ 1231 Obtain periods before the end. If inclusive and selecting in the final 1232 selector, obtain the period at the end. 1233 """ 1234 1235 inclusive = self.inclusive and not self.selector.selecting 1236 return not inclusive and self.current == self.end or \ 1237 self.current > self.end 1238 1239 class PatternIterator(SelectorIterator): 1240 1241 "An iterator for a general selection pattern." 1242 1243 def __init__(self, selector, current, start, end, inclusive, step, unit_step): 1244 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1245 self.step = step 1246 self.unit_step = unit_step 1247 1248 def next(self): 1249 1250 "Return the next value." 1251 1252 while not self.at_limit(): 1253 1254 # Increment the current datetime by the step for the next period. 1255 1256 next = update(self.current, self.step) 1257 1258 # Determine the end point of the current period. 1259 1260 current_end = update(self.current, self.unit_step) 1261 1262 # Obtain any period or periods within the bounds defined by the 1263 # current period and any contraining start and end points. 1264 1265 try: 1266 result = self.next_item(max(self.current, self.start), 1267 min(current_end, self.end)) 1268 1269 # Obtain the next period if not selecting within this period. 1270 1271 if not self.selector.selecting: 1272 self.current = next 1273 1274 # Filter out periods. 1275 1276 if self.filter_by_period(result): 1277 return result 1278 1279 # Move on to the next instance. 1280 1281 except StopIteration: 1282 self.current = next 1283 self.iterator = None 1284 1285 raise StopIteration 1286 1287 class WeekDayIterator(SelectorIterator): 1288 1289 "An iterator over weekday selections in week periods." 1290 1291 def __init__(self, selector, current, start, end, inclusive, step, values): 1292 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1293 self.step = step 1294 self.values = values 1295 1296 def next(self): 1297 1298 "Return the next value." 1299 1300 while not self.at_limit(): 1301 1302 # Increment the current datetime by the step for the next period. 1303 1304 next = update(self.current, self.step) 1305 1306 # Determine whether the day is one chosen. 1307 1308 if date(*self.current).isoweekday() in self.values: 1309 try: 1310 result = self.next_item(max(self.current, self.start), 1311 min(next, self.end)) 1312 1313 # Obtain the next period if not selecting within this period. 1314 1315 if not self.selector.selecting: 1316 self.current = next 1317 1318 return result 1319 1320 # Move on to the next instance. 1321 1322 except StopIteration: 1323 self.current = next 1324 self.iterator = None 1325 1326 else: 1327 self.current = next 1328 self.iterator = None 1329 1330 raise StopIteration 1331 1332 class EnumIterator(SelectorIterator): 1333 1334 "An iterator over specific value selections." 1335 1336 def __init__(self, selector, current, start, end, inclusive, step, values): 1337 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1338 self.step = step 1339 1340 # Derive selected periods from a base and the indicated values. 1341 1342 self.base = current 1343 1344 # Iterate over the indicated period values. 1345 1346 self.values = iter(values) 1347 self.value = None 1348 1349 def get_selected_period(self): 1350 1351 "Return the period indicated by the current value." 1352 1353 t = make_value(self.base, self.selector.level, self.value) 1354 1355 if not within_month(t): 1356 raise StopIteration 1357 1358 return t 1359 1360 def next(self): 1361 1362 "Return the next value." 1363 1364 while True: 1365 1366 # Find each of the given selected values. 1367 1368 if not self.selector.selecting or self.value is None: 1369 self.value = self.values.next() 1370 1371 try: 1372 # Select a period for each value at the current resolution. 1373 1374 self.current = self.get_selected_period() 1375 next = update(self.current, self.step) 1376 1377 # To support setpos, only current and next bound the search, not 1378 # the period in addition. 1379 1380 return self.next_item(self.current, next) 1381 1382 # Move on to the next instance. 1383 1384 except StopIteration: 1385 self.value = None 1386 self.iterator = None 1387 1388 raise StopIteration 1389 1390 class WeekDayGeneralIterator(EnumIterator): 1391 1392 "An iterator over weekday selections in month and year periods." 1393 1394 def get_selected_period(self): 1395 1396 "Return the day indicated by the current day value." 1397 1398 value, index = self.value 1399 offset = timedelta(7 * (index - 1)) 1400 weekday0 = get_first_day(self.base, value) 1401 return limit_value(to_tuple(weekday0 + offset), DAYS) 1402 1403 class YearDayFilterIterator(EnumIterator): 1404 1405 "An iterator over day-in-year selections." 1406 1407 def get_selected_period(self): 1408 1409 "Return the day indicated by the current day value." 1410 1411 offset = timedelta(self.value - 1) 1412 return limit_value(to_tuple(date(*self.base) + offset), DAYS) 1413 1414 class LimitIterator(SelectorIterator): 1415 1416 "A result set limiting iterator." 1417 1418 def __init__(self, selector, context, start, end, inclusive, limit): 1419 SelectorIterator.__init__(self, selector, context, start, end, inclusive) 1420 self.limit = limit 1421 self.count = 0 1422 1423 def next(self): 1424 1425 "Return the next value." 1426 1427 if self.count < self.limit: 1428 self.count += 1 1429 result = self.next_item(self.start, self.end) 1430 return result 1431 1432 raise StopIteration 1433 1434 class PositionIterator(SelectorIterator): 1435 1436 "An iterator over results, selecting positions." 1437 1438 def __init__(self, selector, context, start, end, inclusive, step, positions): 1439 SelectorIterator.__init__(self, selector, context, start, end, inclusive) 1440 self.step = step 1441 1442 # Positions to select. 1443 1444 self.positions = positions 1445 1446 # Queue to hold values matching the negative position values. 1447 1448 self.queue_length = positions and positions[0] < 0 and abs(positions[0]) or 0 1449 self.queue = [] 1450 1451 # Result position. 1452 1453 self.resultpos = 0 1454 1455 def next(self): 1456 1457 "Return the next value." 1458 1459 while True: 1460 try: 1461 result = self.next_item(self.start, self.end) 1462 1463 # Positive positions can have their values released immediately. 1464 1465 selected = self.resultpos in self.positions 1466 self.resultpos += 1 1467 1468 if selected: 1469 return result 1470 1471 # Negative positions must be held until this iterator completes and 1472 # then be released. 1473 1474 if self.queue_length: 1475 self.queue.append(result) 1476 if len(self.queue) > self.queue_length: 1477 del self.queue[0] 1478 1479 except StopIteration: 1480 1481 # With a queue and positions, attempt to find the referenced 1482 # positions. 1483 1484 if self.queue and self.positions: 1485 index = self.positions[0] 1486 del self.positions[0] 1487 1488 # Only negative positions are used at this point. 1489 1490 if index < 0: 1491 try: 1492 return self.queue[index] 1493 except IndexError: 1494 pass 1495 1496 # With only positive positions remaining, signal the end of 1497 # the collection. 1498 1499 else: 1500 raise 1501 1502 # With no queue or positions remaining, signal the end of the 1503 # collection. 1504 1505 else: 1506 raise 1507 1508 class StartIterator(SelectorIterator): 1509 1510 "An iterator ensuring that the start occurrence is included." 1511 1512 def __init__(self, selector, current, start, end, inclusive, start_dt): 1513 SelectorIterator.__init__(self, selector, current, start, end, inclusive) 1514 self.waiting = start_dt 1515 1516 def next(self): 1517 1518 "Return the next value, initially the start period." 1519 1520 # Obtain the next item. 1521 1522 try: 1523 result = self.next_item(self.start, self.end) 1524 except StopIteration: 1525 1526 # With no more values, flush any waiting value. 1527 1528 if self.waiting is not None: 1529 result = self.waiting 1530 self.waiting = None 1531 return result 1532 else: 1533 raise 1534 1535 # Compare with any waiting value. 1536 1537 if self.waiting is not None: 1538 1539 # Produce the waiting value, queue the latest result. 1540 1541 if result != self.waiting: 1542 result, self.waiting = self.waiting, result 1543 1544 # Remove the waiting value if identical to the latest result. 1545 1546 else: 1547 self.waiting = None 1548 1549 return result 1550 1551 def connect_selectors(selectors): 1552 1553 """ 1554 Make the 'selectors' reference each other in a hierarchy so that 1555 materialising the principal selector causes the more specific ones to be 1556 employed in the operation. 1557 """ 1558 1559 current = selectors[0] 1560 1561 for selector in selectors[1:]: 1562 current.selecting = selector 1563 current = selector 1564 1565 return selectors[0] 1566 1567 # Public functions. 1568 1569 def get_rule(dt, rule): 1570 1571 """ 1572 Using the given initial datetime 'dt', interpret the 'rule' (a semicolon- 1573 separated collection of "key=value" strings), and return the resulting 1574 selector object. 1575 """ 1576 1577 selectors = get_selectors_for_rule(rule) 1578 return get_selector(dt, selectors) 1579 1580 def get_selector(dt, selectors): 1581 1582 """ 1583 Combine the initial datetime 'dt' with the given 'selectors', returning an 1584 object that can be used to select recurrences described by the 'selectors'. 1585 """ 1586 1587 dt = to_tuple(dt) 1588 selectors = insert_start_selector(selectors, dt) 1589 return connect_selectors(combine_datetime_with_selectors(dt, selectors)) 1590 1591 def get_selectors_for_rule(rule): 1592 1593 """ 1594 Return a list of selectors implementing 'rule', useful for "explaining" how 1595 a rule works. 1596 """ 1597 1598 if not isinstance(rule, tuple): 1599 rule = (rule or "").split(";") 1600 return make_selectors(get_qualifiers(rule)) 1601 1602 def get_selectors_from_selector(selector): 1603 1604 "Return the chain of selectors from 'selector', useful for debugging." 1605 1606 if selector.selecting: 1607 return [selector] + get_selectors_from_selector(selector.selecting) 1608 else: 1609 return [selector] 1610 1611 # vim: tabstop=4 expandtab shiftwidth=4