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 special_enum_levels = ("BYDAY", "BYMONTHDAY", "BYYEARDAY") 82 83 # Map from levels to lengths of datetime tuples. 84 85 lengths = [6, 5, 4, 3, 3, 2, 1] 86 positions = [l-1 for l in lengths] 87 88 # Map from qualifiers to interval units. Here, weeks are defined as 7 days. 89 90 units = {"WEEKLY" : 7} 91 92 # Map from tuple positions to base values at each resolution. 93 94 bases = [0, 1, 1, 0, 0, 0] 95 96 def basevalue(resolution): 97 return bases[positions[resolution]] 98 99 # Make dictionaries mapping qualifiers to levels. 100 101 freq = dict([(level, i) for (i, level) in enumerate(freq_levels)]) 102 enum = dict([(level, i) for (i, levels) in enumerate(enum_levels) for level in levels]) 103 104 # Functions for structuring the recurrences. 105 106 def get_next(it): 107 try: 108 return it.next() 109 except StopIteration: 110 return None 111 112 def order_qualifiers(qualifiers): 113 114 "Return the 'qualifiers' in order of increasing resolution." 115 116 l = [] 117 118 for qualifier, args in qualifiers: 119 if enum.has_key(qualifier): 120 level = enum[qualifier] 121 if qualifier in special_enum_levels: 122 args["interval"] = 1 123 selector = PatternFilter 124 else: 125 selector = Enum 126 else: 127 level = freq[qualifier] 128 selector = Pattern 129 130 pos = positions[level] 131 l.append(selector(pos, args, qualifier)) 132 133 l.sort(key=lambda x: x.pos) 134 return l 135 136 def get_datetime_structure(datetime): 137 138 "Return the structure of 'datetime' for recurrence production." 139 140 l = [] 141 for pos, value in enumerate(datetime): 142 l.append(Enum(pos, {"values" : [value]}, "DT")) 143 return l 144 145 def combine_datetime_with_qualifiers(datetime, qualifiers): 146 147 """ 148 Combine 'datetime' with 'qualifiers' to produce a structure for recurrence 149 production. 150 """ 151 152 iter_dt = iter(get_datetime_structure(datetime)) 153 iter_q = iter(order_qualifiers(qualifiers)) 154 155 l = [] 156 157 from_dt = get_next(iter_dt) 158 from_q = get_next(iter_q) 159 160 have_q = False 161 context = [] 162 163 # Consume from both lists, merging entries. 164 165 while from_dt and from_q: 166 _pos = from_dt.pos 167 pos = from_q.pos 168 169 # Datetime value at wider resolution. 170 171 if _pos < pos: 172 if have_q: 173 l.append(from_dt) 174 else: 175 context.append(from_dt.args["values"][0]) 176 from_dt = get_next(iter_dt) 177 178 # Qualifier at wider or same resolution as datetime value. 179 180 else: 181 if not have_q: 182 if isinstance(from_q, Enum) and pos > 0: 183 repeat = Pattern(pos - 1, {"interval" : 1, "values" : [context[-1]]}, "REPEAT") 184 repeat.context = tuple(context[:-1]) 185 l.append(repeat) 186 else: 187 from_q.context = tuple(context) 188 have_q = True 189 190 # Either introduce the qualifier first. 191 192 if _pos > pos: 193 l.append(from_q) 194 195 # Or combine the qualifier and value details. 196 197 else: 198 l.append(combine_value_with_qualifier(from_dt, from_q)) 199 from_dt = get_next(iter_dt) 200 201 from_q = get_next(iter_q) 202 203 # Complete the list. 204 205 while from_dt: 206 l.append(from_dt) 207 from_dt = get_next(iter_dt) 208 209 while from_q: 210 if not have_q: 211 if isinstance(from_q, Enum) and pos > 0: 212 repeat = Pattern(pos - 1, {"interval" : 1, "values" : [context[-1]]}, "REPEAT") 213 repeat.context = tuple(context[:-1]) 214 l.append(repeat) 215 else: 216 from_q.context = tuple(context) 217 have_q = True 218 l.append(from_q) 219 from_q = get_next(iter_q) 220 221 return l 222 223 def combine_value_with_qualifier(from_dt, from_q): 224 225 """ 226 Combine value information supplied by 'from_dt' (a datetime) and 'from_q' 227 (a qualifier), imposing the datetime value information on any qualifiers. 228 """ 229 230 if not from_q.args.has_key("values") and from_dt.args.has_key("values"): 231 from_q.args["values"] = from_dt.args["values"] 232 return from_q 233 234 # Datetime arithmetic. 235 236 def combine(t1, t2): 237 return tuple(map(lambda x, y: x or y, t1, t2)) 238 239 def scale(interval, pos): 240 return (0,) * pos + (interval,) 241 242 def get_seconds(t): 243 244 "Convert the sub-day part of 't' into seconds." 245 246 t = t + (0,) * (6 - len(t)) 247 return (t[3] * 60 + t[4]) * 60 + t[5] 248 249 def update(t, step): 250 251 "Update 't' by 'step' at the resolution of 'step'." 252 253 i = len(step) 254 255 # Years only. 256 257 if i == 1: 258 return (t[0] + step[0],) + tuple(t[1:]) 259 260 # Years and months. 261 262 elif i == 2: 263 month = t[1] + step[1] 264 return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:]) 265 266 # Dates and datetimes. 267 268 else: 269 updated_for_months = update(t, step[:2]) 270 271 # Dates only. 272 273 if i == 3: 274 d = datetime(*updated_for_months) 275 s = timedelta(step[2]) 276 277 # Datetimes. 278 279 else: 280 d = datetime(*updated_for_months) 281 s = timedelta(step[2], get_seconds(step)) 282 283 return (d + s).timetuple()[:len(t)] 284 285 # Classes for producing instances from recurrence structures. 286 287 class Selector: 288 def __init__(self, pos, args, qualifier, selecting=None): 289 self.pos = pos 290 self.args = args 291 self.qualifier = qualifier 292 self.context = () 293 self.selecting = selecting 294 295 def __repr__(self): 296 return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.pos, self.args, self.qualifier, self.context) 297 298 def materialise(self, end, count=None): 299 counter = count and [0, count] 300 return self.materialise_items(self.context, end, counter) 301 302 def materialise_item(self, current, next, counter): 303 if counter is None or counter[0] < counter[1]: 304 if self.selecting: 305 return self.selecting.materialise_items(current, next, counter) 306 else: 307 if counter is not None: 308 counter[0] += 1 309 return [current] 310 else: 311 return [] 312 313 class Pattern(Selector): 314 def materialise_items(self, context, end, counter): 315 first = scale(self.args["values"][0], self.pos) 316 317 # Define the step between items. 318 319 interval = self.args.get("interval", 1) * units.get(self.qualifier, 1) 320 step = scale(interval, self.pos) 321 322 # Define the scale of a single item. 323 324 unit_interval = units.get(self.qualifier, 1) 325 unit_step = scale(unit_interval, self.pos) 326 327 current = combine(context, first) 328 results = [] 329 330 while current < end and (counter is None or counter[0] < counter[1]): 331 next = update(current, step) 332 current_end = update(current, unit_step) 333 results += self.materialise_item(current, min(current_end, end), counter) 334 current = next 335 336 return results 337 338 class PatternFilter(Selector): 339 def materialise_items(self, context, end, counter): 340 first = scale(bases[self.pos], self.pos) 341 342 # Define the step between items to be tested. 343 344 step = scale(1, self.pos) 345 346 current = combine(context, first) 347 results = [] 348 349 while current < end and (counter is None or counter[0] < counter[1]): 350 next = update(current, step) 351 results += self.materialise_item(current, min(next, end), counter) 352 current = next 353 354 return results 355 356 def materialise_item(self, current, next, counter): 357 values = self.args["values"] 358 359 # Select by day in week, also by occurrence in month. 360 361 if self.qualifier == "BYDAY": 362 for value, index in values: 363 if datetime(*current).isoweekday() == value: 364 last_day = monthrange(current[0], current[1])[1] 365 index_from_start = (current[2] - 1) / 7 366 index_from_end = -(1 + (last_day - current[2]) / 7) 367 if index is None or index in (index_from_start, index_from_end): 368 return Selector.materialise_item(self, current, next, counter) 369 370 return [] 371 372 class Enum(Selector): 373 def materialise_items(self, context, end, counter): 374 step = scale(1, self.pos) 375 results = [] 376 for value in self.args["values"]: 377 current = combine(context, scale(value, self.pos)) 378 if current < end and (counter is None or counter[0] < counter[1]): 379 next = update(current, step) 380 results += self.materialise_item(current, min(next, end), counter) 381 return results 382 383 def process(selectors): 384 current = selectors[0] 385 for selector in selectors[1:]: 386 current.selecting = selector 387 current = selector 388 return selectors[0] 389 390 # vim: tabstop=4 expandtab shiftwidth=4