1 #!/usr/bin/env python 2 3 """ 4 Recurrence rule calculation. 5 6 Copyright (C) 2014 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 100 # Functions for structuring the recurrences. 101 102 def get_next(it): 103 try: 104 return it.next() 105 except StopIteration: 106 return None 107 108 def order_qualifiers(qualifiers): 109 110 "Return the 'qualifiers' in order of increasing resolution." 111 112 l = [] 113 114 for qualifier, args in qualifiers: 115 if enum.has_key(qualifier): 116 level = enum[qualifier] 117 if special_enum_levels.has_key(qualifier): 118 args["interval"] = 1 119 selector = special_enum_levels[qualifier] 120 else: 121 selector = Enum 122 else: 123 level = freq[qualifier] 124 selector = Pattern 125 126 l.append(selector(level, args, qualifier)) 127 128 l.sort(key=lambda x: x.level) 129 return l 130 131 def get_datetime_structure(datetime): 132 133 "Return the structure of 'datetime' for recurrence production." 134 135 l = [] 136 offset = 0 137 for level, value in enumerate(datetime): 138 if level == 2: 139 offset = 3 140 l.append(Enum(level + offset, {"values" : [value]}, "DT")) 141 return l 142 143 def combine_datetime_with_qualifiers(datetime, qualifiers): 144 145 """ 146 Combine 'datetime' with 'qualifiers' to produce a structure for recurrence 147 production. 148 """ 149 150 iter_dt = iter(get_datetime_structure(datetime)) 151 iter_q = iter(order_qualifiers(qualifiers)) 152 153 l = [] 154 155 from_dt = get_next(iter_dt) 156 from_q = get_next(iter_q) 157 158 have_q = False 159 context = [] 160 context.append(from_dt.args["values"][0]) 161 162 # Consume from both lists, merging entries. 163 164 while from_dt and from_q: 165 _level = from_dt.level 166 level = from_q.level 167 168 # Datetime value at wider resolution. 169 170 if _level < level: 171 from_dt = get_next(iter_dt) 172 context.append(from_dt.args["values"][0]) 173 174 # Qualifier at wider or same resolution as datetime value. 175 176 else: 177 if not have_q: 178 if isinstance(from_q, Enum) and level > 0: 179 repeat = Pattern(level - 1, {"interval" : 1}, None) 180 repeat.context = tuple(context) 181 l.append(repeat) 182 have_q = True 183 184 from_q.context = tuple(context) 185 l.append(from_q) 186 from_q = get_next(iter_q) 187 188 if _level == level: 189 from_dt = get_next(iter_dt) 190 context.append(from_dt.args["values"][0]) 191 192 # Complete the list. 193 194 while from_dt: 195 l.append(from_dt) 196 from_dt = get_next(iter_dt) 197 198 while from_q: 199 if not have_q: 200 if isinstance(from_q, Enum) and level > 0: 201 repeat = Pattern(level - 1, {"interval" : 1}, None) 202 repeat.context = tuple(context) 203 l.append(repeat) 204 have_q = True 205 206 from_q.context = tuple(context) 207 l.append(from_q) 208 from_q = get_next(iter_q) 209 210 return l 211 212 # Datetime arithmetic. 213 214 def combine(t1, t2): 215 return tuple(map(lambda x, y: x or y, t1, t2)) 216 217 def scale(interval, pos): 218 return (0,) * pos + (interval,) 219 220 def get_seconds(t): 221 222 "Convert the sub-day part of 't' into seconds." 223 224 t = t + (0,) * (6 - len(t)) 225 return (t[3] * 60 + t[4]) * 60 + t[5] 226 227 def update(t, step): 228 229 "Update 't' by 'step' at the resolution of 'step'." 230 231 i = len(step) 232 233 # Years only. 234 235 if i == 1: 236 return (t[0] + step[0],) + tuple(t[1:]) 237 238 # Years and months. 239 240 elif i == 2: 241 month = t[1] + step[1] 242 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 243 244 # Dates and datetimes. 245 246 else: 247 updated_for_months = update(t, step[:2]) 248 249 # Dates only. 250 251 if i == 3: 252 d = datetime(*updated_for_months) 253 s = timedelta(step[2]) 254 255 # Datetimes. 256 257 else: 258 d = datetime(*updated_for_months) 259 s = timedelta(step[2], get_seconds(step)) 260 261 return to_tuple(d + s, len(t)) 262 263 def to_tuple(d, n): 264 return d.timetuple()[:n] 265 266 def get_first_day(first_day, weekday): 267 first_day = date(*first_day) 268 first_weekday = first_day.isoweekday() 269 if first_weekday > weekday: 270 return first_day + timedelta(7 - first_weekday + weekday) 271 else: 272 return first_day + timedelta(weekday - first_weekday) 273 274 def get_last_day(last_day, weekday): 275 last_day = date(*last_day) 276 last_weekday = last_day.isoweekday() 277 if last_weekday < weekday: 278 return last_day - timedelta(last_weekday + 7 - weekday) 279 else: 280 return last_day - timedelta(last_weekday - weekday) 281 282 # Classes for producing instances from recurrence structures. 283 284 class Selector: 285 def __init__(self, level, args, qualifier, selecting=None): 286 self.level = level 287 self.pos = positions[level] 288 self.args = args 289 self.qualifier = qualifier 290 self.context = () 291 self.selecting = selecting 292 293 def __repr__(self): 294 return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.level, self.args, self.qualifier, self.context) 295 296 def materialise(self, start, end, count=None, setpos=None): 297 counter = count and [0, count] 298 results = self.materialise_items(self.context, start, end, counter, setpos) 299 results.sort() 300 return results[:count] 301 302 def materialise_item(self, current, last, next, counter, setpos=None): 303 if self.selecting: 304 return self.selecting.materialise_items(current, last, next, counter, setpos) 305 elif last <= current: 306 return [current] 307 else: 308 return [] 309 310 def convert_positions(self, setpos): 311 l = [] 312 for pos in setpos: 313 lower = pos < 0 and pos or pos - 1 314 upper = pos > 0 and pos or pos < -1 and pos + 1 or None 315 l.append((lower, upper)) 316 return l 317 318 def select_positions(self, results, setpos): 319 results.sort() 320 l = [] 321 for lower, upper in self.convert_positions(setpos): 322 l += results[lower:upper] 323 return l 324 325 def filter_by_period(self, results, start, end): 326 l = [] 327 for result in results: 328 if start <= result < end: 329 l.append(result) 330 return l 331 332 class Pattern(Selector): 333 def materialise_items(self, context, start, end, counter, setpos=None): 334 first = scale(self.context[self.pos], self.pos) 335 336 # Define the step between items. 337 338 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 339 step = scale(interval, self.pos) 340 341 # Define the scale of a single item. 342 343 unit_interval = units.get(self.qualifier, 1) 344 unit_step = scale(unit_interval, self.pos) 345 346 current = combine(context, first) 347 results = [] 348 349 while current < end and (counter is None or counter[0] < counter[1]): 350 next = update(current, step) 351 current_end = update(current, unit_step) 352 interval_results = self.materialise_item(current, max(current, start), min(current_end, end), counter, setpos) 353 if counter is not None: 354 counter[0] += len(interval_results) 355 results += interval_results 356 current = next 357 358 return results 359 360 class WeekDayFilter(Selector): 361 def materialise_items(self, context, start, end, counter, setpos=None): 362 step = scale(1, 2) 363 results = [] 364 365 # Get weekdays in the year. 366 367 if len(context) == 1: 368 first_day = (context[0], 1, 1) 369 last_day = (context[0], 12, 31) 370 371 # Get weekdays in the month. 372 373 elif len(context) == 2: 374 first_day = (context[0], context[1], 1) 375 last_day = update((context[0], context[1], 1), (0, 1, 0)) 376 last_day = update(last_day, (0, 0, -1)) 377 378 # Get weekdays in the week. 379 380 else: 381 current = context 382 values = [value for (value, index) in self.args["values"]] 383 384 while current < end: 385 next = update(current, step) 386 if date(*current).isoweekday() in values: 387 results += self.materialise_item(current, max(current, start), min(next, end), counter) 388 current = next 389 390 if setpos: 391 return self.select_positions(results, setpos) 392 else: 393 return results 394 395 # Find each of the given days. 396 397 for value, index in self.args["values"]: 398 if index is not None: 399 offset = timedelta(7 * (abs(index) - 1)) 400 401 if index < 0: 402 current = to_tuple(get_last_day(last_day, value) - offset, 3) 403 else: 404 current = to_tuple(get_first_day(first_day, value) + offset, 3) 405 406 next = update(current, step) 407 408 # To support setpos, only current and next bound the search, not 409 # the period in addition. 410 411 results += self.materialise_item(current, current, next, counter) 412 413 else: 414 if index < 0: 415 current = to_tuple(get_last_day(last_day, value), 3) 416 direction = operator.sub 417 else: 418 current = to_tuple(get_first_day(first_day, value), 3) 419 direction = operator.add 420 421 while first_day <= current <= last_day: 422 next = update(current, step) 423 424 # To support setpos, only current and next bound the search, not 425 # the period in addition. 426 427 results += self.materialise_item(current, current, next, counter) 428 current = to_tuple(direction(date(*current), timedelta(7)), 3) 429 430 # Extract selected positions and remove out-of-period instances. 431 432 if setpos: 433 results = self.select_positions(results, setpos) 434 435 return self.filter_by_period(results, start, end) 436 437 class Enum(Selector): 438 def materialise_items(self, context, start, end, counter, setpos=None): 439 step = scale(1, self.pos) 440 results = [] 441 for value in self.args["values"]: 442 current = combine(context, scale(value, self.pos)) 443 next = update(current, step) 444 445 # To support setpos, only current and next bound the search, not 446 # the period in addition. 447 448 results += self.materialise_item(current, current, next, counter, setpos) 449 450 # Extract selected positions and remove out-of-period instances. 451 452 if setpos: 453 results = self.select_positions(results, setpos) 454 455 return self.filter_by_period(results, start, end) 456 457 class MonthDayFilter(Enum): 458 def materialise_items(self, context, start, end, counter, setpos=None): 459 last_day = monthrange(context[0], context[1])[1] 460 step = scale(1, self.pos) 461 results = [] 462 for value in self.args["values"]: 463 if value < 0: 464 value = last_day + 1 + value 465 current = combine(context, scale(value, self.pos)) 466 next = update(current, step) 467 468 # To support setpos, only current and next bound the search, not 469 # the period in addition. 470 471 results += self.materialise_item(current, current, next, counter) 472 473 # Extract selected positions and remove out-of-period instances. 474 475 if setpos: 476 results = self.select_positions(results, setpos) 477 478 return self.filter_by_period(results, start, end) 479 480 class YearDayFilter(Enum): 481 def materialise_items(self, context, start, end, counter, setpos=None): 482 first_day = date(context[0], 1, 1) 483 next_first_day = date(context[0] + 1, 1, 1) 484 year_length = (next_first_day - first_day).days 485 step = scale(1, self.pos) 486 results = [] 487 for value in self.args["values"]: 488 if value < 0: 489 value = year_length + 1 + value 490 current = to_tuple(first_day + timedelta(value - 1), 3) 491 next = update(current, step) 492 493 # To support setpos, only current and next bound the search, not 494 # the period in addition. 495 496 results += self.materialise_item(current, current, next, counter) 497 498 # Extract selected positions and remove out-of-period instances. 499 500 if setpos: 501 results = self.select_positions(results, setpos) 502 503 return self.filter_by_period(results, start, end) 504 505 def process(selectors): 506 current = selectors[0] 507 for selector in selectors[1:]: 508 current.selecting = selector 509 current = selector 510 return selectors[0] 511 512 special_enum_levels = { 513 "BYDAY" : WeekDayFilter, 514 "BYMONTHDAY" : MonthDayFilter, 515 "BYYEARDAY" : YearDayFilter, 516 } 517 518 # vim: tabstop=4 expandtab shiftwidth=4