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}, "REPEAT") 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}, "REPEAT") 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): 297 counter = count and [0, count] 298 results = self.materialise_items(self.context, start, end, counter) 299 results.sort() 300 return results[:count] 301 302 def materialise_item(self, current, last, next, counter): 303 if counter is None or counter[0] < counter[1]: 304 if self.selecting: 305 return self.selecting.materialise_items(current, last, next, counter) 306 elif last <= current: 307 if counter is not None: 308 counter[0] += 1 309 return [current] 310 return [] 311 312 class Pattern(Selector): 313 def materialise_items(self, context, start, end, counter): 314 first = scale(self.context[self.pos], self.pos) 315 316 # Define the step between items. 317 318 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 319 step = scale(interval, self.pos) 320 321 # Define the scale of a single item. 322 323 unit_interval = units.get(self.qualifier, 1) 324 unit_step = scale(unit_interval, self.pos) 325 326 current = combine(context, first) 327 results = [] 328 329 while current < end and (counter is None or counter[0] < counter[1]): 330 next = update(current, step) 331 current_end = update(current, unit_step) 332 results += self.materialise_item(current, max(current, start), min(current_end, end), counter) 333 current = next 334 335 return results 336 337 class WeekDayFilter(Selector): 338 def materialise_items(self, context, start, end, counter): 339 step = scale(1, 2) 340 results = [] 341 342 # Get weekdays in the year. 343 344 if len(context) == 1: 345 first_day = (context[0], 1, 1) 346 last_day = (context[0], 12, 31) 347 348 # Get weekdays in the month. 349 350 elif len(context) == 2: 351 first_day = (context[0], context[1], 1) 352 last_day = update((context[0], context[1], 1), (0, 1, 0)) 353 last_day = update(last_day, (0, 0, -1)) 354 355 # Get weekdays in the week. 356 357 else: 358 current = context 359 values = [value for (value, index) in self.args["values"]] 360 361 while current < end and (counter is None or counter[0] < counter[1]): 362 next = update(current, step) 363 if date(*current).isoweekday() in values: 364 results += self.materialise_item(current, max(current, start), min(next, end), counter) 365 current = next 366 return results 367 368 # Find each of the given days. 369 370 for value, index in self.args["values"]: 371 if index is not None: 372 offset = timedelta(7 * (abs(index) - 1)) 373 374 if index < 0: 375 current = to_tuple(get_last_day(last_day, value) - offset, 3) 376 else: 377 current = to_tuple(get_first_day(first_day, value) + offset, 3) 378 379 if current < end: 380 next = update(current, step) 381 results += self.materialise_item(current, max(current, start), min(next, end), counter) 382 383 else: 384 if index < 0: 385 current = to_tuple(get_last_day(last_day, value), 3) 386 direction = operator.sub 387 else: 388 current = to_tuple(get_first_day(first_day, value), 3) 389 direction = operator.add 390 391 while first_day <= current <= last_day: 392 if current < end: 393 next = update(current, step) 394 results += self.materialise_item(current, max(current, start), min(next, end), counter) 395 current = to_tuple(direction(date(*current), timedelta(7)), 3) 396 397 return results 398 399 class Enum(Selector): 400 def materialise_items(self, context, start, end, counter): 401 step = scale(1, self.pos) 402 results = [] 403 for value in self.args["values"]: 404 current = combine(context, scale(value, self.pos)) 405 if current < end: 406 next = update(current, step) 407 results += self.materialise_item(current, max(current, start), min(next, end), counter) 408 return results 409 410 class MonthDayFilter(Enum): 411 def materialise_items(self, context, start, end, counter): 412 last_day = monthrange(context[0], context[1])[1] 413 step = scale(1, self.pos) 414 results = [] 415 for value in self.args["values"]: 416 if value < 0: 417 value = last_day + 1 + value 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 YearDayFilter(Enum): 425 def materialise_items(self, context, start, end, counter): 426 first_day = date(context[0], 1, 1) 427 next_first_day = date(context[0] + 1, 1, 1) 428 year_length = (next_first_day - first_day).days 429 step = scale(1, self.pos) 430 results = [] 431 for value in self.args["values"]: 432 if value < 0: 433 value = year_length + 1 + value 434 current = to_tuple(first_day + timedelta(value - 1), 3) 435 if current < end: 436 next = update(current, step) 437 results += self.materialise_item(current, max(current, start), min(next, end), counter) 438 return results 439 440 def process(selectors): 441 current = selectors[0] 442 for selector in selectors[1:]: 443 current.selecting = selector 444 current = selector 445 return selectors[0] 446 447 special_enum_levels = { 448 "BYDAY" : WeekDayFilter, 449 "BYMONTHDAY" : MonthDayFilter, 450 "BYYEARDAY" : YearDayFilter, 451 } 452 453 # vim: tabstop=4 expandtab shiftwidth=4