imip-agent

vRecurrence.py

379:b5744872031a
2015-03-05 Paul Boddie Introduced some support for rescheduled/moved events where recurrences are obsoleted because the original event periods have changed, and where new additional or modified recurrences are received to replace them. recurring-events
     1 #!/usr/bin/env python     2      3 """     4 Recurrence rule calculation.     5      6 Copyright (C) 2014, 2015 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 weekdays = dict([(weekday, i+1) for (i, weekday) in enumerate(["MO", "TU", "WE", "TH", "FR", "SA", "SU"])])   100    101 # Functions for structuring the recurrences.   102    103 def get_next(it):   104     try:   105         return it.next()   106     except StopIteration:   107         return None   108    109 def get_parameters(values):   110    111     "Return parameters from the given list of 'values'."   112    113     d = {}   114     for value in values:   115         parts = value.split("=", 1)   116         if len(parts) < 2:   117             continue   118         key, value = parts   119         if key in ("COUNT", "BYSETPOS"):   120             d[key] = int(value)   121     return d   122    123 def get_qualifiers(values):   124    125     """   126     Process the list of 'values' of the form "key=value", returning a list of   127     qualifiers of the form (qualifier name, args).   128     """   129    130     qualifiers = []   131     frequency = None   132     interval = 1   133    134     for value in values:   135         parts = value.split("=", 1)   136         if len(parts) < 2:   137             continue   138         key, value = parts   139         if key == "FREQ" and freq.has_key(value):   140             qualifier = frequency = (value, {})   141         elif key == "INTERVAL":   142             interval = int(value)   143             continue   144         elif enum.has_key(key):   145             qualifier = (key, {"values" : get_qualifier_values(key, value)})   146         else:   147             continue   148    149         qualifiers.append(qualifier)   150    151     if frequency:   152         frequency[1]["interval"] = interval   153    154     return qualifiers   155    156 def get_qualifier_values(qualifier, value):   157    158     """   159     For the given 'qualifier', process the 'value' string, returning a list of   160     suitable values.   161     """   162    163     if qualifier != "BYDAY":   164         return map(int, value.split(","))   165    166     values = []   167     for part in value.split(","):   168         weekday = weekdays.get(part[-2:])   169         if not weekday:   170             continue   171         index = part[:-2]   172         if index:   173             index = int(index)   174         else:   175             index = None   176         values.append((weekday, index))   177    178     return values   179    180 def order_qualifiers(qualifiers):   181    182     "Return the 'qualifiers' in order of increasing resolution."   183    184     l = []   185    186     for qualifier, args in qualifiers:   187         if enum.has_key(qualifier):   188             level = enum[qualifier]   189             if special_enum_levels.has_key(qualifier):   190                 args["interval"] = 1   191                 selector = special_enum_levels[qualifier]   192             else:   193                 selector = Enum   194         else:   195             level = freq[qualifier]   196             selector = Pattern   197    198         l.append(selector(level, args, qualifier))   199    200     l.sort(key=lambda x: x.level)   201     return l   202    203 def get_datetime_structure(datetime):   204    205     "Return the structure of 'datetime' for recurrence production."   206    207     l = []   208     offset = 0   209     for level, value in enumerate(datetime):   210         if level == 2:   211             offset = 3   212         l.append(Enum(level + offset, {"values" : [value]}, "DT"))   213     return l   214    215 def combine_datetime_with_qualifiers(datetime, qualifiers):   216    217     """   218     Combine 'datetime' with 'qualifiers' to produce a structure for recurrence   219     production.   220     """   221    222     iter_dt = iter(get_datetime_structure(datetime))   223     iter_q = iter(order_qualifiers(qualifiers))   224    225     l = []   226    227     from_dt = get_next(iter_dt)   228     from_q = get_next(iter_q)   229    230     have_q = False   231     context = []   232     context.append(from_dt.args["values"][0])   233    234     # Consume from both lists, merging entries.   235    236     while from_dt and from_q:   237         _level = from_dt.level   238         level = from_q.level   239    240         # Datetime value at wider resolution.   241    242         if _level < level:   243             from_dt = get_next(iter_dt)   244             context.append(from_dt.args["values"][0])   245    246         # Qualifier at wider or same resolution as datetime value.   247    248         else:   249             if not have_q:   250                 if isinstance(from_q, Enum) and level > 0:   251                     repeat = Pattern(level - 1, {"interval" : 1}, None)   252                     repeat.context = tuple(context)   253                     l.append(repeat)   254                 have_q = True   255    256             from_q.context = tuple(context)   257             l.append(from_q)   258             from_q = get_next(iter_q)   259    260             if _level == level:   261                 from_dt = get_next(iter_dt)   262                 context.append(from_dt.args["values"][0])   263    264     # Complete the list.   265    266     while from_dt:   267         l.append(from_dt)   268         from_dt = get_next(iter_dt)   269    270     while from_q:   271         if not have_q:   272             if isinstance(from_q, Enum) and level > 0:   273                 repeat = Pattern(level - 1, {"interval" : 1}, None)   274                 repeat.context = tuple(context)   275                 l.append(repeat)   276             have_q = True   277    278         from_q.context = tuple(context)   279         l.append(from_q)   280         from_q = get_next(iter_q)   281    282     return l   283    284 # Datetime arithmetic.   285    286 def combine(t1, t2):   287    288     """   289     Combine tuples 't1' and 't2', returning a copy of 't1' filled with values   290     from 't2' in positions where 0 appeared in 't1'.   291     """   292    293     return tuple(map(lambda x, y: x or y, t1, t2))   294    295 def scale(interval, pos):   296    297     """   298     Scale the given 'interval' value to the indicated position 'pos', returning   299     a tuple with leading zero elements and 'interval' at the stated position.   300     """   301    302     return (0,) * pos + (interval,)   303    304 def get_seconds(t):   305    306     "Convert the sub-day part of 't' into seconds."   307    308     t = t + (0,) * (6 - len(t))   309     return (t[3] * 60 + t[4]) * 60 + t[5]   310    311 def update(t, step):   312    313     "Update 't' by 'step' at the resolution of 'step'."   314    315     i = len(step)   316    317     # Years only.   318    319     if i == 1:   320         return (t[0] + step[0],) + tuple(t[1:])   321    322     # Years and months.   323    324     elif i == 2:   325         month = t[1] + step[1]   326         return (t[0] + step[0] + (month - 1) / 12, (month - 1) % 12 + 1) + tuple(t[2:])   327    328     # Dates and datetimes.   329    330     else:   331         updated_for_months = update(t, step[:2])   332    333         # Dates only.   334    335         if i == 3:   336             d = datetime(*updated_for_months)   337             s = timedelta(step[2])   338    339         # Datetimes.   340    341         else:   342             d = datetime(*updated_for_months)   343             s = timedelta(step[2], get_seconds(step))   344    345         return to_tuple(d + s, len(t))   346    347 def to_tuple(d, n=None):   348    349     "Return 'd' as a tuple, optionally trimming the result to 'n' positions."   350    351     if not isinstance(d, date):   352         return d   353     if n is None:   354         if isinstance(d, datetime):   355             n = 6   356         else:   357             n = 3   358     return d.timetuple()[:n]   359    360 def get_first_day(first_day, weekday):   361    362     "Return the first occurrence at or after 'first_day' of 'weekday'."   363    364     first_day = date(*first_day)   365     first_weekday = first_day.isoweekday()   366     if first_weekday > weekday:   367         return first_day + timedelta(7 - first_weekday + weekday)   368     else:   369         return first_day + timedelta(weekday - first_weekday)   370    371 def get_last_day(last_day, weekday):   372    373     "Return the last occurrence at or before 'last_day' of 'weekday'."   374    375     last_day = date(*last_day)   376     last_weekday = last_day.isoweekday()   377     if last_weekday < weekday:   378         return last_day - timedelta(last_weekday + 7 - weekday)   379     else:   380         return last_day - timedelta(last_weekday - weekday)   381    382 # Classes for producing instances from recurrence structures.   383    384 class Selector:   385    386     "A generic selector."   387    388     def __init__(self, level, args, qualifier, selecting=None):   389    390         """   391         Initialise at the given 'level' a selector employing the given 'args'   392         defined in the interpretation of recurrence rule qualifiers, with the   393         'qualifier' being the name of the rule qualifier, and 'selecting' being   394         an optional selector used to find more specific instances from those   395         found by this selector.   396         """   397    398         self.level = level   399         self.pos = positions[level]   400         self.args = args   401         self.qualifier = qualifier   402         self.context = ()   403         self.selecting = selecting   404    405     def __repr__(self):   406         return "%s(%r, %r, %r, %r)" % (self.__class__.__name__, self.level, self.args, self.qualifier, self.context)   407    408     def materialise(self, start, end, count=None, setpos=None, inclusive=False):   409    410         """   411         Starting at 'start', materialise instances up to but not including any   412         at 'end' or later, returning at most 'count' if specified, and returning   413         only the occurrences indicated by 'setpos' if specified. A list of   414         instances is returned.   415    416         If 'inclusive' is specified, the selection of instances will include the   417         end of the search period if present in the results.   418         """   419    420         start = to_tuple(start)   421         end = to_tuple(end)   422         counter = count and [0, count]   423         results = self.materialise_items(self.context, start, end, counter, setpos, inclusive)   424         results.sort()   425         return results[:count]   426    427     def materialise_item(self, current, earliest, next, counter, setpos=None, inclusive=False):   428    429         """   430         Given the 'current' instance, the 'earliest' acceptable instance, the   431         'next' instance, an instance 'counter', and the optional 'setpos'   432         criteria, return a list of result items. Where no selection within the   433         current instance occurs, the current instance will be returned as a   434         result if the same or later than the earliest acceptable instance.   435         """   436    437         if self.selecting:   438             return self.selecting.materialise_items(current, earliest, next, counter, setpos, inclusive)   439         elif earliest <= current:   440             return [current]   441         else:   442             return []   443    444     def convert_positions(self, setpos):   445    446         "Convert 'setpos' to 0-based indexes."   447    448         l = []   449         for pos in setpos:   450             lower = pos < 0 and pos or pos - 1   451             upper = pos > 0 and pos or pos < -1 and pos + 1 or None   452             l.append((lower, upper))   453         return l   454    455     def select_positions(self, results, setpos):   456    457         "Select in 'results' the 1-based positions given by 'setpos'."   458    459         results.sort()   460         l = []   461         for lower, upper in self.convert_positions(setpos):   462             l += results[lower:upper]   463         return l   464    465     def filter_by_period(self, results, start, end, inclusive):   466    467         """   468         Filter 'results' so that only those at or after 'start' and before 'end'   469         are returned.   470    471         If 'inclusive' is specified, the selection of instances will include the   472         end of the search period if present in the results.   473         """   474    475         l = []   476         for result in results:   477             if start <= result and (inclusive and result <= end or result < end):   478                 l.append(result)   479         return l   480    481 class Pattern(Selector):   482    483     "A selector of instances according to a repeating pattern."   484    485     def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False):   486         first = scale(self.context[self.pos], self.pos)   487    488         # Define the step between items.   489    490         interval = self.args.get("interval", 1) * units.get(self.qualifier, 1)   491         step = scale(interval, self.pos)   492    493         # Define the scale of a single item.   494    495         unit_interval = units.get(self.qualifier, 1)   496         unit_step = scale(unit_interval, self.pos)   497    498         current = combine(context, first)   499         results = []   500    501         while (inclusive and current <= end or current < end) and (counter is None or counter[0] < counter[1]):   502             next = update(current, step)   503             current_end = update(current, unit_step)   504             interval_results = self.materialise_item(current, max(current, start), min(current_end, end), counter, setpos, inclusive)   505             if counter is not None:   506                 counter[0] += len(interval_results)   507             results += interval_results   508             current = next   509    510         return results   511    512 class WeekDayFilter(Selector):   513    514     "A selector of instances specified in terms of day numbers."   515    516     def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False):   517         step = scale(1, 2)   518         results = []   519    520         # Get weekdays in the year.   521    522         if len(context) == 1:   523             first_day = (context[0], 1, 1)   524             last_day = (context[0], 12, 31)   525    526         # Get weekdays in the month.   527    528         elif len(context) == 2:   529             first_day = (context[0], context[1], 1)   530             last_day = update((context[0], context[1], 1), (0, 1, 0))   531             last_day = update(last_day, (0, 0, -1))   532    533         # Get weekdays in the week.   534    535         else:   536             current = context   537             values = [value for (value, index) in self.args["values"]]   538    539             while (inclusive and current <= end or current < end):   540                 next = update(current, step)   541                 if date(*current).isoweekday() in values:   542                     results += self.materialise_item(current, max(current, start), min(next, end), counter, inclusive=inclusive)   543                 current = next   544    545             if setpos:   546                 return self.select_positions(results, setpos)   547             else:   548                 return results   549    550         # Find each of the given days.   551    552         for value, index in self.args["values"]:   553             if index is not None:   554                 offset = timedelta(7 * (abs(index) - 1))   555    556                 if index < 0:   557                     current = to_tuple(get_last_day(last_day, value) - offset, 3)   558                 else:   559                     current = to_tuple(get_first_day(first_day, value) + offset, 3)   560    561                 next = update(current, step)   562    563                 # To support setpos, only current and next bound the search, not   564                 # the period in addition.   565    566                 results += self.materialise_item(current, current, next, counter, inclusive=inclusive)   567    568             else:   569                 if index < 0:   570                     current = to_tuple(get_last_day(last_day, value), 3)   571                     direction = operator.sub   572                 else:   573                     current = to_tuple(get_first_day(first_day, value), 3)   574                     direction = operator.add   575    576                 while first_day <= current <= last_day:   577                     next = update(current, step)   578    579                     # To support setpos, only current and next bound the search, not   580                     # the period in addition.   581    582                     results += self.materialise_item(current, current, next, counter, inclusive=inclusive)   583                     current = to_tuple(direction(date(*current), timedelta(7)), 3)   584    585         # Extract selected positions and remove out-of-period instances.   586    587         if setpos:   588             results = self.select_positions(results, setpos)   589    590         return self.filter_by_period(results, start, end, inclusive)   591    592 class Enum(Selector):   593     def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False):   594         step = scale(1, self.pos)   595         results = []   596         for value in self.args["values"]:   597             current = combine(context, scale(value, self.pos))   598             next = update(current, step)   599    600             # To support setpos, only current and next bound the search, not   601             # the period in addition.   602    603             results += self.materialise_item(current, current, next, counter, setpos, inclusive)   604    605         # Extract selected positions and remove out-of-period instances.   606    607         if setpos:   608             results = self.select_positions(results, setpos)   609    610         return self.filter_by_period(results, start, end, inclusive)   611    612 class MonthDayFilter(Enum):   613     def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False):   614         last_day = monthrange(context[0], context[1])[1]   615         step = scale(1, self.pos)   616         results = []   617         for value in self.args["values"]:   618             if value < 0:   619                 value = last_day + 1 + value   620             current = combine(context, scale(value, self.pos))   621             next = update(current, step)   622    623             # To support setpos, only current and next bound the search, not   624             # the period in addition.   625    626             results += self.materialise_item(current, current, next, counter, inclusive=inclusive)   627    628         # Extract selected positions and remove out-of-period instances.   629    630         if setpos:   631             results = self.select_positions(results, setpos)   632    633         return self.filter_by_period(results, start, end, inclusive)   634    635 class YearDayFilter(Enum):   636     def materialise_items(self, context, start, end, counter, setpos=None, inclusive=False):   637         first_day = date(context[0], 1, 1)   638         next_first_day = date(context[0] + 1, 1, 1)   639         year_length = (next_first_day - first_day).days   640         step = scale(1, self.pos)   641         results = []   642         for value in self.args["values"]:   643             if value < 0:   644                 value = year_length + 1 + value   645             current = to_tuple(first_day + timedelta(value - 1), 3)   646             next = update(current, step)   647    648             # To support setpos, only current and next bound the search, not   649             # the period in addition.   650    651             results += self.materialise_item(current, current, next, counter, inclusive=inclusive)   652    653         # Extract selected positions and remove out-of-period instances.   654    655         if setpos:   656             results = self.select_positions(results, setpos)   657    658         return self.filter_by_period(results, start, end, inclusive)   659    660 special_enum_levels = {   661     "BYDAY" : WeekDayFilter,   662     "BYMONTHDAY" : MonthDayFilter,   663     "BYYEARDAY" : YearDayFilter,   664     }   665    666 # Public functions.   667    668 def connect_selectors(selectors):   669    670     """   671     Make the 'selectors' reference each other in a hierarchy so that   672     materialising the principal selector causes the more specific ones to be   673     employed in the operation.   674     """   675    676     current = selectors[0]   677     for selector in selectors[1:]:   678         current.selecting = selector   679         current = selector   680     return selectors[0]   681    682 def get_selector(dt, qualifiers):   683    684     """   685     Combine the initial datetime 'dt' with the given 'qualifiers', returning an   686     object that can be used to select recurrences described by the 'qualifiers'.   687     """   688    689     dt = to_tuple(dt)   690     return connect_selectors(combine_datetime_with_qualifiers(dt, qualifiers))   691    692 def get_rule(dt, rule):   693    694     """   695     Using the given initial datetime 'dt', interpret the 'rule' (a semicolon-   696     separated collection of "key=value" strings), and return the resulting   697     selector object.   698     """   699    700     if not isinstance(rule, tuple):   701         rule = rule.split(";")   702     qualifiers = get_qualifiers(rule)   703     return get_selector(dt, qualifiers)   704    705 # vim: tabstop=4 expandtab shiftwidth=4