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