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 "SECONDLY", 62 "MINUTELY", 63 "HOURLY", 64 "DAILY", 65 "WEEKLY", 66 "MONTHLY", 67 "YEARLY" 68 ) 69 70 # Enumeration levels, employed by BY... qualifiers. 71 72 enum_levels = ( 73 ("BYSECOND",), 74 ("BYMINUTE",), 75 ("BYHOUR",), 76 ("BYDAY", "BYMONTHDAY", "BYYEARDAY"), 77 ("BYWEEKNO",), 78 ("BYMONTH",) 79 ) 80 81 # Map from levels to lengths of datetime tuples. 82 83 lengths = [6, 5, 4, 3, 3, 2, 1] 84 positions = [l-1 for l in lengths] 85 86 # Map from qualifiers to interval units. Here, weeks are defined as 7 days. 87 88 units = {"WEEKLY" : 7} 89 90 # Map from tuple positions to base values at each resolution. 91 92 bases = [0, 1, 1, 0, 0, 0] 93 94 def basevalue(resolution): 95 return bases[positions[resolution]] 96 97 # Make dictionaries mapping qualifiers to levels. 98 99 freq = dict([(level, i) for (i, level) in enumerate(freq_levels)]) 100 enum = dict([(level, i) for (i, levels) in enumerate(enum_levels) for level in levels]) 101 102 # Functions for structuring the recurrences. 103 104 def get_next(it): 105 try: 106 return it.next() 107 except StopIteration: 108 return None 109 110 def order_qualifiers(qualifiers): 111 112 "Return the 'qualifiers' in order of increasing resolution." 113 114 l = [] 115 116 for qualifier, args in qualifiers: 117 if enum.has_key(qualifier): 118 level = enum[qualifier] 119 if special_enum_levels.has_key(qualifier): 120 args["interval"] = 1 121 selector = special_enum_levels[qualifier] 122 else: 123 selector = Enum 124 else: 125 level = freq[qualifier] 126 selector = Pattern 127 128 pos = positions[level] 129 l.append(selector(pos, args, qualifier)) 130 131 l.sort(key=lambda x: x.pos) 132 return l 133 134 def get_datetime_structure(datetime): 135 136 "Return the structure of 'datetime' for recurrence production." 137 138 l = [] 139 for pos, value in enumerate(datetime): 140 l.append(Enum(pos, {"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 _pos = from_dt.pos 166 pos = from_q.pos 167 168 # Datetime value at wider resolution. 169 170 if _pos < pos: 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 pos > 0: 179 repeat = Pattern(pos - 1, {"interval" : 1}, "REPEAT") 180 repeat.context = tuple(context) 181 l.append(repeat) 182 else: 183 from_q.context = tuple(context) 184 have_q = True 185 186 # Either introduce the qualifier first. 187 188 if _pos > pos: 189 l.append(from_q) 190 191 # Or combine the qualifier and value details. 192 193 else: 194 l.append(combine_context_with_qualifier(context, from_q)) 195 from_dt = get_next(iter_dt) 196 context.append(from_dt.args["values"][0]) 197 198 from_q = get_next(iter_q) 199 200 # Complete the list. 201 202 while from_dt: 203 l.append(from_dt) 204 from_dt = get_next(iter_dt) 205 206 while from_q: 207 if not have_q: 208 if isinstance(from_q, Enum) and pos > 0: 209 repeat = Pattern(pos - 1, {"interval" : 1}, "REPEAT") 210 repeat.context = tuple(context) 211 l.append(repeat) 212 else: 213 from_q.context = tuple(context) 214 have_q = True 215 l.append(from_q) 216 from_q = get_next(iter_q) 217 218 return l 219 220 def combine_context_with_qualifier(context, from_q): 221 222 """ 223 Combine 'context' information (a datetime) and 'from_q' (a qualifier), 224 imposing the datetime value information on any qualifiers. 225 """ 226 227 from_q.context = tuple(context) 228 return from_q 229 230 # Datetime arithmetic. 231 232 def combine(t1, t2): 233 return tuple(map(lambda x, y: x or y, t1, t2)) 234 235 def scale(interval, pos): 236 return (0,) * pos + (interval,) 237 238 def get_seconds(t): 239 240 "Convert the sub-day part of 't' into seconds." 241 242 t = t + (0,) * (6 - len(t)) 243 return (t[3] * 60 + t[4]) * 60 + t[5] 244 245 def update(t, step): 246 247 "Update 't' by 'step' at the resolution of 'step'." 248 249 i = len(step) 250 251 # Years only. 252 253 if i == 1: 254 return (t[0] + step[0],) + tuple(t[1:]) 255 256 # Years and months. 257 258 elif i == 2: 259 month = t[1] + step[1] 260 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 261 262 # Dates and datetimes. 263 264 else: 265 updated_for_months = update(t, step[:2]) 266 267 # Dates only. 268 269 if i == 3: 270 d = datetime(*updated_for_months) 271 s = timedelta(step[2]) 272 273 # Datetimes. 274 275 else: 276 d = datetime(*updated_for_months) 277 s = timedelta(step[2], get_seconds(step)) 278 279 return to_tuple(d + s, len(t)) 280 281 def to_tuple(d, n): 282 return d.timetuple()[:n] 283 284 def get_first_day(first_day, weekday): 285 first_day = date(*first_day) 286 first_weekday = first_day.isoweekday() 287 if first_weekday > weekday: 288 return first_day + timedelta(7 - first_weekday + weekday) 289 else: 290 return first_day + timedelta(weekday - first_weekday) 291 292 def get_last_day(last_day, weekday): 293 last_day = date(*last_day) 294 last_weekday = last_day.isoweekday() 295 if last_weekday < weekday: 296 return last_day - timedelta(last_weekday + 7 - weekday) 297 else: 298 return last_day - timedelta(last_weekday - weekday) 299 300 # Classes for producing instances from recurrence structures. 301 302 class Selector: 303 def __init__(self, pos, args, qualifier, selecting=None): 304 self.pos = pos 305 self.args = args 306 self.qualifier = qualifier 307 self.context = () 308 self.selecting = selecting 309 310 def __repr__(self): 311 return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.pos, self.args, self.qualifier, self.context) 312 313 def materialise(self, start, end, count=None): 314 counter = count and [0, count] 315 results = self.materialise_items(self.context, start, end, counter) 316 results.sort() 317 return results 318 319 def materialise_item(self, current, last, next, counter): 320 if counter is None or counter[0] < counter[1]: 321 if self.selecting: 322 return self.selecting.materialise_items(current, last, next, counter) 323 elif last <= current: 324 if counter is not None: 325 counter[0] += 1 326 return [current] 327 return [] 328 329 class Pattern(Selector): 330 def materialise_items(self, context, start, end, counter): 331 first = scale(self.context[self.pos], self.pos) 332 333 # Define the step between items. 334 335 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 336 step = scale(interval, self.pos) 337 338 # Define the scale of a single item. 339 340 unit_interval = units.get(self.qualifier, 1) 341 unit_step = scale(unit_interval, self.pos) 342 343 current = combine(context, first) 344 results = [] 345 346 while current < end and (counter is None or counter[0] < counter[1]): 347 next = update(current, step) 348 current_end = update(current, unit_step) 349 results += self.materialise_item(current, max(current, start), min(current_end, end), counter) 350 current = next 351 352 return results 353 354 class WeekDayFilter(Selector): 355 def materialise_items(self, context, start, end, counter): 356 step = scale(1, 2) 357 results = [] 358 359 # Get weekdays in the year. 360 361 if len(context) == 1: 362 first_day = (context[0], 1, 1) 363 last_day = (context[0], 12, 31) 364 365 # Get weekdays in the month. 366 367 elif len(context) == 2: 368 first_day = (context[0], context[1], 1) 369 last_day = update((context[0], context[1], 1), (0, 1, 0)) 370 last_day = update(last_day, (0, 0, -1)) 371 372 # Get weekdays in the week. 373 374 else: 375 current = context 376 values = [value for (value, index) in self.args["values"]] 377 378 while current < end and (counter is None or counter[0] < counter[1]): 379 next = update(current, step) 380 if date(*current).isoweekday() in values: 381 results += self.materialise_item(current, max(current, start), min(next, end), counter) 382 current = next 383 return results 384 385 # Find each of the given days. 386 387 for value, index in self.args["values"]: 388 if index is not None: 389 offset = timedelta(7 * (abs(index) - 1)) 390 391 if index < 0: 392 current = to_tuple(get_last_day(last_day, value) - offset, 3) 393 else: 394 current = to_tuple(get_first_day(first_day, value) + offset, 3) 395 396 if current < end and (counter is None or counter[0] < counter[1]): 397 next = update(current, step) 398 results += self.materialise_item(current, max(current, start), min(next, end), counter) 399 400 else: 401 if index < 0: 402 current = to_tuple(get_last_day(last_day, value), 3) 403 direction = operator.sub 404 else: 405 current = to_tuple(get_first_day(first_day, value), 3) 406 direction = operator.add 407 408 while first_day <= current <= last_day: 409 if current < end and (counter is None or counter[0] < counter[1]): 410 next = update(current, step) 411 results += self.materialise_item(current, max(current, start), min(next, end), counter) 412 current = to_tuple(direction(date(*current), timedelta(7)), 3) 413 414 return results 415 416 class Enum(Selector): 417 def materialise_items(self, context, start, end, counter): 418 step = scale(1, self.pos) 419 results = [] 420 for value in self.args["values"]: 421 current = combine(context, scale(value, self.pos)) 422 if current < end and (counter is None or counter[0] < counter[1]): 423 next = update(current, step) 424 results += self.materialise_item(current, max(current, start), min(next, end), counter) 425 return results 426 427 class MonthDayFilter(Enum): 428 def materialise_items(self, context, start, end, counter): 429 last_day = monthrange(context[0], context[1])[1] 430 step = scale(1, self.pos) 431 results = [] 432 for value in self.args["values"]: 433 if value < 0: 434 value = last_day + 1 + value 435 current = combine(context, scale(value, self.pos)) 436 if current < end and (counter is None or counter[0] < counter[1]): 437 next = update(current, step) 438 results += self.materialise_item(current, max(current, start), min(next, end), counter) 439 return results 440 441 class YearDayFilter(Enum): 442 def materialise_items(self, context, start, end, counter): 443 first_day = date(context[0], 1, 1) 444 next_first_day = date(context[0] + 1, 1, 1) 445 year_length = (next_first_day - first_day).days 446 step = scale(1, self.pos) 447 results = [] 448 for value in self.args["values"]: 449 if value < 0: 450 value = year_length + 1 + value 451 current = to_tuple(first_day + timedelta(value - 1), 3) 452 if current < end and (counter is None or counter[0] < counter[1]): 453 next = update(current, step) 454 results += self.materialise_item(current, max(current, start), min(next, end), counter) 455 return results 456 457 def process(selectors): 458 current = selectors[0] 459 for selector in selectors[1:]: 460 current.selecting = selector 461 current = selector 462 return selectors[0] 463 464 special_enum_levels = { 465 "BYDAY" : WeekDayFilter, 466 "BYMONTHDAY" : MonthDayFilter, 467 "BYYEARDAY" : YearDayFilter, 468 } 469 470 # vim: tabstop=4 expandtab shiftwidth=4