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 161 # Consume from both lists, merging entries. 162 163 while from_dt and from_q: 164 _pos = from_dt.pos 165 pos = from_q.pos 166 167 # Datetime value at wider resolution. 168 169 if _pos < pos: 170 context.append(from_dt.args["values"][0]) 171 from_dt = get_next(iter_dt) 172 173 # Qualifier at wider or same resolution as datetime value. 174 175 else: 176 if not have_q: 177 if isinstance(from_q, Enum) and pos > 0: 178 repeat = Pattern(pos - 1, {"interval" : 1}, "REPEAT") 179 repeat.context = tuple(context) 180 l.append(repeat) 181 else: 182 from_q.context = tuple(context) 183 have_q = True 184 185 # Either introduce the qualifier first. 186 187 if _pos > pos: 188 l.append(from_q) 189 190 # Or combine the qualifier and value details. 191 192 else: 193 context.append(from_dt.args["values"][0]) 194 l.append(combine_context_with_qualifier(context, from_q)) 195 from_dt = get_next(iter_dt) 196 197 from_q = get_next(iter_q) 198 199 # Complete the list. 200 201 while from_dt: 202 l.append(from_dt) 203 from_dt = get_next(iter_dt) 204 205 while from_q: 206 if not have_q: 207 if isinstance(from_q, Enum) and pos > 0: 208 repeat = Pattern(pos - 1, {"interval" : 1}, "REPEAT") 209 repeat.context = tuple(context) 210 l.append(repeat) 211 else: 212 from_q.context = tuple(context) 213 have_q = True 214 l.append(from_q) 215 from_q = get_next(iter_q) 216 217 return l 218 219 def combine_context_with_qualifier(context, from_q): 220 221 """ 222 Combine 'context' information (a datetime) and 'from_q' (a qualifier), 223 imposing the datetime value information on any qualifiers. 224 """ 225 226 if not from_q.args.has_key("values"): 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 (d + s).timetuple()[:len(t)] 280 281 # Classes for producing instances from recurrence structures. 282 283 class Selector: 284 def __init__(self, pos, args, qualifier, selecting=None): 285 self.pos = pos 286 self.args = args 287 self.qualifier = qualifier 288 self.context = () 289 self.selecting = selecting 290 291 def __repr__(self): 292 return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.pos, self.args, self.qualifier, self.context) 293 294 def materialise(self, start, end, count=None): 295 counter = count and [0, count] 296 return self.materialise_items(self.context, start, end, counter) 297 298 def materialise_item(self, current, last, next, counter): 299 if counter is None or counter[0] < counter[1]: 300 if self.selecting: 301 return self.selecting.materialise_items(current, last, next, counter) 302 elif last <= current: 303 if counter is not None: 304 counter[0] += 1 305 return [current] 306 return [] 307 308 class Pattern(Selector): 309 def materialise_items(self, context, start, end, counter): 310 first = scale(self.context[self.pos], self.pos) 311 312 # Define the step between items. 313 314 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 315 step = scale(interval, self.pos) 316 317 # Define the scale of a single item. 318 319 unit_interval = units.get(self.qualifier, 1) 320 unit_step = scale(unit_interval, self.pos) 321 322 current = combine(context, first) 323 results = [] 324 325 while current < end and (counter is None or counter[0] < counter[1]): 326 next = update(current, step) 327 current_end = update(current, unit_step) 328 results += self.materialise_item(current, max(current, start), min(current_end, end), counter) 329 current = next 330 331 return results 332 333 class WeekDayFilter(Selector): 334 def materialise_items(self, context, start, end, counter): 335 first = scale(bases[self.pos], self.pos) 336 337 # Define the step between items to be tested. 338 339 step = scale(1, self.pos) 340 341 current = combine(context, first) 342 results = [] 343 344 while current < end and (counter is None or counter[0] < counter[1]): 345 next = update(current, step) 346 results += self.materialise_item(current, max(current, start), min(next, end), counter) 347 current = next 348 349 return results 350 351 def materialise_item(self, current, last, next, counter): 352 values = self.args["values"] 353 354 # Select by day in week, also by occurrence in month. 355 356 for value, index in values: 357 if datetime(*current).isoweekday() == value: 358 last_day = monthrange(current[0], current[1])[1] 359 index_from_start = (current[2] - 1) / 7 360 index_from_end = -(1 + (last_day - current[2]) / 7) 361 if index is None or index in (index_from_start, index_from_end): 362 return Selector.materialise_item(self, current, last, next, counter) 363 364 return [] 365 366 class Enum(Selector): 367 def materialise_items(self, context, start, end, counter): 368 step = scale(1, self.pos) 369 results = [] 370 for value in self.args["values"]: 371 current = combine(context, scale(value, self.pos)) 372 if current < end and (counter is None or counter[0] < counter[1]): 373 next = update(current, step) 374 results += self.materialise_item(current, max(current, start), min(next, end), counter) 375 return results 376 377 class MonthDayFilter(Enum): 378 def materialise_items(self, context, start, end, counter): 379 last_day = monthrange(context[0], context[1])[1] 380 step = scale(1, self.pos) 381 results = [] 382 for value in self.args["values"]: 383 if value < 0: 384 value = last_day + 1 + value 385 current = combine(context, scale(value, self.pos)) 386 if current < end and (counter is None or counter[0] < counter[1]): 387 next = update(current, step) 388 results += self.materialise_item(current, max(current, start), min(next, end), counter) 389 return results 390 391 class YearDayFilter(Enum): 392 def materialise_items(self, context, start, end, counter): 393 first_day = date(context[0], 1, 1) 394 next_first_day = date(context[0] + 1, 1, 1) 395 year_length = (next_first_day - first_day).days 396 step = scale(1, self.pos) 397 results = [] 398 for value in self.args["values"]: 399 if value < 0: 400 value = year_length + 1 + value 401 current = (first_day + timedelta(value - 1)).timetuple()[:3] 402 if current < end and (counter is None or counter[0] < counter[1]): 403 next = update(current, step) 404 results += self.materialise_item(current, max(current, start), min(next, end), counter) 405 return results 406 407 def process(selectors): 408 current = selectors[0] 409 for selector in selectors[1:]: 410 current.selecting = selector 411 current = selector 412 return selectors[0] 413 414 special_enum_levels = { 415 "BYDAY" : WeekDayFilter, 416 "BYMONTHDAY" : MonthDayFilter, 417 "BYYEARDAY" : YearDayFilter, 418 } 419 420 # vim: tabstop=4 expandtab shiftwidth=4