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 if have_q: 171 l.append(from_dt) 172 else: 173 context.append(from_dt.args["values"][0]) 174 from_dt = get_next(iter_dt) 175 176 # Qualifier at wider or same resolution as datetime value. 177 178 else: 179 if not have_q: 180 if isinstance(from_q, Enum) and pos > 0: 181 repeat = Pattern(pos - 1, {"interval" : 1, "values" : [context[-1]]}, "REPEAT") 182 repeat.context = tuple(context[:-1]) 183 l.append(repeat) 184 else: 185 from_q.context = tuple(context) 186 have_q = True 187 188 # Either introduce the qualifier first. 189 190 if _pos > pos: 191 l.append(from_q) 192 193 # Or combine the qualifier and value details. 194 195 else: 196 l.append(combine_value_with_qualifier(from_dt, from_q)) 197 from_dt = get_next(iter_dt) 198 199 from_q = get_next(iter_q) 200 201 # Complete the list. 202 203 while from_dt: 204 l.append(from_dt) 205 from_dt = get_next(iter_dt) 206 207 while from_q: 208 if not have_q: 209 if isinstance(from_q, Enum) and pos > 0: 210 repeat = Pattern(pos - 1, {"interval" : 1, "values" : [context[-1]]}, "REPEAT") 211 repeat.context = tuple(context[:-1]) 212 l.append(repeat) 213 else: 214 from_q.context = tuple(context) 215 have_q = True 216 l.append(from_q) 217 from_q = get_next(iter_q) 218 219 return l 220 221 def combine_value_with_qualifier(from_dt, from_q): 222 223 """ 224 Combine value information supplied by 'from_dt' (a datetime) and 'from_q' 225 (a qualifier), imposing the datetime value information on any qualifiers. 226 """ 227 228 if not from_q.args.has_key("values") and from_dt.args.has_key("values"): 229 from_q.args["values"] = from_dt.args["values"] 230 return from_q 231 232 # Datetime arithmetic. 233 234 def combine(t1, t2): 235 return tuple(map(lambda x, y: x or y, t1, t2)) 236 237 def scale(interval, pos): 238 return (0,) * pos + (interval,) 239 240 def get_seconds(t): 241 242 "Convert the sub-day part of 't' into seconds." 243 244 t = t + (0,) * (6 - len(t)) 245 return (t[3] * 60 + t[4]) * 60 + t[5] 246 247 def update(t, step): 248 249 "Update 't' by 'step' at the resolution of 'step'." 250 251 i = len(step) 252 253 # Years only. 254 255 if i == 1: 256 return (t[0] + step[0],) + tuple(t[1:]) 257 258 # Years and months. 259 260 elif i == 2: 261 month = t[1] + step[1] 262 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 263 264 # Dates and datetimes. 265 266 else: 267 updated_for_months = update(t, step[:2]) 268 269 # Dates only. 270 271 if i == 3: 272 d = datetime(*updated_for_months) 273 s = timedelta(step[2]) 274 275 # Datetimes. 276 277 else: 278 d = datetime(*updated_for_months) 279 s = timedelta(step[2], get_seconds(step)) 280 281 return (d + s).timetuple()[:len(t)] 282 283 # Classes for producing instances from recurrence structures. 284 285 class Selector: 286 def __init__(self, pos, args, qualifier, selecting=None): 287 self.pos = pos 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.pos, self.args, self.qualifier, self.context) 295 296 def materialise(self, start, end, count=None): 297 counter = count and [0, count] 298 return self.materialise_items(self.context, start, end, counter) 299 300 def materialise_item(self, current, last, next, counter): 301 if counter is None or counter[0] < counter[1]: 302 if self.selecting: 303 return self.selecting.materialise_items(current, last, next, counter) 304 elif last <= current: 305 if counter is not None: 306 counter[0] += 1 307 return [current] 308 return [] 309 310 class Pattern(Selector): 311 def materialise_items(self, context, start, end, counter): 312 first = scale(self.args["values"][0], self.pos) 313 314 # Define the step between items. 315 316 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 317 step = scale(interval, self.pos) 318 319 # Define the scale of a single item. 320 321 unit_interval = units.get(self.qualifier, 1) 322 unit_step = scale(unit_interval, self.pos) 323 324 current = combine(context, first) 325 results = [] 326 327 while current < end and (counter is None or counter[0] < counter[1]): 328 next = update(current, step) 329 current_end = update(current, unit_step) 330 results += self.materialise_item(current, max(current, start), min(current_end, end), counter) 331 current = next 332 333 return results 334 335 class WeekDayFilter(Selector): 336 def materialise_items(self, context, start, end, counter): 337 first = scale(bases[self.pos], self.pos) 338 339 # Define the step between items to be tested. 340 341 step = scale(1, 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 results += self.materialise_item(current, max(current, start), min(next, end), counter) 349 current = next 350 351 return results 352 353 def materialise_item(self, current, last, next, counter): 354 values = self.args["values"] 355 356 # Select by day in week, also by occurrence in month. 357 358 for value, index in values: 359 if datetime(*current).isoweekday() == value: 360 last_day = monthrange(current[0], current[1])[1] 361 index_from_start = (current[2] - 1) / 7 362 index_from_end = -(1 + (last_day - current[2]) / 7) 363 if index is None or index in (index_from_start, index_from_end): 364 return Selector.materialise_item(self, current, last, next, counter) 365 366 return [] 367 368 class Enum(Selector): 369 def materialise_items(self, context, start, end, counter): 370 step = scale(1, self.pos) 371 results = [] 372 for value in self.args["values"]: 373 current = combine(context, scale(value, self.pos)) 374 if current < end and (counter is None or counter[0] < counter[1]): 375 next = update(current, step) 376 results += self.materialise_item(current, max(current, start), min(next, end), counter) 377 return results 378 379 class MonthDayFilter(Enum): 380 def materialise_items(self, context, start, end, counter): 381 last_day = monthrange(context[0], context[1])[1] 382 step = scale(1, self.pos) 383 results = [] 384 for value in self.args["values"]: 385 if value < 0: 386 value = last_day + 1 + value 387 current = combine(context, scale(value, self.pos)) 388 if current < end and (counter is None or counter[0] < counter[1]): 389 next = update(current, step) 390 results += self.materialise_item(current, max(current, start), min(next, end), counter) 391 return results 392 393 class YearDayFilter(Enum): 394 def materialise_items(self, context, start, end, counter): 395 first_day = date(context[0], 1, 1) 396 next_first_day = date(context[0] + 1, 1, 1) 397 year_length = (next_first_day - first_day).days 398 step = scale(1, self.pos) 399 results = [] 400 for value in self.args["values"]: 401 if value < 0: 402 value = year_length + 1 + value 403 current = (first_day + timedelta(value - 1)).timetuple()[:3] 404 if current < end and (counter is None or counter[0] < counter[1]): 405 next = update(current, step) 406 results += self.materialise_item(current, max(current, start), min(next, end), counter) 407 return results 408 409 def process(selectors): 410 current = selectors[0] 411 for selector in selectors[1:]: 412 current.selecting = selector 413 current = selector 414 return selectors[0] 415 416 special_enum_levels = { 417 "BYDAY" : WeekDayFilter, 418 "BYMONTHDAY" : MonthDayFilter, 419 "BYYEARDAY" : YearDayFilter, 420 } 421 422 # vim: tabstop=4 expandtab shiftwidth=4