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