1 #!/usr/bin/env python 2 3 """ 4 Recurrence rule calculation. 5 6 Copyright (C) 2014, 2015 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; UNTIL defines a limit to the selection. 35 36 BY... qualifiers select instances within each outer selection instance according 37 to the recurrence of instances of the next highest resolution. For example, 38 BYDAY selects days in weeks. Thus, if no explicit week recurrence is indicated, 39 all weeks are selected within the selection of the next highest explicitly 40 specified resolution, whether this is months or years. 41 42 BYSETPOS in conjunction with BY... qualifiers permit the selection of specific 43 instances. 44 45 Within the FREQ resolution, BY... qualifiers refine selected instances. 46 47 Outside the FREQ resolution, BY... qualifiers select instances at the resolution 48 concerned. 49 50 Thus, FREQ and BY... qualifiers need to be ordered in terms of increasing 51 resolution (or decreasing scope). 52 """ 53 54 from calendar import monthrange 55 from datetime import date, datetime, timedelta 56 import operator 57 58 # Frequency levels, specified by FREQ in iCalendar. 59 60 freq_levels = ( 61 "YEARLY", 62 "MONTHLY", 63 "WEEKLY", 64 None, 65 None, 66 "DAILY", 67 "HOURLY", 68 "MINUTELY", 69 "SECONDLY" 70 ) 71 72 # Enumeration levels, employed by BY... qualifiers. 73 74 enum_levels = ( 75 None, 76 "BYMONTH", 77 "BYWEEKNO", 78 "BYYEARDAY", 79 "BYMONTHDAY", 80 "BYDAY", 81 "BYHOUR", 82 "BYMINUTE", 83 "BYSECOND" 84 ) 85 86 # Map from levels to lengths of datetime tuples. 87 88 lengths = [1, 2, 3, 3, 3, 3, 4, 5, 6] 89 positions = [l-1 for l in lengths] 90 91 # Map from qualifiers to interval units. Here, weeks are defined as 7 days. 92 93 units = {"WEEKLY" : 7} 94 95 # Make dictionaries mapping qualifiers to levels. 96 97 freq = dict([(level, i) for (i, level) in enumerate(freq_levels) if level]) 98 enum = dict([(level, i) for (i, level) in enumerate(enum_levels) if level]) 99 weekdays = dict([(weekday, i+1) for (i, weekday) in enumerate(["MO", "TU", "WE", "TH", "FR", "SA", "SU"])]) 100 101 # Functions for structuring the recurrences. 102 103 def get_next(it): 104 try: 105 return it.next() 106 except StopIteration: 107 return None 108 109 def get_parameters(values): 110 111 "Return parameters from the given list of 'values'." 112 113 d = {} 114 for value in values: 115 parts = value.split("=", 1) 116 if len(parts) < 2: 117 continue 118 key, value = parts 119 if key in ("COUNT", "BYSETPOS"): 120 d[key] = int(value) 121 return d 122 123 def get_qualifiers(values): 124 125 """ 126 Process the list of 'values' of the form "key=value", returning a list of 127 qualifiers of the form (qualifier name, args). 128 """ 129 130 qualifiers = [] 131 frequency = None 132 interval = 1 133 134 for value in values: 135 parts = value.split("=", 1) 136 if len(parts) < 2: 137 continue 138 key, value = parts 139 if key == "FREQ" and freq.has_key(value): 140 qualifier = frequency = (value, {}) 141 elif key == "INTERVAL": 142 interval = int(value) 143 continue 144 elif enum.has_key(key): 145 qualifier = (key, {"values" : get_qualifier_values(key, value)}) 146 else: 147 continue 148 149 qualifiers.append(qualifier) 150 151 if frequency: 152 frequency[1]["interval"] = interval 153 154 return qualifiers 155 156 def get_qualifier_values(qualifier, value): 157 158 """ 159 For the given 'qualifier', process the 'value' string, returning a list of 160 suitable values. 161 """ 162 163 if qualifier != "BYDAY": 164 return map(int, value.split(",")) 165 166 values = [] 167 for part in value.split(","): 168 weekday = weekdays.get(part[-2:]) 169 if not weekday: 170 continue 171 index = part[:-2] 172 if index: 173 index = int(index) 174 else: 175 index = None 176 values.append((weekday, index)) 177 178 return values 179 180 def order_qualifiers(qualifiers): 181 182 "Return the 'qualifiers' in order of increasing resolution." 183 184 l = [] 185 186 for qualifier, args in qualifiers: 187 if enum.has_key(qualifier): 188 level = enum[qualifier] 189 if special_enum_levels.has_key(qualifier): 190 args["interval"] = 1 191 selector = special_enum_levels[qualifier] 192 else: 193 selector = Enum 194 else: 195 level = freq[qualifier] 196 selector = Pattern 197 198 l.append(selector(level, args, qualifier)) 199 200 l.sort(key=lambda x: x.level) 201 return l 202 203 def get_datetime_structure(datetime): 204 205 "Return the structure of 'datetime' for recurrence production." 206 207 l = [] 208 offset = 0 209 for level, value in enumerate(datetime): 210 if level == 2: 211 offset = 3 212 l.append(Enum(level + offset, {"values" : [value]}, "DT")) 213 return l 214 215 def combine_datetime_with_qualifiers(datetime, qualifiers): 216 217 """ 218 Combine 'datetime' with 'qualifiers' to produce a structure for recurrence 219 production. 220 """ 221 222 iter_dt = iter(get_datetime_structure(datetime)) 223 iter_q = iter(order_qualifiers(qualifiers)) 224 225 l = [] 226 227 from_dt = get_next(iter_dt) 228 from_q = get_next(iter_q) 229 230 have_q = False 231 context = [] 232 context.append(from_dt.args["values"][0]) 233 234 # Consume from both lists, merging entries. 235 236 while from_dt and from_q: 237 _level = from_dt.level 238 level = from_q.level 239 240 # Datetime value at wider resolution. 241 242 if _level < level: 243 from_dt = get_next(iter_dt) 244 context.append(from_dt.args["values"][0]) 245 246 # Qualifier at wider or same resolution as datetime value. 247 248 else: 249 if not have_q: 250 if isinstance(from_q, Enum) and level > 0: 251 repeat = Pattern(level - 1, {"interval" : 1}, None) 252 repeat.context = tuple(context) 253 l.append(repeat) 254 have_q = True 255 256 from_q.context = tuple(context) 257 l.append(from_q) 258 from_q = get_next(iter_q) 259 260 if _level == level: 261 from_dt = get_next(iter_dt) 262 context.append(from_dt.args["values"][0]) 263 264 # Complete the list. 265 266 while from_dt: 267 l.append(from_dt) 268 from_dt = get_next(iter_dt) 269 270 while from_q: 271 if not have_q: 272 if isinstance(from_q, Enum) and level > 0: 273 repeat = Pattern(level - 1, {"interval" : 1}, None) 274 repeat.context = tuple(context) 275 l.append(repeat) 276 have_q = True 277 278 from_q.context = tuple(context) 279 l.append(from_q) 280 from_q = get_next(iter_q) 281 282 return l 283 284 # Datetime arithmetic. 285 286 def combine(t1, t2): 287 288 """ 289 Combine tuples 't1' and 't2', returning a copy of 't1' filled with values 290 from 't2' in positions where 0 appeared in 't1'. 291 """ 292 293 return tuple(map(lambda x, y: x or y, t1, t2)) 294 295 def scale(interval, pos): 296 297 """ 298 Scale the given 'interval' value to the indicated position 'pos', returning 299 a tuple with leading zero elements and 'interval' at the stated position. 300 """ 301 302 return (0,) * pos + (interval,) 303 304 def get_seconds(t): 305 306 "Convert the sub-day part of 't' into seconds." 307 308 t = t + (0,) * (6 - len(t)) 309 return (t[3] * 60 + t[4]) * 60 + t[5] 310 311 def update(t, step): 312 313 "Update 't' by 'step' at the resolution of 'step'." 314 315 i = len(step) 316 317 # Years only. 318 319 if i == 1: 320 return (t[0] + step[0],) + tuple(t[1:]) 321 322 # Years and months. 323 324 elif i == 2: 325 month = t[1] + step[1] 326 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 327 328 # Dates and datetimes. 329 330 else: 331 updated_for_months = update(t, step[:2]) 332 333 # Dates only. 334 335 if i == 3: 336 d = datetime(*updated_for_months) 337 s = timedelta(step[2]) 338 339 # Datetimes. 340 341 else: 342 d = datetime(*updated_for_months) 343 s = timedelta(step[2], get_seconds(step)) 344 345 return to_tuple(d + s, len(t)) 346 347 def to_tuple(d, n=None): 348 349 "Return 'd' as a tuple, optionally trimming the result to 'n' positions." 350 351 if not isinstance(d, date): 352 return d 353 if n is None: 354 if isinstance(d, datetime): 355 n = 6 356 else: 357 n = 3 358 return d.timetuple()[:n] 359 360 def get_first_day(first_day, weekday): 361 362 "Return the first occurrence at or after 'first_day' of 'weekday'." 363 364 first_day = date(*first_day) 365 first_weekday = first_day.isoweekday() 366 if first_weekday > weekday: 367 return first_day + timedelta(7 - first_weekday + weekday) 368 else: 369 return first_day + timedelta(weekday - first_weekday) 370 371 def get_last_day(last_day, weekday): 372 373 "Return the last occurrence at or before 'last_day' of 'weekday'." 374 375 last_day = date(*last_day) 376 last_weekday = last_day.isoweekday() 377 if last_weekday < weekday: 378 return last_day - timedelta(last_weekday + 7 - weekday) 379 else: 380 return last_day - timedelta(last_weekday - weekday) 381 382 # Classes for producing instances from recurrence structures. 383 384 class Selector: 385 386 "A generic selector." 387 388 def __init__(self, level, args, qualifier, selecting=None): 389 390 """ 391 Initialise at the given 'level' a selector employing the given 'args' 392 defined in the interpretation of recurrence rule qualifiers, with the 393 'qualifier' being the name of the rule qualifier, and 'selecting' being 394 an optional selector used to find more specific instances from those 395 found by this selector. 396 """ 397 398 self.level = level 399 self.pos = positions[level] 400 self.args = args 401 self.qualifier = qualifier 402 self.context = () 403 self.selecting = selecting 404 405 def __repr__(self): 406 return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.level, self.args, self.qualifier, self.context) 407 408 def materialise(self, start, end, count=None, setpos=None, inclusive=False): 409 410 """ 411 Starting at 'start', materialise instances up to but not including any 412 at 'end' or later, returning at most 'count' if specified, and returning 413 only the occurrences indicated by 'setpos' if specified. A list of 414 instances is returned. 415 416 If 'inclusive' is specified, the selection of instances will include the 417 end of the search period if present in the results. 418 """ 419 420 start = to_tuple(start) 421 end = to_tuple(end) 422 counter = count and [0, count] 423 results = self.materialise_items(self.context, start, end, counter, setpos, inclusive) 424 results.sort() 425 return results[:count] 426 427 def materialise_item(self, current, earliest, next, counter, setpos=None, inclusive=False): 428 429 """ 430 Given the 'current' instance, the 'earliest' acceptable instance, the 431 'next' instance, an instance 'counter', and the optional 'setpos' 432 criteria, return a list of result items. Where no selection within the 433 current instance occurs, the current instance will be returned as a 434 result if the same or later than the earliest acceptable instance. 435 """ 436 437 if self.selecting: 438 return self.selecting.materialise_items(current, earliest, next, counter, setpos, inclusive) 439 elif earliest <= current: 440 return [current] 441 else: 442 return [] 443 444 def convert_positions(self, setpos): 445 446 "Convert 'setpos' to 0-based indexes." 447 448 l = [] 449 for pos in setpos: 450 lower = pos < 0 and pos or pos - 1 451 upper = pos > 0 and pos or pos < -1 and pos + 1 or None 452 l.append((lower, upper)) 453 return l 454 455 def select_positions(self, results, setpos): 456 457 "Select in 'results' the 1-based positions given by 'setpos'." 458 459 results.sort() 460 l = [] 461 for lower, upper in self.convert_positions(setpos): 462 l += results[lower:upper] 463 return l 464 465 def filter_by_period(self, results, start, end, inclusive): 466 467 """ 468 Filter 'results' so that only those at or after 'start' and before 'end' 469 are returned. 470 471 If 'inclusive' is specified, the selection of instances will include the 472 end of the search period if present in the results. 473 """ 474 475 l = [] 476 for result in results: 477 if start <= result and (inclusive and result <= end or result < end): 478 l.append(result) 479 return l 480 481 class Pattern(Selector): 482 483 "A selector of instances according to a repeating pattern." 484 485 def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): 486 first = scale(self.context[self.pos], self.pos) 487 488 # Define the step between items. 489 490 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 491 step = scale(interval, self.pos) 492 493 # Define the scale of a single item. 494 495 unit_interval = units.get(self.qualifier, 1) 496 unit_step = scale(unit_interval, self.pos) 497 498 current = combine(context, first) 499 results = [] 500 501 while (inclusive and current <= end or current < end) and (counter is None or counter[0] < counter[1]): 502 next = update(current, step) 503 current_end = update(current, unit_step) 504 interval_results = self.materialise_item(current, max(current, start), min(current_end, end), counter, setpos, inclusive) 505 if counter is not None: 506 counter[0] += len(interval_results) 507 results += interval_results 508 current = next 509 510 return results 511 512 class WeekDayFilter(Selector): 513 514 "A selector of instances specified in terms of day numbers." 515 516 def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): 517 step = scale(1, 2) 518 results = [] 519 520 # Get weekdays in the year. 521 522 if len(context) == 1: 523 first_day = (context[0], 1, 1) 524 last_day = (context[0], 12, 31) 525 526 # Get weekdays in the month. 527 528 elif len(context) == 2: 529 first_day = (context[0], context[1], 1) 530 last_day = update((context[0], context[1], 1), (0, 1, 0)) 531 last_day = update(last_day, (0, 0, -1)) 532 533 # Get weekdays in the week. 534 535 else: 536 current = context 537 values = [value for (value, index) in self.args["values"]] 538 539 while (inclusive and current <= end or current < end): 540 next = update(current, step) 541 if date(*current).isoweekday() in values: 542 results += self.materialise_item(current, max(current, start), min(next, end), counter, inclusive=inclusive) 543 current = next 544 545 if setpos: 546 return self.select_positions(results, setpos) 547 else: 548 return results 549 550 # Find each of the given days. 551 552 for value, index in self.args["values"]: 553 if index is not None: 554 offset = timedelta(7 * (abs(index) - 1)) 555 556 if index < 0: 557 current = to_tuple(get_last_day(last_day, value) - offset, 3) 558 else: 559 current = to_tuple(get_first_day(first_day, value) + offset, 3) 560 561 next = update(current, step) 562 563 # To support setpos, only current and next bound the search, not 564 # the period in addition. 565 566 results += self.materialise_item(current, current, next, counter, inclusive=inclusive) 567 568 else: 569 if index < 0: 570 current = to_tuple(get_last_day(last_day, value), 3) 571 direction = operator.sub 572 else: 573 current = to_tuple(get_first_day(first_day, value), 3) 574 direction = operator.add 575 576 while first_day <= current <= last_day: 577 next = update(current, step) 578 579 # To support setpos, only current and next bound the search, not 580 # the period in addition. 581 582 results += self.materialise_item(current, current, next, counter, inclusive=inclusive) 583 current = to_tuple(direction(date(*current), timedelta(7)), 3) 584 585 # Extract selected positions and remove out-of-period instances. 586 587 if setpos: 588 results = self.select_positions(results, setpos) 589 590 return self.filter_by_period(results, start, end, inclusive) 591 592 class Enum(Selector): 593 def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): 594 step = scale(1, self.pos) 595 results = [] 596 for value in self.args["values"]: 597 current = combine(context, scale(value, self.pos)) 598 next = update(current, step) 599 600 # To support setpos, only current and next bound the search, not 601 # the period in addition. 602 603 results += self.materialise_item(current, current, next, counter, setpos, inclusive) 604 605 # Extract selected positions and remove out-of-period instances. 606 607 if setpos: 608 results = self.select_positions(results, setpos) 609 610 return self.filter_by_period(results, start, end, inclusive) 611 612 class MonthDayFilter(Enum): 613 def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): 614 last_day = monthrange(context[0], context[1])[1] 615 step = scale(1, self.pos) 616 results = [] 617 for value in self.args["values"]: 618 if value < 0: 619 value = last_day + 1 + value 620 current = combine(context, scale(value, self.pos)) 621 next = update(current, step) 622 623 # To support setpos, only current and next bound the search, not 624 # the period in addition. 625 626 results += self.materialise_item(current, current, next, counter, inclusive=inclusive) 627 628 # Extract selected positions and remove out-of-period instances. 629 630 if setpos: 631 results = self.select_positions(results, setpos) 632 633 return self.filter_by_period(results, start, end, inclusive) 634 635 class YearDayFilter(Enum): 636 def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False): 637 first_day = date(context[0], 1, 1) 638 next_first_day = date(context[0] + 1, 1, 1) 639 year_length = (next_first_day - first_day).days 640 step = scale(1, self.pos) 641 results = [] 642 for value in self.args["values"]: 643 if value < 0: 644 value = year_length + 1 + value 645 current = to_tuple(first_day + timedelta(value - 1), 3) 646 next = update(current, step) 647 648 # To support setpos, only current and next bound the search, not 649 # the period in addition. 650 651 results += self.materialise_item(current, current, next, counter, inclusive=inclusive) 652 653 # Extract selected positions and remove out-of-period instances. 654 655 if setpos: 656 results = self.select_positions(results, setpos) 657 658 return self.filter_by_period(results, start, end, inclusive) 659 660 special_enum_levels = { 661 "BYDAY" : WeekDayFilter, 662 "BYMONTHDAY" : MonthDayFilter, 663 "BYYEARDAY" : YearDayFilter, 664 } 665 666 # Public functions. 667 668 def connect_selectors(selectors): 669 670 """ 671 Make the 'selectors' reference each other in a hierarchy so that 672 materialising the principal selector causes the more specific ones to be 673 employed in the operation. 674 """ 675 676 current = selectors[0] 677 for selector in selectors[1:]: 678 current.selecting = selector 679 current = selector 680 return selectors[0] 681 682 def get_selector(dt, qualifiers): 683 684 """ 685 Combine the initial datetime 'dt' with the given 'qualifiers', returning an 686 object that can be used to select recurrences described by the 'qualifiers'. 687 """ 688 689 dt = to_tuple(dt) 690 return connect_selectors(combine_datetime_with_qualifiers(dt, qualifiers)) 691 692 def get_rule(dt, rule): 693 694 """ 695 Using the given initial datetime 'dt', interpret the 'rule' (a semicolon- 696 separated collection of "key=value" strings), and return the resulting 697 selector object. 698 """ 699 700 if not isinstance(rule, tuple): 701 rule = rule.split(";") 702 qualifiers = get_qualifiers(rule) 703 return get_selector(dt, qualifiers) 704 705 # vim: tabstop=4 expandtab shiftwidth=4