1 /* -*- Mode: C -*-
2 ======================================================================
3 FILE: icalrecur.c
4 CREATOR: eric 16 May 2000
5
6 $Id: icalrecur.c,v 1.71 2008-02-03 16:10:46 dothebart Exp $
7 $Locker: $
8
9
10 (C) COPYRIGHT 2000, Eric Busboom <eric@softwarestudio.org>
11 http://www.softwarestudio.org
12
13 This program is free software; you can redistribute it and/or modify
14 it under the terms of either:
15
16 The LGPL as published by the Free Software Foundation, version
17 2.1, available at: http://www.fsf.org/copyleft/lesser.html
18
19 Or:
20
21 The Mozilla Public License Version 1.0. You may obtain a copy of
22 the License at http://www.mozilla.org/MPL/
23 */
24
25 /**
26 @file icalrecur.c
27 @brief Implementation of routines for dealing with recurring time
28
29 How this code works:
30
31 Processing starts when the caller generates a new recurrence
32 iterator via icalrecur_iterator_new(). This routine copies the
33 recurrence rule into the iterator and extracts things like start and
34 end dates. Then, it checks if the rule is legal, using some logic
35 from RFC2445 and some logic that probably should be in RFC2445.
36
37 Then, icalrecur_iterator_new() re-writes some of the BY*
38 arrays. This involves ( via a call to setup_defaults() ) :
39
40 1) For BY rule parts with no data ( ie BYSECOND was not specified )
41 copy the corresponding time part from DTSTART into the BY array. (
42 So impl->by_ptrs[BY_SECOND] will then have one element if is
43 originally had none ) This only happens if the BY* rule part data
44 would expand the number of occurrences in the occurrence set. This
45 lets the code ignore DTSTART later on and still use it to get the
46 time parts that were not specified in any other way.
47
48 2) For the by rule part that are not the same interval as the
49 frequency -- for HOURLY anything but BYHOUR, for instance -- copy the
50 first data element from the rule part into the first occurrence. For
51 example, for "INTERVAL=MONTHLY and BYHOUR=10,30", initialize the
52 first time to be returned to have an hour of 10.
53
54 Finally, for INTERVAL=YEARLY, the routine expands the rule to get
55 all of the days specified in the rule. The code will do this for
56 each new year, and this is the first expansion. This is a special
57 case for the yearly interval; no other frequency gets expanded this
58 way. The yearly interval is the most complex, so some special
59 processing is required.
60
61 After creating a new iterator, the caller will make successive calls
62 to icalrecur_iterator_next() to get the next time specified by the
63 rule. The main part of this routine is a switch on the frequency of
64 the rule. Each different frequency is handled by a different
65 routine.
66
67 For example, next_hour handles the case of INTERVAL=HOURLY, and it
68 is called by other routines to get the next hour. First, the routine
69 tries to get the next minute part of a time with a call to
70 next_minute(). If next_minute() returns 1, it has reached the end of
71 its data, usually the last element of the BYMINUTE array. Then, if
72 there is data in the BYHOUR array, the routine changes the hour to
73 the next one in the array. If INTERVAL=HOURLY, the routine advances
74 the hour by the interval.
75
76 If the routine used the last hour in the BYHOUR array, and the
77 INTERVAL=HOURLY, then the routine calls increment_monthday() to set
78 the next month day. The increment_* routines may call higher routine
79 to increment the month or year also.
80
81 The code for INTERVAL=DAILY is handled by next_day(). First, the
82 routine tries to get the next hour part of a time with a call to
83 next_hour. If next_hour() returns 1, it has reached the end of its
84 data, usually the last element of the BYHOUR array. This means that
85 next_day() should increment the time to the next day. If FREQUENCY==DAILY,
86 the routine increments the day by the interval; otherwise, it
87 increments the day by 1.
88
89 Next_day() differs from next_hour because it does not use the BYDAY
90 array to select an appropriate day. Instead, it returns every day (
91 incrementing by 1 if the frequency is not DAILY with INTERVAL!=1)
92 Any days that are not specified in an non-empty BYDAY array are
93 filtered out later.
94
95 Generally, the flow of these routine is for a next_* call a next_*
96 routine of a lower interval ( next_day calls next_hour) and then to
97 possibly call an increment_* routine of an equal or higher
98 interval. ( next_day calls increment_monthday() )
99
100 When the call to the original next_* routine returns,
101 icalrecur_iterator_next() will check the returned data against other
102 BYrule parts to determine if is should be excluded by calling
103 check_contracting_rules. Generally, a contracting rule is any with a
104 larger time span than the interval. For instance, if
105 INTERVAL=DAILY, BYMONTH is a contracting rule part.
106
107 Check_contracting_rules() uses icalrecur_check_rulepart() to do its
108 work. icalrecur_check_rulepart() uses expand_map[] to determine if a rule
109 is contracting, and if it is, and if the BY rule part has some data,
110 then the routine checks if the value of a component of the time is
111 part of the byrule part. For instance, for "INTERVAL=DAILY;
112 BYMONTH=6,10", icalrecur_check_rulepart() would check that the time value
113 given to it has a month of either 6 or 10.
114
115 Finally, icalrecur_iterator_next() does a few other checks on the
116 time value, and if it passes, it returns the time.
117
118 A note about the end_of_data flag. The flag indicates that the
119 routine is at the end of its data -- the last BY rule if the routine
120 is using by rules, or the last day of the week/month/year/etc if
121 not.
122
123 This flag is usually set early in a next_* routine and returned in
124 the end. The way it is used allows the next_* routine to set the
125 last time back to the first element in a BYxx rule, and then signal
126 to the higer level routine to increment the next higher level. For
127 instance. WITH FREQ=MONTHLY;BYDAY=TU,FR, After next_weekday_by_month
128 runs though both TU and FR, it sets the week day back to TU and sets
129 end_of_data to 1x. This signals next_month to increment the month.
130
131
132 ======================================================================*/
133
134 #ifdef HAVE_CONFIG_H
135 #include "config.h"
136 #endif
137
138 #ifdef HAVE_STDINT_H
139 #include <stdint.h>
140 #endif
141
142 #ifdef WIN32
143 #if defined(_MSC_VER) && (_MSC_VER < 1900)
144 #define snprintf _snprintf
145 #endif
146 #endif
147
148
149 #include <limits.h>
150
151 #ifndef HAVE_INTPTR_T
152 #if (defined (_MSC_VER) && _MSC_VER < 1400) || defined (XP_BEOS)
153 typedef long intptr_t;
154 #endif
155 #endif
156
157 #ifdef WIN32
158 #define strcasecmp stricmp
159 #endif
160
161 #include "icalrecur.h"
162
163 #include "icalerror.h"
164 #include "icalmemory.h"
165
166 #include <stdlib.h> /* for malloc */
167 #include <errno.h> /* for errno */
168 #include <string.h> /* for strdup and strchr*/
169 #include <assert.h>
170 #include <stddef.h> /* For offsetof() macro */
171 #ifdef HAVE_INTTYPES_H
172 #include <inttypes.h>
173 #endif
174
175 #include "pvl.h"
176
177 /** This is the last year we will go up to, since 32-bit time_t values
178 only go up to the start of 2038. */
179 #define MAX_TIME_T_YEAR 2037
180
181 #define TEMP_MAX 1024
182
183
184 #define BYDAYIDX impl->by_indices[BY_DAY]
185 #define BYDAYPTR impl->by_ptrs[BY_DAY]
186
187 #define BYMONIDX impl->by_indices[BY_MONTH]
188 #define BYMONPTR impl->by_ptrs[BY_MONTH]
189
190 #define BYMDIDX impl->by_indices[BY_MONTH_DAY]
191 #define BYMDPTR impl->by_ptrs[BY_MONTH_DAY]
192
193 #define BYWEEKIDX impl->by_indices[BY_WEEK_NO]
194 #define BYWEEKPTR impl->by_ptrs[BY_WEEK_NO]
195
196 const char* icalrecur_freq_to_string(icalrecurrencetype_frequency kind);
197 icalrecurrencetype_frequency icalrecur_string_to_freq(const char* str);
198
199 const char* icalrecur_weekday_to_string(icalrecurrencetype_weekday kind);
200 icalrecurrencetype_weekday icalrecur_string_to_weekday(const char* str);
201
202
203 /*********************** Rule parsing routines ************************/
204
205 struct icalrecur_parser {
206 const char* rule;
207 char* copy;
208 char* this_clause;
209 char* next_clause;
210
211 struct icalrecurrencetype rt;
212 };
213
icalrecur_first_clause(struct icalrecur_parser * parser)214 const char* icalrecur_first_clause(struct icalrecur_parser *parser)
215 {
216 char *idx;
217 parser->this_clause = parser->copy;
218
219 idx = strchr(parser->this_clause,';');
220
221 if (idx == 0){
222 parser->next_clause = 0;
223 return 0;
224 }
225
226 *idx = 0;
227 idx++;
228 parser->next_clause = idx;
229
230 return parser->this_clause;
231
232 }
233
icalrecur_next_clause(struct icalrecur_parser * parser)234 const char* icalrecur_next_clause(struct icalrecur_parser *parser)
235 {
236 char* idx;
237
238 parser->this_clause = parser->next_clause;
239
240 if(parser->this_clause == 0){
241 return 0;
242 }
243
244 idx = strchr(parser->this_clause,';');
245
246 if (idx == 0){
247 parser->next_clause = 0;
248 } else {
249
250 *idx = 0;
251 idx++;
252 parser->next_clause = idx;
253 }
254
255 return parser->this_clause;
256
257 }
258
icalrecur_clause_name_and_value(struct icalrecur_parser * parser,char ** name,char ** value)259 void icalrecur_clause_name_and_value(struct icalrecur_parser *parser,
260 char** name, char** value)
261 {
262 char *idx;
263
264 *name = parser->this_clause;
265
266 idx = strchr(parser->this_clause,'=');
267
268 if (idx == 0){
269 *name = 0;
270 *value = 0;
271 return;
272 }
273
274 *idx = 0;
275 idx++;
276 *value = idx;
277 }
278
icalrecur_add_byrules(struct icalrecur_parser * parser,short * array,int size,char * vals)279 void icalrecur_add_byrules(struct icalrecur_parser *parser, short *array,
280 int size, char* vals)
281 {
282 char *t, *n;
283 int i=0;
284 int sign = 1;
285 int v;
286
287 n = vals;
288
289 while(n != 0){
290
291 if(i == size){
292 return;
293 }
294
295 t = n;
296
297 n = strchr(t,',');
298
299 if(n != 0){
300 *n = 0;
301 n++;
302 }
303
304 /* Get optional sign. HACK. sign is not allowed for all BYxxx
305 rule parts */
306 if( *t == '-'){
307 sign = -1;
308 t++;
309 } else if (*t == '+'){
310 sign = 1;
311 t++;
312 } else {
313 sign = 1;
314 }
315
316 v = atoi(t) * sign ;
317
318
319 array[i++] = (short)v;
320 array[i] = ICAL_RECURRENCE_ARRAY_MAX;
321
322 }
323
324 }
325
326 /*
327 * Days in the BYDAY rule are expected by the code to be sorted, and while
328 * this may be the common case, the RFC doesn't actually mandate it. This
329 * function sorts the days taking into account the first day of week.
330 */
331 static void
sort_bydayrules(short * array,int week_start)332 sort_bydayrules(short *array, int week_start)
333 {
334 int one, two, i, j;
335
336 for (i=0;
337 i<ICAL_BY_DAY_SIZE && array[i] != ICAL_RECURRENCE_ARRAY_MAX;
338 i++) {
339 for (j=0; j<i; j++) {
340 one = icalrecurrencetype_day_day_of_week(array[j]) - week_start;
341 if (one < 0) one += 7;
342 two = icalrecurrencetype_day_day_of_week(array[i]) - week_start;
343 if (two < 0) two += 7;
344
345 if (one > two) {
346 short tmp = array[j];
347 array[j] = array[i];
348 array[i] = tmp;
349 }
350 }
351 }
352 }
353
icalrecur_add_bydayrules(struct icalrecur_parser * parser,const char * vals)354 void icalrecur_add_bydayrules(struct icalrecur_parser *parser, const char* vals)
355 {
356
357 char *t, *n;
358 int i=0;
359 int sign = 1;
360 int weekno = 0;
361 icalrecurrencetype_weekday wd;
362 short *array = parser->rt.by_day;
363 char* end;
364 char* vals_copy;
365
366 vals_copy = icalmemory_strdup(vals);
367
368 end = (char*)vals_copy+strlen(vals_copy);
369 n = vals_copy;
370
371 array[0] = ICAL_RECURRENCE_ARRAY_MAX;
372
373 while(n != 0){
374
375
376 t = n;
377
378 n = strchr(t,',');
379
380 if(n != 0){
381 *n = 0;
382 n++;
383 }
384
385 /* Get optional sign. */
386 if( *t == '-'){
387 sign = -1;
388 t++;
389 } else if (*t == '+'){
390 sign = 1;
391 t++;
392 } else {
393 sign = 1;
394 }
395
396 /* Get Optional weekno */
397 weekno = strtol(t,&t,10);
398
399 /* Outlook/Exchange generate "BYDAY=MO, FR" and "BYDAY=2 TH".
400 * Cope with that.
401 */
402 if (*t == ' ')
403 t++;
404
405 wd = icalrecur_string_to_weekday(t);
406
407 /* Sanity check value */
408 if (wd == ICAL_NO_WEEKDAY || weekno >= ICAL_BY_WEEKNO_SIZE) {
409 free(vals_copy);
410 return;
411 }
412
413 int position = sign * weekno;
414 array[i++] = (wd + (8 * abs(position))) * ((position < 0) ? -1 : 1);
415 array[i] = ICAL_RECURRENCE_ARRAY_MAX;
416 }
417
418 free(vals_copy);
419
420 sort_bydayrules(parser->rt.by_day, parser->rt.week_start);
421 }
422
423
icalrecurrencetype_from_string(const char * str)424 struct icalrecurrencetype icalrecurrencetype_from_string(const char* str)
425 {
426 struct icalrecur_parser parser;
427
428 memset(&parser,0,sizeof(parser));
429 icalrecurrencetype_clear(&parser.rt);
430
431 icalerror_check_arg_re(str!=0,"str",parser.rt);
432
433
434 /* Set up the parser struct */
435 parser.rule = str;
436 parser.copy = icalmemory_strdup(parser.rule);
437 parser.this_clause = parser.copy;
438
439 if(parser.copy == 0){
440 icalerror_set_errno(ICAL_NEWFAILED_ERROR);
441 return parser.rt;
442 }
443
444 /* Loop through all of the clauses */
445 for(icalrecur_first_clause(&parser);
446 parser.this_clause != 0;
447 icalrecur_next_clause(&parser))
448 {
449 char *name, *value;
450 icalrecur_clause_name_and_value(&parser,&name,&value);
451
452 if(name == 0){
453 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
454 icalrecurrencetype_clear(&parser.rt);
455 free(parser.copy);
456 return parser.rt;
457 }
458
459 if (strcasecmp(name,"FREQ") == 0){
460 parser.rt.freq = icalrecur_string_to_freq(value);
461 } else if (strcasecmp(name,"COUNT") == 0){
462 int v = atoi(value);
463 if (v >= 0) {
464 parser.rt.count = v;
465 }
466 } else if (strcasecmp(name,"UNTIL") == 0){
467 parser.rt.until = icaltime_from_string(value);
468 } else if (strcasecmp(name,"INTERVAL") == 0){
469 int v = atoi(value);
470 if (v > 0 && v <= SHRT_MAX) {
471 parser.rt.interval = (short) v;
472 }
473 } else if (strcasecmp(name,"WKST") == 0){
474 parser.rt.week_start = icalrecur_string_to_weekday(value);
475 sort_bydayrules(parser.rt.by_day, parser.rt.week_start);
476 } else if (strcasecmp(name,"BYSECOND") == 0){
477 icalrecur_add_byrules(&parser,parser.rt.by_second,
478 ICAL_BY_SECOND_SIZE,value);
479 } else if (strcasecmp(name,"BYMINUTE") == 0){
480 icalrecur_add_byrules(&parser,parser.rt.by_minute,
481 ICAL_BY_MINUTE_SIZE,value);
482 } else if (strcasecmp(name,"BYHOUR") == 0){
483 icalrecur_add_byrules(&parser,parser.rt.by_hour,
484 ICAL_BY_HOUR_SIZE,value);
485 } else if (strcasecmp(name,"BYDAY") == 0){
486 icalrecur_add_bydayrules(&parser,value);
487 } else if (strcasecmp(name,"BYMONTHDAY") == 0){
488 icalrecur_add_byrules(&parser,parser.rt.by_month_day,
489 ICAL_BY_MONTHDAY_SIZE,value);
490 } else if (strcasecmp(name,"BYYEARDAY") == 0){
491 icalrecur_add_byrules(&parser,parser.rt.by_year_day,
492 ICAL_BY_YEARDAY_SIZE,value);
493 } else if (strcasecmp(name,"BYWEEKNO") == 0){
494 icalrecur_add_byrules(&parser,parser.rt.by_week_no,
495 ICAL_BY_WEEKNO_SIZE,value);
496 } else if (strcasecmp(name,"BYMONTH") == 0){
497 icalrecur_add_byrules(&parser,parser.rt.by_month,
498 ICAL_BY_MONTH_SIZE,value);
499 } else if (strcasecmp(name,"BYSETPOS") == 0){
500 icalrecur_add_byrules(&parser,parser.rt.by_set_pos,
501 ICAL_BY_SETPOS_SIZE,value);
502 } else {
503 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
504 icalrecurrencetype_clear(&parser.rt);
505 free(parser.copy);
506 return parser.rt;
507 }
508
509 }
510
511 free(parser.copy);
512
513 return parser.rt;
514
515 }
516
517 static struct {const char* str;size_t offset; int limit; } recurmap[] =
518 {
519 {";BYSECOND=",offsetof(struct icalrecurrencetype,by_second),ICAL_BY_SECOND_SIZE - 1},
520 {";BYMINUTE=",offsetof(struct icalrecurrencetype,by_minute),ICAL_BY_MINUTE_SIZE - 1},
521 {";BYHOUR=",offsetof(struct icalrecurrencetype,by_hour),ICAL_BY_HOUR_SIZE - 1},
522 {";BYDAY=",offsetof(struct icalrecurrencetype,by_day),ICAL_BY_DAY_SIZE - 1},
523 {";BYMONTHDAY=",offsetof(struct icalrecurrencetype,by_month_day),ICAL_BY_MONTHDAY_SIZE - 1},
524 {";BYYEARDAY=",offsetof(struct icalrecurrencetype,by_year_day),ICAL_BY_YEARDAY_SIZE - 1},
525 {";BYWEEKNO=",offsetof(struct icalrecurrencetype,by_week_no),ICAL_BY_WEEKNO_SIZE - 1},
526 {";BYMONTH=",offsetof(struct icalrecurrencetype,by_month),ICAL_BY_MONTH_SIZE - 1},
527 {";BYSETPOS=",offsetof(struct icalrecurrencetype,by_set_pos),ICAL_BY_SETPOS_SIZE - 1},
528 {0,0,0},
529 };
530
531 /* A private routine in icalvalue.c */
532 void print_date_to_string(char* str, struct icaltimetype *data);
533 void print_datetime_to_string(char* str, struct icaltimetype *data);
534
icalrecurrencetype_as_string(struct icalrecurrencetype * recur)535 char* icalrecurrencetype_as_string(struct icalrecurrencetype *recur)
536 {
537 char *buf;
538 buf = icalrecurrencetype_as_string_r(recur);
539 icalmemory_add_tmp_buffer(buf);
540 return buf;
541 }
542
543
icalrecurrencetype_as_string_r(struct icalrecurrencetype * recur)544 char* icalrecurrencetype_as_string_r(struct icalrecurrencetype *recur)
545 {
546 char* str;
547 char *str_p;
548 size_t buf_sz = 200;
549 char temp[20];
550 int i,j;
551
552 if(recur->freq == ICAL_NO_RECURRENCE){
553 return 0;
554 }
555
556 str = (char*)icalmemory_new_buffer(buf_sz);
557 str_p = str;
558
559 icalmemory_append_string(&str,&str_p,&buf_sz,"FREQ=");
560 icalmemory_append_string(&str,&str_p,&buf_sz,
561 icalrecur_freq_to_string(recur->freq));
562
563 if(recur->until.year != 0){
564
565 temp[0] = 0;
566 if (recur->until.is_date)
567 print_date_to_string(temp,&(recur->until));
568 else
569 print_datetime_to_string(temp,&(recur->until));
570
571 icalmemory_append_string(&str,&str_p,&buf_sz,";UNTIL=");
572 icalmemory_append_string(&str,&str_p,&buf_sz, temp);
573 }
574
575 if(recur->count != 0){
576 snprintf(temp,sizeof(temp),"%d",recur->count);
577 icalmemory_append_string(&str,&str_p,&buf_sz,";COUNT=");
578 icalmemory_append_string(&str,&str_p,&buf_sz, temp);
579 }
580
581 if(recur->interval != 1){
582 snprintf(temp,sizeof(temp),"%d",recur->interval);
583 icalmemory_append_string(&str,&str_p,&buf_sz,";INTERVAL=");
584 icalmemory_append_string(&str,&str_p,&buf_sz, temp);
585 }
586
587 for(j =0; recurmap[j].str != 0; j++){
588 short* array = (short*)(recurmap[j].offset+ (size_t)recur);
589 int limit = recurmap[j].limit;
590
591 /* Skip unused arrays */
592 if( array[0] != ICAL_RECURRENCE_ARRAY_MAX ) {
593
594 icalmemory_append_string(&str,&str_p,&buf_sz,recurmap[j].str);
595
596 for(i=0;
597 i< limit && array[i] != ICAL_RECURRENCE_ARRAY_MAX;
598 i++){
599 if (j == 3) { /* BYDAY */
600 const char *daystr = icalrecur_weekday_to_string(
601 icalrecurrencetype_day_day_of_week(array[i]));
602 int pos;
603
604 pos = icalrecurrencetype_day_position(array[i]);
605
606 if (pos == 0)
607 icalmemory_append_string(&str,&str_p,&buf_sz,daystr);
608 else {
609 snprintf(temp,sizeof(temp),"%d%s",pos,daystr);
610 icalmemory_append_string(&str,&str_p,&buf_sz,temp);
611 }
612
613 } else {
614 snprintf(temp,sizeof(temp),"%d",array[i]);
615 icalmemory_append_string(&str,&str_p,&buf_sz, temp);
616 }
617
618 if( (i+1)<limit &&array[i+1]
619 != ICAL_RECURRENCE_ARRAY_MAX){
620 icalmemory_append_char(&str,&str_p,&buf_sz,',');
621 }
622 }
623 }
624 }
625
626 /* Monday is the default, so no need to write that out */
627 if ( recur->week_start != ICAL_MONDAY_WEEKDAY && recur->week_start != ICAL_NO_WEEKDAY ) {
628 const char *daystr = icalrecur_weekday_to_string(
629 icalrecurrencetype_day_day_of_week( recur->week_start ));
630 icalmemory_append_string(&str,&str_p,&buf_sz,";WKST=");
631 icalmemory_append_string(&str,&str_p,&buf_sz,daystr);
632 }
633
634 return str;
635 }
636
637
638 /************************* occurrence iteration routiens ******************/
639
640 enum byrule {
641 NO_CONTRACTION = -1,
642 BY_SECOND = 0,
643 BY_MINUTE = 1,
644 BY_HOUR = 2,
645 BY_DAY = 3,
646 BY_MONTH_DAY = 4,
647 BY_YEAR_DAY = 5,
648 BY_WEEK_NO = 6,
649 BY_MONTH = 7,
650 BY_SET_POS
651 };
652
653
654
655 struct icalrecur_iterator_impl {
656
657 struct icaltimetype dtstart; /* Hack. Make into time_t */
658 struct icaltimetype last; /* last time return from _iterator_next*/
659 int occurrence_no; /* number of step made on t iterator */
660 struct icalrecurrencetype rule;
661
662 short days[366];
663 short days_index;
664
665 enum byrule byrule;
666 short by_indices[9];
667 short orig_data[9]; /**< 1 if there was data in the byrule */
668
669
670 short *by_ptrs[9]; /**< Pointers into the by_* array elements of the rule */
671
672 };
673
674 static void increment_year(icalrecur_iterator* impl, int inc);
675
icalrecur_iterator_sizeof_byarray(short * byarray)676 int icalrecur_iterator_sizeof_byarray(short* byarray)
677 {
678 int array_itr;
679
680 for(array_itr = 0;
681 byarray[array_itr] != ICAL_RECURRENCE_ARRAY_MAX;
682 array_itr++){
683 }
684
685 return array_itr;
686 }
687
688 enum expand_table {
689 UNKNOWN = 0,
690 CONTRACT = 1,
691 EXPAND =2,
692 ILLEGAL=3
693 };
694
695 /**
696 * The split map indicates, for a particular interval, wether a BY_*
697 * rule part expands the number of instances in the occcurrence set or
698 * contracts it. 1=> contract, 2=>expand, and 3 means the pairing is
699 * not allowed.
700 */
701
702 struct expand_split_map_struct
703 {
704 icalrecurrencetype_frequency frequency;
705
706 /* Elements of the 'map' array correspond to the BYxxx rules:
707 Second,Minute,Hour,Day,Month Day,Year Day,Week No,Month*/
708
709 short map[8];
710 };
711
712 static const struct expand_split_map_struct expand_map[] =
713 {
714 {ICAL_SECONDLY_RECURRENCE,{1,1,1,1,1,1,1,1}},
715 {ICAL_MINUTELY_RECURRENCE,{2,1,1,1,1,1,1,1}},
716 {ICAL_HOURLY_RECURRENCE, {2,2,1,1,1,1,1,1}},
717 {ICAL_DAILY_RECURRENCE, {2,2,2,1,1,1,1,1}},
718 {ICAL_WEEKLY_RECURRENCE, {2,2,2,2,3,3,1,1}},
719 {ICAL_MONTHLY_RECURRENCE, {2,2,2,2,2,3,3,1}},
720 {ICAL_YEARLY_RECURRENCE, {2,2,2,2,2,2,2,2}},
721 {ICAL_NO_RECURRENCE, {0,0,0,0,0,0,0,0}}
722
723 };
724
725
726
727 /** Check that the rule has only the two given interday byrule parts. */
728 static
icalrecur_two_byrule(icalrecur_iterator * impl,enum byrule one,enum byrule two)729 int icalrecur_two_byrule(icalrecur_iterator* impl,
730 enum byrule one,enum byrule two)
731 {
732 short test_array[9];
733 enum byrule itr;
734 int passes = 0;
735
736 memset(test_array,0,sizeof(test_array));
737
738 test_array[one] = 1;
739 test_array[two] = 1;
740
741 for(itr = BY_DAY; itr != BY_SET_POS; itr++){
742
743 if( (test_array[itr] == 0 &&
744 impl->by_ptrs[itr][0] != ICAL_RECURRENCE_ARRAY_MAX
745 ) ||
746 (test_array[itr] == 1 &&
747 impl->by_ptrs[itr][0] == ICAL_RECURRENCE_ARRAY_MAX
748 )
749 ) {
750 /* test failed */
751 passes = 0;
752 }
753 }
754
755 return passes;
756
757 }
758
759 /** Check that the rule has only the one given interdat byrule parts. */
icalrecur_one_byrule(icalrecur_iterator * impl,enum byrule one)760 static int icalrecur_one_byrule(icalrecur_iterator* impl,enum byrule one)
761 {
762 int passes = 1;
763 enum byrule itr;
764
765 for(itr = BY_DAY; itr != BY_SET_POS; itr++){
766
767 if ((itr==one && impl->by_ptrs[itr][0] == ICAL_RECURRENCE_ARRAY_MAX) ||
768 (itr!=one && impl->by_ptrs[itr][0] != ICAL_RECURRENCE_ARRAY_MAX)) {
769 passes = 0;
770 }
771 }
772
773 return passes;
774 }
775 /*
776 static int count_byrules(icalrecur_iterator* impl)
777 {
778 int count = 0;
779 enum byrule itr;
780
781 for(itr = BY_DAY; itr <= BY_SET_POS; itr++){
782 if(impl->by_ptrs[itr][0] != ICAL_RECURRENCE_ARRAY_MAX){
783 count++;
784 }
785 }
786
787 return count;
788 }
789 */
790
setup_defaults(icalrecur_iterator * impl,enum byrule byrule,icalrecurrencetype_frequency req,int deftime,int * timepart)791 static void setup_defaults(icalrecur_iterator* impl,
792 enum byrule byrule, icalrecurrencetype_frequency req,
793 int deftime, int *timepart)
794 {
795
796 icalrecurrencetype_frequency freq;
797 freq = impl->rule.freq;
798
799 /* Re-write the BY rule arrays with data from the DTSTART time so
800 we don't have to explicitly deal with DTSTART */
801
802 if(impl->by_ptrs[byrule][0] == ICAL_RECURRENCE_ARRAY_MAX &&
803 expand_map[freq].map[byrule] != CONTRACT){
804 impl->by_ptrs[byrule][0] = (short)deftime;
805 }
806
807 /* Initialize the first occurrence */
808 if( freq != req && expand_map[freq].map[byrule] != CONTRACT){
809 *timepart = impl->by_ptrs[byrule][0];
810 }
811
812
813 }
814
has_by_data(icalrecur_iterator * impl,enum byrule byrule)815 static int has_by_data(icalrecur_iterator* impl, enum byrule byrule){
816
817 return (impl->orig_data[byrule] == 1);
818 }
819
820
821 static int expand_year_days(icalrecur_iterator* impl, int year);
822 static int nth_weekday(int dow, int pos, struct icaltimetype t);
823 static void increment_month(icalrecur_iterator* impl);
824 static int next_month(icalrecur_iterator* impl);
825
826
icalrecur_iterator_new(struct icalrecurrencetype rule,struct icaltimetype dtstart)827 icalrecur_iterator* icalrecur_iterator_new(struct icalrecurrencetype rule,
828 struct icaltimetype dtstart)
829 {
830 icalrecur_iterator* impl;
831 icalrecurrencetype_frequency freq;
832
833 icalerror_clear_errno();
834
835 if ( ( impl = (icalrecur_iterator*)
836 malloc(sizeof(icalrecur_iterator))) == 0) {
837 icalerror_set_errno(ICAL_NEWFAILED_ERROR);
838 return 0;
839 }
840
841 memset(impl,0,sizeof(icalrecur_iterator));
842
843 impl->rule = rule;
844 impl->last = dtstart;
845 impl->dtstart = dtstart;
846 impl->days_index =0;
847 impl->occurrence_no = 0;
848 freq = impl->rule.freq;
849
850 /* Set up convienience pointers to make the code simpler. Allows
851 us to iterate through all of the BY* arrays in the rule. */
852
853 impl->by_ptrs[BY_MONTH]=impl->rule.by_month;
854 impl->by_ptrs[BY_WEEK_NO]=impl->rule.by_week_no;
855 impl->by_ptrs[BY_YEAR_DAY]=impl->rule.by_year_day;
856 impl->by_ptrs[BY_MONTH_DAY]=impl->rule.by_month_day;
857 impl->by_ptrs[BY_DAY]=impl->rule.by_day;
858 impl->by_ptrs[BY_HOUR]=impl->rule.by_hour;
859 impl->by_ptrs[BY_MINUTE]=impl->rule.by_minute;
860 impl->by_ptrs[BY_SECOND]=impl->rule.by_second;
861 impl->by_ptrs[BY_SET_POS]=impl->rule.by_set_pos;
862
863 memset(impl->orig_data,0,9*sizeof(short));
864
865 /* Note which by rules had data in them when the iterator was
866 created. We can't use the actuall by_x arrays, because the
867 empty ones will be given default values later in this
868 routine. The orig_data array will be used later in has_by_data */
869
870 impl->orig_data[BY_MONTH]
871 = (short)(impl->rule.by_month[0]!=ICAL_RECURRENCE_ARRAY_MAX);
872 impl->orig_data[BY_WEEK_NO]
873 =(short)(impl->rule.by_week_no[0]!=ICAL_RECURRENCE_ARRAY_MAX);
874 impl->orig_data[BY_YEAR_DAY]
875 =(short)(impl->rule.by_year_day[0]!=ICAL_RECURRENCE_ARRAY_MAX);
876 impl->orig_data[BY_MONTH_DAY]
877 =(short)(impl->rule.by_month_day[0]!=ICAL_RECURRENCE_ARRAY_MAX);
878 impl->orig_data[BY_DAY]
879 = (short)(impl->rule.by_day[0]!=ICAL_RECURRENCE_ARRAY_MAX);
880 impl->orig_data[BY_HOUR]
881 = (short)(impl->rule.by_hour[0]!=ICAL_RECURRENCE_ARRAY_MAX);
882 impl->orig_data[BY_MINUTE]
883 = (short)(impl->rule.by_minute[0]!=ICAL_RECURRENCE_ARRAY_MAX);
884 impl->orig_data[BY_SECOND]
885 = (short)(impl->rule.by_second[0]!=ICAL_RECURRENCE_ARRAY_MAX);
886 impl->orig_data[BY_SET_POS]
887 = (short)(impl->rule.by_set_pos[0]!=ICAL_RECURRENCE_ARRAY_MAX);
888
889
890 /* Check if the recurrence rule is legal */
891
892 /* If the BYYEARDAY appears, no other date rule part may appear. */
893
894 if(icalrecur_two_byrule(impl,BY_YEAR_DAY,BY_MONTH) ||
895 icalrecur_two_byrule(impl,BY_YEAR_DAY,BY_WEEK_NO) ||
896 icalrecur_two_byrule(impl,BY_YEAR_DAY,BY_MONTH_DAY) ||
897 icalrecur_two_byrule(impl,BY_YEAR_DAY,BY_DAY) ){
898
899 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
900 free(impl);
901 return 0;
902 }
903
904
905
906 /* BYWEEKNO and BYMONTHDAY rule parts may not both appear.*/
907
908 if(icalrecur_two_byrule(impl,BY_WEEK_NO,BY_MONTH_DAY)){
909 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
910 free(impl);
911 return 0;
912 }
913
914
915 /*For MONTHLY recurrences (FREQ=MONTHLY) neither BYYEARDAY nor
916 BYWEEKNO may appear. */
917
918 if(freq == ICAL_MONTHLY_RECURRENCE &&
919 icalrecur_one_byrule(impl,BY_WEEK_NO)){
920 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
921 free(impl);
922 return 0;
923 }
924
925
926 /*For WEEKLY recurrences (FREQ=WEEKLY) neither BYMONTHDAY nor
927 BYYEARDAY may appear. */
928
929 if(freq == ICAL_WEEKLY_RECURRENCE &&
930 icalrecur_one_byrule(impl,BY_MONTH_DAY )) {
931 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
932 free(impl);
933 return 0;
934 }
935
936 /* BYYEARDAY may only appear in YEARLY rules */
937 if(freq != ICAL_YEARLY_RECURRENCE &&
938 icalrecur_one_byrule(impl,BY_YEAR_DAY )) {
939 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
940 free(impl);
941 return 0;
942 }
943
944 /* Rewrite some of the rules and set up defaults to make later
945 processing easier. Primarily, t involves copying an element
946 from the start time into the corresponding BY_* array when the
947 BY_* array is empty */
948
949
950 setup_defaults(impl,BY_SECOND,ICAL_SECONDLY_RECURRENCE,
951 impl->dtstart.second,
952 &(impl->last.second));
953
954 setup_defaults(impl,BY_MINUTE,ICAL_MINUTELY_RECURRENCE,
955 impl->dtstart.minute,
956 &(impl->last.minute));
957
958 setup_defaults(impl,BY_HOUR,ICAL_HOURLY_RECURRENCE,
959 impl->dtstart.hour,
960 &(impl->last.hour));
961
962 setup_defaults(impl,BY_MONTH_DAY,ICAL_DAILY_RECURRENCE,
963 impl->dtstart.day,
964 &(impl->last.day));
965
966 setup_defaults(impl,BY_MONTH,ICAL_MONTHLY_RECURRENCE,
967 impl->dtstart.month,
968 &(impl->last.month));
969
970
971 if(impl->rule.freq == ICAL_WEEKLY_RECURRENCE ){
972
973 if(impl->by_ptrs[BY_DAY][0] == ICAL_RECURRENCE_ARRAY_MAX){
974
975 /* Weekly recurrences with no BY_DAY data should occur on the
976 same day of the week as the start time . */
977 impl->by_ptrs[BY_DAY][0] = (short)icaltime_day_of_week(impl->dtstart);
978
979 } else {
980 /* If there is BY_DAY data, then we need to move the initial
981 time to the start of the BY_DAY data. That is if the
982 start time is on a Wednesday, and the rule has
983 BYDAY=MO,WE,FR, move the initial time back to
984 monday. Otherwise, jumping to the next week ( jumping 7
985 days ahead ) will skip over some occurrences in the
986 second week. */
987
988 /* This depends on impl->by_ptrs[BY_DAY] being correctly sorted by
989 * day. This should probably be abstracted to make such assumption
990 * more explicit. */
991 short dow = (short)(impl->by_ptrs[BY_DAY][0]-icaltime_day_of_week(impl->last));
992
993 if((icaltime_day_of_week(impl->last) < impl->by_ptrs[BY_DAY][0] && dow >= 0) || dow < 0)
994 {
995 /* initial time is after first day of BY_DAY data */
996 impl->last.day += dow;
997 impl->last = icaltime_normalize(impl->last);
998 }
999
1000 }
1001
1002
1003 }
1004
1005 /* For YEARLY rule, begin by setting up the year days array . The
1006 YEARLY rules work by expanding one year at a time. */
1007
1008 if(impl->rule.freq == ICAL_YEARLY_RECURRENCE){
1009 struct icaltimetype next;
1010 icalerror_clear_errno();
1011
1012 for (;;) {
1013 expand_year_days(impl, impl->last.year);
1014 if( icalerrno != ICAL_NO_ERROR) {
1015 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
1016 free(impl);
1017 return 0;
1018 }
1019 if (impl->days[0] != ICAL_RECURRENCE_ARRAY_MAX)
1020 break; /* break when no days are expanded */
1021 increment_year(impl,impl->rule.interval);
1022 }
1023
1024 /* Copy the first day into last. */
1025 next = icaltime_from_day_of_year(impl->days[0], impl->last.year);
1026
1027 impl->last.day = next.day;
1028 impl->last.month = next.month;
1029 }
1030
1031
1032 /* If this is a monthly interval with by day data, then we need to
1033 set the last value to the appropriate day of the month */
1034
1035 if(impl->rule.freq == ICAL_MONTHLY_RECURRENCE &&
1036 has_by_data(impl,BY_DAY)) {
1037
1038 struct icaltimetype tmp_last = icaltime_null_time();
1039 struct icaltimetype init_last = impl->last;
1040 int days_in_month =
1041 icaltime_days_in_month(impl->last.month, impl->last.year);
1042 int i, dow, pos, day_of_month;
1043
1044 /* Check every weekday in BYDAY with relative dow and pos. */
1045 for (i = 0; impl->by_ptrs[BY_DAY][i] != ICAL_RECURRENCE_ARRAY_MAX; i++) {
1046 impl->last = init_last;
1047 dow = icalrecurrencetype_day_day_of_week(impl->by_ptrs[BY_DAY][i]);
1048 pos = icalrecurrencetype_day_position(impl->by_ptrs[BY_DAY][i]);
1049 day_of_month = nth_weekday(dow, pos, impl->last);
1050
1051 /* If |pos| >= 6, the byday is invalid for a monthly rule */
1052 if (pos >= 6 || pos <= -6) {
1053 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
1054 free(impl);
1055 return 0;
1056 }
1057
1058 /* If a Byday with pos=+/-5 is not in the current month it
1059 must be searched in the next months. */
1060 if (day_of_month > days_in_month || day_of_month <= 0) {
1061 /* Skip if we have already found a "last" in this month. */
1062 if (!icaltime_is_null_time(tmp_last) && tmp_last.month == init_last.month) {
1063 continue;
1064 }
1065 while (day_of_month > days_in_month || day_of_month <= 0) {
1066 impl->last.day = 1;
1067 increment_month(impl);
1068 days_in_month =
1069 icaltime_days_in_month(impl->last.month, impl->last.year);
1070 day_of_month = nth_weekday(dow, pos, impl->last);
1071 }
1072 }
1073
1074 impl->last.day = day_of_month;
1075 if (icaltime_is_null_time(tmp_last) ||
1076 icaltime_compare(impl->last, tmp_last) < 0) {
1077 tmp_last = impl->last;
1078 }
1079 }
1080
1081 impl->last = tmp_last;
1082
1083
1084 if (impl->last.day > days_in_month || impl->last.day == 0) {
1085 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
1086 free(impl);
1087 return 0;
1088 }
1089
1090 if (has_by_data(impl, BY_MONTH_DAY)) {
1091 /* If there is also a BYMONTHDAY rule, the "last" found must
1092 match one of the bymonthdays too.
1093 The funtion next_month() allows to find it. */
1094
1095 int months_counter = 48; /* Maximum number of months to check for
1096 (keeping in count a possible leap year).*/
1097 impl->last.day--;
1098 while (!next_month(impl) && months_counter) {
1099 /* If next_month() hasn't found a valid day, continue to loop
1100 in the next month.
1101 Malformed rules such as BYDAY=4MO;BYMONTHDAY=1,2,3 can
1102 cause an infinite loop, months_counter allows to get out. */
1103 months_counter--;
1104 }
1105 if (months_counter <= 0) {
1106 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
1107 free(impl);
1108 return 0;
1109 }
1110 }
1111
1112 } else if (has_by_data(impl,BY_MONTH_DAY)) {
1113 // setup_defaults sets the day to -1 for negative BYMONTHDAY values,
1114 // so make sure to re-calculate with days_in_month
1115 if (impl->last.day < 0) {
1116 int days_in_month =
1117 icaltime_days_in_month(impl->last.month, impl->last.year);
1118 impl->last.day = days_in_month + impl->last.day + 1;
1119 }
1120 impl->last = icaltime_normalize(impl->last);
1121 }
1122
1123
1124
1125 return impl;
1126 }
1127
1128
icalrecur_iterator_free(icalrecur_iterator * i)1129 void icalrecur_iterator_free(icalrecur_iterator* i)
1130 {
1131 icalerror_check_arg_rv((i!=0),"impl");
1132
1133 free(i);
1134
1135 }
1136
increment_year(icalrecur_iterator * impl,int inc)1137 static void increment_year(icalrecur_iterator* impl, int inc)
1138 {
1139 impl->last.year+=inc;
1140 }
1141
1142 /** Increment month is different that the other incement_* routines --
1143 it figures out the interval for itself, and uses BYMONTH data if
1144 available. */
increment_month(icalrecur_iterator * impl)1145 static void increment_month(icalrecur_iterator* impl)
1146 {
1147 int years;
1148
1149 if(has_by_data(impl,BY_MONTH) ){
1150 /* Ignore the frequency and use the byrule data */
1151
1152 impl->by_indices[BY_MONTH]++;
1153
1154 if (impl->by_ptrs[BY_MONTH][impl->by_indices[BY_MONTH]]
1155 ==ICAL_RECURRENCE_ARRAY_MAX){
1156 impl->by_indices[BY_MONTH] = 0;
1157
1158 increment_year(impl,1);
1159
1160 }
1161
1162 impl->last.month =
1163 impl->by_ptrs[BY_MONTH][impl->by_indices[BY_MONTH]];
1164
1165 } else {
1166
1167 int inc;
1168
1169 if(impl->rule.freq == ICAL_MONTHLY_RECURRENCE){
1170 inc = impl->rule.interval;
1171 } else {
1172 inc = 1;
1173 }
1174
1175 impl->last.month+=inc;
1176
1177 /* Months are offset by one */
1178 impl->last.month--;
1179
1180 years = impl->last.month / 12;
1181
1182 impl->last.month = impl->last.month % 12;
1183
1184 impl->last.month++;
1185
1186 if (years != 0){
1187 increment_year(impl,years);
1188 }
1189 }
1190 }
1191
increment_monthday(icalrecur_iterator * impl,int inc)1192 static void increment_monthday(icalrecur_iterator* impl, int inc)
1193 {
1194 int i;
1195
1196 for(i=0; i<inc; i++){
1197
1198 int days_in_month =
1199 icaltime_days_in_month(impl->last.month, impl->last.year);
1200
1201 impl->last.day++;
1202
1203 if (impl->last.day > days_in_month){
1204 impl->last.day = impl->last.day-days_in_month;
1205 increment_month(impl);
1206 }
1207 }
1208 }
1209
1210
increment_hour(icalrecur_iterator * impl,int inc)1211 static void increment_hour(icalrecur_iterator* impl, int inc)
1212 {
1213 int days;
1214
1215 impl->last.hour+=inc;
1216
1217 days = impl->last.hour / 24;
1218 impl->last.hour = impl->last.hour % 24;
1219
1220 if (days != 0){
1221 increment_monthday(impl,days);
1222 }
1223 }
1224
increment_minute(icalrecur_iterator * impl,int inc)1225 static void increment_minute(icalrecur_iterator* impl, int inc)
1226 {
1227 int hours;
1228
1229 impl->last.minute+=inc;
1230
1231 hours = impl->last.minute / 60;
1232 impl->last.minute = impl->last.minute % 60;
1233
1234 if (hours != 0){
1235 increment_hour(impl,hours);
1236 }
1237
1238 }
1239
increment_second(icalrecur_iterator * impl,int inc)1240 static void increment_second(icalrecur_iterator* impl, int inc)
1241 {
1242 int minutes;
1243
1244 impl->last.second+=inc;
1245
1246 minutes = impl->last.second / 60;
1247 impl->last.second = impl->last.second % 60;
1248
1249 if (minutes != 0)
1250 {
1251 increment_minute(impl, minutes);
1252 }
1253 }
1254
1255 #if 0
1256 #include "ical.h"
1257 void test_increment()
1258 {
1259 icalrecur_iterator impl;
1260
1261 impl.last = icaltime_from_string("20000101T000000Z");
1262
1263 printf("Orig: %s\n",icaltime_as_ctime(impl.last));
1264
1265 increment_second(&impl,5);
1266 printf("+ 5 sec : %s\n",icaltime_as_ctime(impl.last));
1267
1268 increment_second(&impl,355);
1269 printf("+ 355 sec : %s\n",icaltime_as_ctime(impl.last));
1270
1271 increment_minute(&impl,5);
1272 printf("+ 5 min : %s\n",icaltime_as_ctime(impl.last));
1273
1274 increment_minute(&impl,360);
1275 printf("+ 360 min : %s\n",icaltime_as_ctime(impl.last));
1276 increment_hour(&impl,5);
1277 printf("+ 5 hours : %s\n",icaltime_as_ctime(impl.last));
1278 increment_hour(&impl,43);
1279 printf("+ 43 hours : %s\n",icaltime_as_ctime(impl.last));
1280 increment_monthday(&impl,3);
1281 printf("+ 3 days : %s\n",icaltime_as_ctime(impl.last));
1282 increment_monthday(&impl,600);
1283 printf("+ 600 days : %s\n",icaltime_as_ctime(impl.last));
1284
1285 }
1286
1287 #endif
1288
next_second(icalrecur_iterator * impl)1289 static int next_second(icalrecur_iterator* impl)
1290 {
1291
1292 int has_by_second = (impl->by_ptrs[BY_SECOND][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1293 int this_frequency = (impl->rule.freq == ICAL_SECONDLY_RECURRENCE);
1294
1295 int end_of_data = 0;
1296
1297 assert(has_by_second || this_frequency);
1298
1299 if( has_by_second ){
1300 /* Ignore the frequency and use the byrule data */
1301
1302 impl->by_indices[BY_SECOND]++;
1303
1304 if (impl->by_ptrs[BY_SECOND][impl->by_indices[BY_SECOND]]
1305 ==ICAL_RECURRENCE_ARRAY_MAX){
1306 impl->by_indices[BY_SECOND] = 0;
1307
1308 end_of_data = 1;
1309 }
1310
1311
1312 impl->last.second =
1313 impl->by_ptrs[BY_SECOND][impl->by_indices[BY_SECOND]];
1314
1315
1316 } else if( !has_by_second && this_frequency ){
1317 /* Compute the next value from the last time and the frequency interval*/
1318 increment_second(impl, impl->rule.interval);
1319
1320 }
1321
1322 /* If we have gone through all of the seconds on the BY list, then we
1323 need to move to the next minute */
1324
1325 if(has_by_second && end_of_data && this_frequency ){
1326 increment_minute(impl,1);
1327 }
1328
1329 return end_of_data;
1330
1331 }
1332
next_minute(icalrecur_iterator * impl)1333 static int next_minute(icalrecur_iterator* impl)
1334 {
1335
1336 int has_by_minute = (impl->by_ptrs[BY_MINUTE][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1337 int this_frequency = (impl->rule.freq == ICAL_MINUTELY_RECURRENCE);
1338
1339 int end_of_data = 0;
1340
1341 assert(has_by_minute || this_frequency);
1342
1343
1344 if (next_second(impl) == 0){
1345 return 0;
1346 }
1347
1348 if( has_by_minute ){
1349 /* Ignore the frequency and use the byrule data */
1350
1351 impl->by_indices[BY_MINUTE]++;
1352
1353 if (impl->by_ptrs[BY_MINUTE][impl->by_indices[BY_MINUTE]]
1354 ==ICAL_RECURRENCE_ARRAY_MAX){
1355
1356 impl->by_indices[BY_MINUTE] = 0;
1357
1358 end_of_data = 1;
1359 }
1360
1361 impl->last.minute =
1362 impl->by_ptrs[BY_MINUTE][impl->by_indices[BY_MINUTE]];
1363
1364 } else if( !has_by_minute && this_frequency ){
1365 /* Compute the next value from the last time and the frequency interval*/
1366 increment_minute(impl,impl->rule.interval);
1367 }
1368
1369 /* If we have gone through all of the minutes on the BY list, then we
1370 need to move to the next hour */
1371
1372 if(has_by_minute && end_of_data && this_frequency ){
1373 increment_hour(impl,1);
1374 }
1375
1376 return end_of_data;
1377 }
1378
next_hour(icalrecur_iterator * impl)1379 static int next_hour(icalrecur_iterator* impl)
1380 {
1381
1382 int has_by_hour = (impl->by_ptrs[BY_HOUR][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1383 int this_frequency = (impl->rule.freq == ICAL_HOURLY_RECURRENCE);
1384
1385 int end_of_data = 0;
1386
1387 assert(has_by_hour || this_frequency);
1388
1389 if (next_minute(impl) == 0){
1390 return 0;
1391 }
1392
1393 if( has_by_hour ){
1394 /* Ignore the frequency and use the byrule data */
1395
1396 impl->by_indices[BY_HOUR]++;
1397
1398 if (impl->by_ptrs[BY_HOUR][impl->by_indices[BY_HOUR]]
1399 ==ICAL_RECURRENCE_ARRAY_MAX){
1400 impl->by_indices[BY_HOUR] = 0;
1401
1402 end_of_data = 1;
1403 }
1404
1405 impl->last.hour =
1406 impl->by_ptrs[BY_HOUR][impl->by_indices[BY_HOUR]];
1407
1408 } else if( !has_by_hour && this_frequency ){
1409 /* Compute the next value from the last time and the frequency interval*/
1410 increment_hour(impl,impl->rule.interval);
1411
1412 }
1413
1414 /* If we have gone through all of the hours on the BY list, then we
1415 need to move to the next day */
1416
1417 if(has_by_hour && end_of_data && this_frequency ){
1418 increment_monthday(impl,1);
1419 }
1420
1421 return end_of_data;
1422
1423 }
1424
next_day(icalrecur_iterator * impl)1425 static int next_day(icalrecur_iterator* impl)
1426 {
1427
1428 int has_by_day = (impl->by_ptrs[BY_DAY][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1429 int this_frequency = (impl->rule.freq == ICAL_DAILY_RECURRENCE);
1430
1431 assert(has_by_day || this_frequency);
1432
1433 if (next_hour(impl) == 0){
1434 return 0;
1435 }
1436
1437 /* Always increment through the interval, since this routine is not
1438 called by any other next_* routine, and the days that are
1439 excluded will be taken care of by restriction filtering */
1440
1441 if(this_frequency){
1442 increment_monthday(impl,impl->rule.interval);
1443 } else {
1444 increment_monthday(impl,1);
1445 }
1446
1447
1448 return 0;
1449
1450 }
1451
1452 /*
1453 static int next_yearday(icalrecur_iterator* impl)
1454 {
1455
1456 int has_by_yearday = (impl->by_ptrs[BY_YEAR_DAY][0]!=ICAL_RECURRENCE_ARRAY_MAX);
1457
1458 int end_of_data = 0;
1459
1460 assert(has_by_yearday );
1461
1462 if (next_hour(impl) == 0){
1463 return 0;
1464 }
1465
1466 impl->by_indices[BY_YEAR_DAY]++;
1467
1468 if (impl->by_ptrs[BY_YEAR_DAY][impl->by_indices[BY_YEAR_DAY]]
1469 ==ICAL_RECURRENCE_ARRAY_MAX){
1470 impl->by_indices[BY_YEAR_DAY] = 0;
1471
1472 end_of_data = 1;
1473 }
1474
1475 impl->last.day =
1476 impl->by_ptrs[BY_YEAR_DAY][impl->by_indices[BY_YEAR_DAY]];
1477
1478 if(has_by_yearday && end_of_data){
1479 increment_year(impl,1);
1480 }
1481
1482 return end_of_data;
1483
1484 }
1485 */
1486
1487 /* Returns the day of the month for the current month of t that is the
1488 pos'th instance of the day-of-week dow */
1489
nth_weekday(int dow,int pos,struct icaltimetype t)1490 static int nth_weekday(int dow, int pos, struct icaltimetype t){
1491
1492 int days_in_month = icaltime_days_in_month(t.month, t.year);
1493 int end_dow, start_dow;
1494 int wd;
1495
1496 if(pos >= 0){
1497 t.day = 1;
1498 start_dow = icaltime_day_of_week(t);
1499
1500 if (pos != 0) {
1501 pos--;
1502 }
1503
1504 /* find month day of first occurrence of dow -- such as the
1505 month day of the first monday */
1506
1507 wd = dow-start_dow+1;
1508
1509 if (wd <= 0){
1510 wd = wd + 7;
1511 }
1512
1513 wd = wd + pos * 7;
1514
1515 } else {
1516 t.day = days_in_month;
1517 end_dow = icaltime_day_of_week(t);
1518
1519 pos++;
1520
1521 /* find month day of last occurrence of dow -- such as the
1522 month day of the last monday */
1523
1524 wd = (end_dow - dow);
1525
1526 if (wd < 0){
1527 wd = wd+ 7;
1528 }
1529
1530 wd = days_in_month - wd;
1531
1532 wd = wd + pos * 7;
1533 }
1534
1535 return wd;
1536 }
1537
is_day_in_byday(icalrecur_iterator * impl,struct icaltimetype tt)1538 static int is_day_in_byday(icalrecur_iterator* impl,struct icaltimetype tt){
1539
1540 int idx;
1541
1542 for(idx = 0; BYDAYPTR[idx] != ICAL_RECURRENCE_ARRAY_MAX; idx++){
1543 int dow = icalrecurrencetype_day_day_of_week(BYDAYPTR[idx]);
1544 int pos = icalrecurrencetype_day_position(BYDAYPTR[idx]);
1545 int this_dow = icaltime_day_of_week(tt);
1546
1547 if( (pos == 0 && dow == this_dow ) || /* Just a dow, like "TU" or "FR" */
1548 (nth_weekday(dow,pos,tt) == tt.day)){ /*pos+wod: "3FR" or -1TU" */
1549 return 1;
1550 }
1551 }
1552
1553 return 0;
1554 }
1555
check_set_position(icalrecur_iterator * impl,int set_pos)1556 int check_set_position(icalrecur_iterator* impl, int set_pos)
1557 {
1558 int i;
1559 int found = 0;
1560 for (i = 0; impl->rule.by_set_pos[i] != ICAL_RECURRENCE_ARRAY_MAX &&
1561 i != ICAL_BY_SETPOS_SIZE; i++){
1562 if (impl->rule.by_set_pos[i] == set_pos) {
1563 found = 1;
1564 break;
1565 }
1566 }
1567 return found;
1568 }
1569
next_month(icalrecur_iterator * impl)1570 static int next_month(icalrecur_iterator* impl)
1571 {
1572 int data_valid = 1;
1573
1574 int this_frequency = (impl->rule.freq == ICAL_MONTHLY_RECURRENCE);
1575
1576 assert( has_by_data(impl,BY_MONTH) || this_frequency);
1577
1578 /* Iterate through the occurrences within a day. If we don't get to
1579 the end of the intra-day data, don't bother going to the next
1580 month */
1581
1582 if (next_hour(impl) == 0){
1583 return data_valid; /* Signal that the data is valid */
1584 }
1585
1586 /* Now iterate through the occurrences within a month -- by days,
1587 weeks or weekdays. */
1588
1589 /*
1590 * Case 1:
1591 * Rules Like: FREQ=MONTHLY;INTERVAL=1;BYDAY=FR;BYMONTHDAY=13
1592 */
1593
1594 if(has_by_data(impl,BY_DAY) && has_by_data(impl,BY_MONTH_DAY)){
1595 int day, idx,j;
1596 int days_in_month = icaltime_days_in_month(impl->last.month,
1597 impl->last.year);
1598 /* Iterate through the remaining days in the month and check if
1599 each day is listed in the BY_DAY array and in the BY_MONTHDAY
1600 array. This seems very inneficient, but I think it is the
1601 simplest way to account for both BYDAY=1FR (First friday in
1602 month) and BYDAY=FR ( every friday in month ) */
1603
1604 for(day = impl->last.day+1; day <= days_in_month; day++){
1605 for(idx = 0; BYDAYPTR[idx] != ICAL_RECURRENCE_ARRAY_MAX; idx++){
1606 for(j = 0; BYMDPTR[j]!=ICAL_RECURRENCE_ARRAY_MAX; j++){
1607 int dow =
1608 icalrecurrencetype_day_day_of_week(BYDAYPTR[idx]);
1609 int pos = icalrecurrencetype_day_position(BYDAYPTR[idx]);
1610 int mday = BYMDPTR[j];
1611 int this_dow;
1612
1613 impl->last.day = day;
1614 this_dow = icaltime_day_of_week(impl->last);
1615
1616 if( (pos == 0 && dow == this_dow && mday == day) ||
1617 (nth_weekday(dow,pos,impl->last) == day && mday==day)){
1618 goto MDEND;
1619 }
1620 }
1621 }
1622 }
1623
1624 MDEND:
1625
1626 if ( day > days_in_month){
1627 impl->last.day = 1;
1628 increment_month(impl);
1629 impl->last.day--; /* Go back one day, so searches next month start at day 1 */
1630 data_valid = 0; /* signal that impl->last is invalid */
1631 }
1632
1633
1634 /*
1635 * Case 2:
1636 * Rules Like: FREQ=MONTHLY;INTERVAL=1;BYDAY=FR
1637 */
1638
1639 } else if(has_by_data(impl,BY_DAY)){
1640 /* For this case, the weekdays are relative to the
1641 month. BYDAY=FR -> First Friday in month, etc. */
1642
1643 /* This code iterates through the remaining days in the month
1644 and checks if each day is listed in the BY_DAY array. This
1645 seems very inneficient, but I think it is the simplest way to
1646 account for both BYDAY=1FR (First friday in month) and
1647 BYDAY=FR ( every friday in month ) */
1648
1649 int day;
1650 int days_in_month = icaltime_days_in_month(impl->last.month,
1651 impl->last.year);
1652 int set_pos_counter = 0;
1653 int set_pos_total = 0;
1654 int found = 0;
1655
1656 assert( BYDAYPTR[0]!=ICAL_RECURRENCE_ARRAY_MAX);
1657
1658 /* Count the past positions for the BYSETPOS calculation */
1659 if(has_by_data(impl,BY_SET_POS)){
1660 int last_day = impl->last.day;
1661 for(day = 1; day <= days_in_month; day++){
1662 impl->last.day = day;
1663
1664 if(is_day_in_byday(impl,impl->last)){
1665 set_pos_total++;
1666 if(day <= last_day)
1667 set_pos_counter++;
1668 }
1669 }
1670 impl->last.day = last_day;
1671 }
1672
1673 for(day = impl->last.day+1; day <= days_in_month; day++){
1674 impl->last.day = day;
1675
1676 if(is_day_in_byday(impl,impl->last)){
1677 /* If there is no BYSETPOS rule, calculate only by BYDAY
1678 If there is BYSETPOS rule, take into account the occurence
1679 matches with BYDAY */
1680 if(!has_by_data(impl,BY_SET_POS) || check_set_position(impl, ++set_pos_counter)
1681 || check_set_position(impl, set_pos_counter-set_pos_total-1)) {
1682 found = 1;
1683 break;
1684 }
1685 }
1686 }
1687
1688 data_valid = found;
1689
1690 if ( day > days_in_month){
1691 impl->last.day = 1;
1692 increment_month(impl);
1693
1694 /* Did moving to the next month put us on a valid date? if
1695 so, note that the new data is valid, if, not, mark it
1696 invalid */
1697
1698 if(is_day_in_byday(impl,impl->last)){
1699 /* If there is no BYSETPOS rule or BYSETPOS=1, new data is valid */
1700 if(!has_by_data(impl,BY_SET_POS) || check_set_position(impl,1))
1701 data_valid = 1;
1702 } else {
1703 data_valid = 0; /* signal that impl->last is invalid */
1704 }
1705 }
1706
1707 /*
1708 * Case 3
1709 * Rules Like: FREQ=MONTHLY;COUNT=10;BYMONTHDAY=-3
1710 */
1711
1712 } else if (has_by_data(impl,BY_MONTH_DAY)) {
1713 int day, days_in_month;
1714
1715 assert( BYMDPTR[0]!=ICAL_RECURRENCE_ARRAY_MAX);
1716
1717 BYMDIDX++;
1718
1719 /* Are we at the end of the BYDAY array? */
1720 if (BYMDPTR[BYMDIDX] ==ICAL_RECURRENCE_ARRAY_MAX){
1721
1722 BYMDIDX = 0; /* Reset to 0 */
1723 increment_month(impl);
1724 }
1725
1726 days_in_month = icaltime_days_in_month(impl->last.month,
1727 impl->last.year);
1728
1729 day = BYMDPTR[BYMDIDX];
1730
1731 if (day < 0) {
1732 day = icaltime_days_in_month(impl->last.month, impl->last.year) + day + 1;
1733 }
1734
1735 if ( day > days_in_month){
1736 impl->last.day = 1;
1737
1738 /* Did moving to the next month put us on a valid date? if
1739 so, note that the new data is valid, if, not, mark it
1740 invalid */
1741
1742 if(is_day_in_byday(impl,impl->last)){
1743 data_valid = 1;
1744 } else {
1745 data_valid = 0; /* signal that impl->last is invalid */
1746 }
1747 }
1748
1749 impl->last.day = day;
1750
1751 } else {
1752 int days_in_month;
1753
1754 assert( BYMDPTR[0]!=ICAL_RECURRENCE_ARRAY_MAX);
1755 impl->last.day = BYMDPTR[0];
1756
1757 increment_month(impl);
1758
1759 days_in_month = icaltime_days_in_month(impl->last.month,
1760 impl->last.year);
1761 if (impl->last.day > days_in_month) {
1762 data_valid = 0; /* signal that impl->last is invalid */
1763 }
1764 }
1765
1766 return data_valid;
1767
1768 }
1769
next_weekday_by_week(icalrecur_iterator * impl)1770 static int next_weekday_by_week(icalrecur_iterator* impl)
1771 {
1772
1773 int end_of_data = 0;
1774 int start_of_week, dow;
1775 struct icaltimetype next;
1776
1777 if (next_hour(impl) == 0){
1778 return 0;
1779 }
1780
1781 if(!has_by_data(impl,BY_DAY)){
1782 return 1;
1783 }
1784
1785 /* this call to 'sort_bydayrules' assures that the occurrences for
1786 weekly recurrences will be generated in a strict linear order. */
1787 sort_bydayrules(BYDAYPTR, impl->rule.week_start);
1788
1789 /* If we get here, we need to step to tne next day */
1790
1791 for (;;) {
1792 struct icaltimetype tt = icaltime_null_time();
1793 BYDAYIDX++; /* Look at next elem in BYDAY array */
1794
1795 /* Are we at the end of the BYDAY array? */
1796 if (BYDAYPTR[BYDAYIDX]==ICAL_RECURRENCE_ARRAY_MAX){
1797 BYDAYIDX = 0; /* Reset to 0 */
1798 end_of_data = 1; /* Signal that we're at the end */
1799 }
1800
1801 /* Add the day of week offset to to the start of this week, and use
1802 that to get the next day */
1803 /* ignore position of dow ("4FR"), only use dow ("FR")*/
1804 dow = icalrecurrencetype_day_day_of_week(BYDAYPTR[BYDAYIDX]);
1805 dow -= impl->rule.week_start; /* Set Sunday to be 0 */
1806 if (dow < 0) {
1807 dow += 7;
1808 }
1809
1810 tt.year = impl->last.year;
1811 tt.day = impl->last.day;
1812 tt.month = impl->last.month;
1813
1814 start_of_week = icaltime_start_doy_week(tt, impl->rule.week_start);
1815
1816 if(dow+start_of_week <1){
1817 /* The selected date is in the previous year. */
1818 if(!end_of_data){
1819 continue;
1820 }
1821 }
1822
1823 next = icaltime_from_day_of_year(start_of_week + dow,impl->last.year);
1824
1825 impl->last.day = next.day;
1826 impl->last.month = next.month;
1827 impl->last.year = next.year;
1828
1829 return end_of_data;
1830 }
1831
1832 }
1833
next_week(icalrecur_iterator * impl)1834 static int next_week(icalrecur_iterator* impl)
1835 {
1836 int end_of_data = 0;
1837
1838 /* Increment to the next week day, if there is data at a level less than a week */
1839 if (next_weekday_by_week(impl) == 0){
1840 return 0; /* Have not reached end of week yet */
1841 }
1842
1843 /* If we get here, we have incremented through the entire week, and
1844 can increment to the next week */
1845
1846 if( has_by_data(impl,BY_WEEK_NO)){
1847 /*FREQ=WEEKLY;BYWEEK=20*/
1848 /* Use the Week Number byrule data */
1849 int week_no;
1850 struct icaltimetype t;
1851
1852 impl->by_indices[BY_WEEK_NO]++;
1853
1854 if (impl->by_ptrs[BY_WEEK_NO][impl->by_indices[BY_WEEK_NO]]
1855 ==ICAL_RECURRENCE_ARRAY_MAX){
1856 impl->by_indices[BY_WEEK_NO] = 0;
1857
1858 end_of_data = 1;
1859 }
1860
1861 t = impl->last;
1862 t.month=1; /* HACK, should be setting to the date of the first week of year*/
1863 t.day=1;
1864
1865 week_no = impl->by_ptrs[BY_WEEK_NO][impl->by_indices[BY_WEEK_NO]];
1866
1867 impl->last.day += week_no*7;
1868
1869 impl->last = icaltime_normalize(impl->last);
1870
1871 } else {
1872 /* Jump to the next week */
1873 increment_monthday(impl,7*impl->rule.interval);
1874 }
1875
1876 if( has_by_data(impl,BY_WEEK_NO) && end_of_data){
1877 increment_year(impl,1);
1878 }
1879
1880 return end_of_data;
1881
1882 }
1883
1884 /** Expand the BYDAY rule part and return a pointer to a newly allocated list of days. */
expand_by_day(icalrecur_iterator * impl,int year)1885 static pvl_list expand_by_day(icalrecur_iterator* impl, int year)
1886 {
1887 /* Try to calculate each of the occurrences. */
1888 int i;
1889 pvl_list days_list = pvl_newlist();
1890
1891 int start_dow, end_dow, end_year_day;
1892 struct icaltimetype tmp = impl->last;
1893
1894 tmp.year= year;
1895 tmp.month = 1;
1896 tmp.day = 1;
1897 tmp.is_date = 1;
1898
1899 /* Find the day that 1st Jan falls on, 1 (Sun) to 7 (Sat). */
1900 start_dow = icaltime_day_of_week(tmp);
1901
1902 /* Get the last day of the year*/
1903 tmp.year= year;
1904 tmp.month = 12;
1905 tmp.day = 31;
1906 tmp.is_date = 1;
1907
1908 end_dow = icaltime_day_of_week(tmp);
1909 end_year_day = icaltime_day_of_year(tmp);
1910
1911 for(i = 0; BYDAYPTR[i] != ICAL_RECURRENCE_ARRAY_MAX; i++){
1912 /* This is 1 (Sun) to 7 (Sat). */
1913 int dow =
1914 icalrecurrencetype_day_day_of_week(BYDAYPTR[i]);
1915 int pos = icalrecurrencetype_day_position(BYDAYPTR[i]);
1916
1917 if(pos == 0){
1918 /* The day was specified without a position -- it is just
1919 a bare day of the week ( BYDAY=SU) so add all of the
1920 days of the year with this day-of-week*/
1921 int doy, tmp_start_doy;
1922
1923 tmp_start_doy = ((dow + 7 - start_dow) % 7) + 1;
1924
1925 for (doy = tmp_start_doy; doy <= end_year_day; doy += 7)
1926 pvl_push(days_list,(void*)(ptrdiff_t)doy);
1927
1928 } else if ( pos > 0) {
1929 int first;
1930 /* First occurrence of dow in year */
1931 if( dow >= start_dow) {
1932 first = dow - start_dow + 1;
1933 } else {
1934 first = dow - start_dow + 8;
1935 }
1936
1937 /* Then just multiple the position times 7 to get the pos'th day in the year */
1938 pvl_push(days_list,(void*)(ptrdiff_t)(first + (pos-1) * 7));
1939
1940 } else { /* pos < 0 */
1941 int last;
1942 pos = -pos;
1943
1944 /* last occurrence of dow in year */
1945 if( dow <= end_dow) {
1946 last = end_year_day - end_dow + dow;
1947 } else {
1948 last = end_year_day - end_dow + dow - 7;
1949 }
1950
1951 pvl_push(days_list,(void*)(ptrdiff_t)(last - (pos-1) * 7));
1952 }
1953 }
1954 return days_list;
1955 }
1956
1957 /* A compare function to be used with qsort() in order to get
1958 a sorted array of days of the year */
daysOfYear_compare(const void * a,const void * b)1959 int daysOfYear_compare(const void * a, const void * b)
1960 {
1961 return ( *(short*)a - *(short*)b );
1962 }
1963
1964 /* For INTERVAL=YEARLY, set up the days[] array in the iterator to
1965 list all of the days of the current year that are specified in this
1966 rule. */
1967
expand_year_days(icalrecur_iterator * impl,int year)1968 static int expand_year_days(icalrecur_iterator* impl, int year)
1969 {
1970 int i,j,k;
1971 int days_index=0;
1972 struct icaltimetype t;
1973 int flags;
1974
1975 t = icaltime_null_date();
1976
1977 #define HBD(x) has_by_data(impl,x)
1978
1979 memset(impl->days,ICAL_RECURRENCE_ARRAY_MAX_BYTE,sizeof(impl->days));
1980
1981 /* The flags and the following switch statement select which code
1982 to use to expand the yers days, based on which BY-rules are
1983 present. */
1984
1985 flags = (HBD(BY_DAY) ? 1<<BY_DAY : 0) +
1986 (HBD(BY_WEEK_NO) ? 1<<BY_WEEK_NO : 0) +
1987 (HBD(BY_MONTH_DAY) ? 1<<BY_MONTH_DAY : 0) +
1988 (HBD(BY_MONTH) ? 1<<BY_MONTH : 0) +
1989 (HBD(BY_YEAR_DAY) ? 1<<BY_YEAR_DAY : 0);
1990
1991
1992 /* BY_WEEK_NO together with BY_MONTH - may conflict, in this case BY_MONTH wins */
1993 if( (flags & 1<<BY_MONTH) && (flags & 1<<BY_WEEK_NO) ){
1994 int valid_weeks[ICAL_BY_WEEKNO_SIZE];
1995 int valid = 1;
1996 memset(valid_weeks, 0, sizeof(valid_weeks));
1997 t.year = year;
1998 t.is_date = 1;
1999
2000 /* calculate valid week numbers */
2001 for(j=0; impl->by_ptrs[BY_MONTH][j]!=ICAL_RECURRENCE_ARRAY_MAX; j++){
2002 int month = impl->by_ptrs[BY_MONTH][j];
2003 int first_week, last_week;
2004 t.month = month;
2005 t.day = 1;
2006 first_week = icaltime_week_number(t);
2007 t.day = icaltime_days_in_month(month,year);
2008 last_week = icaltime_week_number(t);
2009 for(j=first_week; j<last_week; j++) {
2010 valid_weeks[j] = 1;
2011 }
2012 }
2013
2014 /* check valid weeks */
2015 for(i = 0; BYWEEKPTR[i] != ICAL_RECURRENCE_ARRAY_MAX && valid; i++){
2016 int weekno = BYWEEKPTR[i];
2017 if(weekno < ICAL_BY_WEEKNO_SIZE)
2018 valid &= valid_weeks[i]; /* check if the week number is valid */
2019 else
2020 valid = 0; /* invalid week number */
2021 }
2022
2023 /* let us make the decision which rule to keep */
2024 if(valid) { /* BYWEEKNO wins */
2025 flags -= 1<<BY_MONTH;
2026 }
2027 else { /* BYMONTH vins */
2028 flags -= 1<<BY_WEEK_NO;
2029 }
2030 }
2031
2032 switch(flags) {
2033
2034 case 0: {
2035 /* FREQ=YEARLY; */
2036 t = impl->dtstart;
2037 t.year = impl->last.year;
2038
2039 impl->days[days_index++] = (short)icaltime_day_of_year(t);
2040
2041 break;
2042 }
2043 case 1<<BY_MONTH: {
2044 /* FREQ=YEARLY; BYMONTH=3,11*/
2045
2046 for(j=0;impl->by_ptrs[BY_MONTH][j]!=ICAL_RECURRENCE_ARRAY_MAX;j++){
2047 int month = impl->by_ptrs[BY_MONTH][j];
2048 int doy;
2049
2050 t = impl->dtstart;
2051 t.year = year;
2052 t.month = month;
2053 t.is_date = 1;
2054
2055 doy = icaltime_day_of_year(t);
2056
2057 impl->days[days_index++] = (short)doy;
2058
2059 }
2060 break;
2061 }
2062
2063 case 1<<BY_MONTH_DAY: {
2064 /* FREQ=YEARLY; BYMONTHDAY=1,15*/
2065 for(k=0;impl->by_ptrs[BY_MONTH_DAY][k]!=ICAL_RECURRENCE_ARRAY_MAX;k++)
2066 {
2067 int month_day = impl->by_ptrs[BY_MONTH_DAY][k];
2068 int doy;
2069
2070 t = impl->dtstart;
2071 if (month_day < 0) {
2072 int days_in_month = icaltime_days_in_month(t.month, year);
2073 month_day = days_in_month + month_day + 1;
2074 }
2075 t.day = month_day;
2076 t.year = year;
2077 t.is_date = 1;
2078
2079 doy = icaltime_day_of_year(t);
2080
2081 impl->days[days_index++] = (short)doy;
2082
2083 }
2084 break;
2085 }
2086
2087 case (1<<BY_MONTH_DAY) + (1<<BY_MONTH): {
2088 /* FREQ=YEARLY; BYMONTHDAY=1,15; BYMONTH=10 */
2089
2090 for(j=0;impl->by_ptrs[BY_MONTH][j]!=ICAL_RECURRENCE_ARRAY_MAX;j++){
2091 int month = impl->by_ptrs[BY_MONTH][j];
2092 int days_in_month = icaltime_days_in_month(month, year);
2093 for(k=0;impl->by_ptrs[BY_MONTH_DAY][k]!=ICAL_RECURRENCE_ARRAY_MAX;k++)
2094 {
2095 int month_day = impl->by_ptrs[BY_MONTH_DAY][k];
2096 int doy;
2097
2098 if (month_day < 0) {
2099 month_day = days_in_month + month_day + 1;
2100 }
2101
2102 t.day = month_day;
2103 t.month = month;
2104 t.year = year;
2105 t.is_date = 1;
2106
2107 doy = icaltime_day_of_year(t);
2108
2109 impl->days[days_index++] = (short)doy;
2110
2111 }
2112 }
2113
2114 break;
2115 }
2116
2117 case 1<<BY_WEEK_NO: {
2118 /* FREQ=YEARLY; BYWEEKNO=20,50 */
2119
2120 int dow;
2121
2122 t.day = impl->dtstart.day;
2123 t.month = impl->dtstart.month;
2124 t.year = year;
2125 t.is_date = 1;
2126
2127 dow = icaltime_day_of_week(t);
2128 /* HACK Not finished */
2129
2130 icalerror_set_errno(ICAL_UNIMPLEMENTED_ERROR);
2131
2132 break;
2133 }
2134
2135 case (1<<BY_WEEK_NO) + (1<<BY_MONTH_DAY): {
2136 /*FREQ=YEARLY; WEEKNO=20,50; BYMONTH= 6,11 */
2137 icalerror_set_errno(ICAL_UNIMPLEMENTED_ERROR);
2138 break;
2139 }
2140
2141 case 1<<BY_DAY: {
2142 /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR*/
2143 pvl_elem i;
2144 pvl_list days = expand_by_day(impl,year);
2145
2146
2147 for(i=pvl_head(days);i!=0;i=pvl_next(i)){
2148 short day = (short)(intptr_t)pvl_data(i);
2149 impl->days[days_index++] = day;
2150 }
2151
2152 pvl_free(days);
2153
2154 break;
2155 }
2156
2157 case (1<<BY_DAY)+(1<<BY_MONTH): {
2158 /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR; BYMONTH = 12*/
2159
2160
2161 for(j=0;impl->by_ptrs[BY_MONTH][j]!=ICAL_RECURRENCE_ARRAY_MAX;j++){
2162 int month = impl->by_ptrs[BY_MONTH][j];
2163 int days_in_month = icaltime_days_in_month(month,year);
2164 int first_dow, last_dow, doy_offset;
2165
2166 t.year = year;
2167 t.month = month;
2168 t.day = 1;
2169 t.is_date = 1;
2170
2171 first_dow = icaltime_day_of_week(t);
2172
2173 /* This holds the day offset used to calculate the day of the year
2174 from the month day. Just add the month day to this. */
2175 doy_offset = icaltime_day_of_year(t) - 1;
2176
2177 t.day = days_in_month;
2178 last_dow = icaltime_day_of_week(t);
2179
2180 if(has_by_data(impl,BY_SET_POS)) {
2181 /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR; BYMONTH = 12; BYSETPOS=1*/
2182 int day;
2183 int set_pos_counter = 0;
2184 int set_pos_total = 0;
2185 int by_month_day[ICAL_BY_MONTHDAY_SIZE];
2186 for(day = 1; day <= days_in_month; day++){
2187 t.day = day;
2188 if(is_day_in_byday(impl,t))
2189 by_month_day[set_pos_total++] = day;
2190 }
2191 for(set_pos_counter = 0; set_pos_counter < set_pos_total; set_pos_counter++){
2192 if(check_set_position(impl, set_pos_counter+1) ||
2193 check_set_position(impl, set_pos_counter-set_pos_total))
2194 impl->days[days_index++] = doy_offset + by_month_day[set_pos_counter];
2195 }
2196 }
2197 else for(k=0;impl->by_ptrs[BY_DAY][k]!=ICAL_RECURRENCE_ARRAY_MAX;k++){
2198 short day_coded = impl->by_ptrs[BY_DAY][k];
2199 enum icalrecurrencetype_weekday dow =
2200 icalrecurrencetype_day_day_of_week(day_coded);
2201 int pos = icalrecurrencetype_day_position(day_coded);
2202 int first_matching_day, last_matching_day, day, month_day;
2203
2204 /* Calculate the first day in the month with the given weekday,
2205 and the last day. */
2206 first_matching_day = ((dow + 7 - first_dow) % 7) + 1;
2207 last_matching_day = days_in_month - ((last_dow + 7 - dow) % 7);
2208
2209 if (pos == 0) {
2210 /* Add all of instances of the weekday within the month. */
2211 for (day = first_matching_day; day <= days_in_month; day += 7)
2212 impl->days[days_index++] = (short)(doy_offset + day);
2213
2214 } else if (pos > 0) {
2215 /* Add the nth instance of the weekday within the month. */
2216 month_day = first_matching_day + (pos - 1) * 7;
2217
2218 if (month_day <= days_in_month)
2219 impl->days[days_index++] = (short)(doy_offset + month_day);
2220
2221 } else {
2222 /* Add the -nth instance of the weekday within the month.*/
2223 month_day = last_matching_day + (pos + 1) * 7;
2224
2225 if (month_day > 0)
2226 impl->days[days_index++] = (short)(doy_offset + month_day);
2227 }
2228 }
2229 }
2230 /* Sort the days according to the Bymonthday order (1,2,3,...). */
2231 qsort(impl->days, days_index, sizeof(short), daysOfYear_compare);
2232 break;
2233 }
2234
2235 case (1<<BY_DAY) + (1<<BY_MONTH_DAY) : {
2236 /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR; BYMONTHDAY=1,15*/
2237
2238 pvl_elem itr;
2239 pvl_list days = expand_by_day(impl,year);
2240
2241 for(itr=pvl_head(days);itr!=0;itr=pvl_next(itr)){
2242 short day = (short)(intptr_t)pvl_data(itr);
2243 struct icaltimetype tt;
2244
2245 tt = icaltime_from_day_of_year(day,year);
2246
2247 for(j = 0; BYMDPTR[j]!=ICAL_RECURRENCE_ARRAY_MAX; j++){
2248 int mday = BYMDPTR[j];
2249
2250 if(tt.day == mday){
2251 impl->days[days_index++] = day;
2252 }
2253 }
2254
2255 }
2256
2257 pvl_free(days);
2258
2259 break;
2260 }
2261
2262 case (1<<BY_DAY) + (1<<BY_MONTH_DAY) + (1<<BY_MONTH): {
2263 /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR; BYMONTHDAY=10; MYMONTH=6,11*/
2264
2265 pvl_elem itr;
2266 pvl_list days = expand_by_day(impl,year);
2267
2268 for(itr=pvl_head(days);itr!=0;itr=pvl_next(itr)){
2269 short day = (short)(intptr_t)pvl_data(itr);
2270 struct icaltimetype tt;
2271 int i;
2272
2273 tt = icaltime_from_day_of_year(day,year);
2274
2275 for(i = 0; BYMONPTR[i] != ICAL_RECURRENCE_ARRAY_MAX; i++){
2276 for(j = 0; BYMDPTR[j]!=ICAL_RECURRENCE_ARRAY_MAX; j++){
2277 int mday = BYMDPTR[j];
2278 int month = BYMONPTR[i];
2279
2280 if(tt.month == month && tt.day == mday){
2281 impl->days[days_index++] = day;
2282 }
2283 }
2284 }
2285
2286 }
2287
2288 pvl_free(days);
2289
2290 break;
2291
2292 }
2293
2294 case (1<<BY_DAY) + (1<<BY_WEEK_NO) : {
2295 /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR; WEEKNO=20,50*/
2296
2297 pvl_elem itr;
2298 pvl_list days = expand_by_day(impl,year);
2299
2300 for(itr=pvl_head(days);itr!=0;itr=pvl_next(itr)){
2301 short day = (short)(intptr_t)pvl_data(itr);
2302 struct icaltimetype tt;
2303 int i;
2304
2305 tt = icaltime_from_day_of_year(day,year);
2306
2307 for(i = 0; BYWEEKPTR[i] != ICAL_RECURRENCE_ARRAY_MAX; i++){
2308 int weekno = BYWEEKPTR[i];
2309 int this_weekno = icaltime_week_number(tt);
2310 if(weekno== this_weekno){
2311 impl->days[days_index++] = day;
2312 }
2313 }
2314
2315 }
2316
2317 pvl_free(days);
2318 break;
2319 }
2320
2321 case (1<<BY_DAY) + (1<<BY_WEEK_NO) + (1<<BY_MONTH_DAY): {
2322 /*FREQ=YEARLY; BYDAY=TH,20MO,-10FR; WEEKNO=20,50; BYMONTHDAY=1,15*/
2323 icalerror_set_errno(ICAL_UNIMPLEMENTED_ERROR);
2324 break;
2325 }
2326
2327 case 1<<BY_YEAR_DAY: {
2328 for(j=0;impl->by_ptrs[BY_YEAR_DAY][j]!=ICAL_RECURRENCE_ARRAY_MAX;j++){
2329 impl->days[days_index++] = impl->by_ptrs[BY_YEAR_DAY][j];
2330 }
2331 break;
2332 }
2333
2334 default: {
2335 icalerror_set_errno(ICAL_UNIMPLEMENTED_ERROR);
2336 break;
2337 }
2338
2339 }
2340
2341 return 0;
2342 }
2343
2344
next_year(icalrecur_iterator * impl)2345 static int next_year(icalrecur_iterator* impl)
2346 {
2347 struct icaltimetype next;
2348
2349 if (next_hour(impl) == 0){
2350 return 0;
2351 }
2352
2353 if (impl->days[++impl->days_index] == ICAL_RECURRENCE_ARRAY_MAX){
2354 impl->days_index = 0;
2355
2356 for (;;) {
2357 increment_year(impl,impl->rule.interval);
2358 expand_year_days(impl,impl->last.year);
2359 if (impl->days[0] != ICAL_RECURRENCE_ARRAY_MAX)
2360 break;
2361 }
2362 }
2363
2364 next = icaltime_from_day_of_year(impl->days[impl->days_index], impl->last.year);
2365
2366 impl->last.day = next.day;
2367 impl->last.month = next.month;
2368
2369 return 1;
2370 }
2371
icalrecur_check_rulepart(icalrecur_iterator * impl,int v,enum byrule byrule)2372 int icalrecur_check_rulepart(icalrecur_iterator* impl,
2373 int v, enum byrule byrule)
2374 {
2375 int itr;
2376
2377 if(impl->by_ptrs[byrule][0]!=ICAL_RECURRENCE_ARRAY_MAX){
2378 for(itr=0; impl->by_ptrs[byrule][itr]!=ICAL_RECURRENCE_ARRAY_MAX;itr++){
2379 if(impl->by_ptrs[byrule][itr] == v){
2380 return 1;
2381 }
2382 }
2383 }
2384
2385 return 0;
2386 }
2387
check_contract_restriction(icalrecur_iterator * impl,enum byrule byrule,int v)2388 static int check_contract_restriction(icalrecur_iterator* impl,
2389 enum byrule byrule, int v)
2390 {
2391 int pass = 0;
2392 int itr;
2393 icalrecurrencetype_frequency freq = impl->rule.freq;
2394
2395 if(impl->by_ptrs[byrule][0]!=ICAL_RECURRENCE_ARRAY_MAX &&
2396 expand_map[freq].map[byrule] == CONTRACT){
2397 for(itr=0; impl->by_ptrs[byrule][itr]!=ICAL_RECURRENCE_ARRAY_MAX;itr++){
2398 if(impl->by_ptrs[byrule][itr] == v){
2399 pass=1;
2400 break;
2401 }
2402 }
2403
2404 return pass;
2405 } else {
2406 /* This is not a contracting byrule, or it has no data, so the
2407 test passes*/
2408 return 1;
2409 }
2410 }
2411
2412
check_contracting_rules(icalrecur_iterator * impl)2413 static int check_contracting_rules(icalrecur_iterator* impl)
2414 {
2415
2416 int day_of_week = icaltime_day_of_week(impl->last);
2417 int week_no = icaltime_week_number(impl->last);
2418 int year_day = icaltime_day_of_year(impl->last);
2419
2420 if (
2421 check_contract_restriction(impl,BY_SECOND, impl->last.second) &&
2422 check_contract_restriction(impl,BY_MINUTE, impl->last.minute) &&
2423 check_contract_restriction(impl,BY_HOUR, impl->last.hour) &&
2424 check_contract_restriction(impl,BY_DAY, day_of_week) &&
2425 check_contract_restriction(impl,BY_WEEK_NO, week_no) &&
2426 check_contract_restriction(impl,BY_MONTH_DAY, impl->last.day) &&
2427 check_contract_restriction(impl,BY_MONTH, impl->last.month) &&
2428 check_contract_restriction(impl,BY_YEAR_DAY, year_day) )
2429 {
2430
2431 return 1;
2432 } else {
2433 return 0;
2434 }
2435 }
2436
icalrecur_iterator_next(icalrecur_iterator * impl)2437 struct icaltimetype icalrecur_iterator_next(icalrecur_iterator *impl)
2438 {
2439 int valid = 1;
2440
2441 if( !impl || (impl->rule.count!=0 &&impl->occurrence_no >= impl->rule.count) ||
2442 (!icaltime_is_null_time(impl->rule.until) &&
2443 icaltime_compare(impl->last,impl->rule.until) > 0)) {
2444 return icaltime_null_time();
2445 }
2446
2447 if(impl->occurrence_no == 0
2448 && icaltime_compare(impl->last,impl->dtstart) >= 0){
2449
2450 impl->occurrence_no++;
2451 return impl->last;
2452 }
2453
2454 do {
2455 valid = 1;
2456 switch(impl->rule.freq){
2457
2458 case ICAL_SECONDLY_RECURRENCE: {
2459 next_second(impl);
2460 break;
2461 }
2462 case ICAL_MINUTELY_RECURRENCE: {
2463 next_minute(impl);
2464 break;
2465 }
2466 case ICAL_HOURLY_RECURRENCE: {
2467 next_hour(impl);
2468 break;
2469 }
2470 case ICAL_DAILY_RECURRENCE: {
2471 next_day(impl);
2472 break;
2473 }
2474 case ICAL_WEEKLY_RECURRENCE: {
2475 next_week(impl);
2476 break;
2477 }
2478 case ICAL_MONTHLY_RECURRENCE: {
2479 valid = next_month(impl);
2480 break;
2481 }
2482 case ICAL_YEARLY_RECURRENCE:{
2483 next_year(impl);
2484 break;
2485 }
2486 default:{
2487 icalerror_set_errno(ICAL_MALFORMEDDATA_ERROR);
2488 return icaltime_null_time();
2489 }
2490 }
2491
2492 } while(!check_contracting_rules(impl)
2493 || icaltime_compare(impl->last,impl->dtstart) < 0
2494 || valid == 0);
2495
2496
2497 /* Ignore null times and times that are after the until time */
2498 if( !icaltime_is_null_time(impl->rule.until) &&
2499 icaltime_compare(impl->last,impl->rule.until) > 0 ) {
2500 return icaltime_null_time();
2501 }
2502
2503 impl->occurrence_no++;
2504
2505 return impl->last;
2506 }
2507
2508
2509 /************************** Type Routines **********************/
2510
2511
icalrecurrencetype_clear(struct icalrecurrencetype * recur)2512 void icalrecurrencetype_clear(struct icalrecurrencetype *recur)
2513 {
2514 memset(recur,ICAL_RECURRENCE_ARRAY_MAX_BYTE,
2515 sizeof(struct icalrecurrencetype));
2516
2517 recur->week_start = ICAL_MONDAY_WEEKDAY;
2518 recur->freq = ICAL_NO_RECURRENCE;
2519 recur->interval = 1;
2520 memset(&(recur->until),0,sizeof(struct icaltimetype));
2521 recur->count = 0;
2522 }
2523
2524 /** The 'day' element of icalrecurrencetype_weekday is encoded to
2525 * allow representation of both the day of the week ( Monday, Tueday),
2526 * but also the Nth day of the week ( First tuesday of the month, last
2527 * thursday of the year) These routines decode the day values.
2528 *
2529 * The day's position in the period ( Nth-ness) and the numerical
2530 * value of the day are encoded together as: pos*7 + dow
2531 *
2532 * A position of 0 means 'any' or 'every'
2533 */
2534
icalrecurrencetype_day_day_of_week(short day)2535 enum icalrecurrencetype_weekday icalrecurrencetype_day_day_of_week(short day)
2536 {
2537 return abs(day)%8;
2538 }
2539
icalrecurrencetype_day_position(short day)2540 int icalrecurrencetype_day_position(short day)
2541 {
2542 int wd, pos;
2543
2544 wd = icalrecurrencetype_day_day_of_week(day);
2545
2546 pos = (abs(day)-wd)/8 * ((day<0)?-1:1);
2547
2548
2549 return pos;
2550 }
2551
2552
2553 /****************** Enumeration Routines ******************/
2554
2555 static struct {icalrecurrencetype_weekday wd; const char * str; }
2556 wd_map[] = {
2557 {ICAL_SUNDAY_WEEKDAY,"SU"},
2558 {ICAL_MONDAY_WEEKDAY,"MO"},
2559 {ICAL_TUESDAY_WEEKDAY,"TU"},
2560 {ICAL_WEDNESDAY_WEEKDAY,"WE"},
2561 {ICAL_THURSDAY_WEEKDAY,"TH"},
2562 {ICAL_FRIDAY_WEEKDAY,"FR"},
2563 {ICAL_SATURDAY_WEEKDAY,"SA"},
2564 {ICAL_NO_WEEKDAY,0}
2565 };
2566
icalrecur_weekday_to_string(icalrecurrencetype_weekday kind)2567 const char* icalrecur_weekday_to_string(icalrecurrencetype_weekday kind)
2568 {
2569 int i;
2570
2571 for (i=0; wd_map[i].wd != ICAL_NO_WEEKDAY; i++) {
2572 if ( wd_map[i].wd == kind) {
2573 return wd_map[i].str;
2574 }
2575 }
2576
2577 return 0;
2578 }
2579
icalrecur_string_to_weekday(const char * str)2580 icalrecurrencetype_weekday icalrecur_string_to_weekday(const char* str)
2581 {
2582 int i;
2583
2584 for (i=0; wd_map[i].wd != ICAL_NO_WEEKDAY; i++) {
2585 if ( strcasecmp(str,wd_map[i].str) == 0){
2586 return wd_map[i].wd;
2587 }
2588 }
2589
2590 return ICAL_NO_WEEKDAY;
2591 }
2592
2593
2594
2595 static struct {
2596 icalrecurrencetype_frequency kind;
2597 const char* str;
2598 } freq_map[] = {
2599 {ICAL_SECONDLY_RECURRENCE,"SECONDLY"},
2600 {ICAL_MINUTELY_RECURRENCE,"MINUTELY"},
2601 {ICAL_HOURLY_RECURRENCE,"HOURLY"},
2602 {ICAL_DAILY_RECURRENCE,"DAILY"},
2603 {ICAL_WEEKLY_RECURRENCE,"WEEKLY"},
2604 {ICAL_MONTHLY_RECURRENCE,"MONTHLY"},
2605 {ICAL_YEARLY_RECURRENCE,"YEARLY"},
2606 {ICAL_NO_RECURRENCE,0}
2607 };
2608
icalrecur_freq_to_string(icalrecurrencetype_frequency kind)2609 const char* icalrecur_freq_to_string(icalrecurrencetype_frequency kind)
2610 {
2611 int i;
2612
2613 for (i=0; freq_map[i].kind != ICAL_NO_RECURRENCE ; i++) {
2614 if ( freq_map[i].kind == kind ) {
2615 return freq_map[i].str;
2616 }
2617 }
2618 return 0;
2619 }
2620
icalrecur_string_to_freq(const char * str)2621 icalrecurrencetype_frequency icalrecur_string_to_freq(const char* str)
2622 {
2623 int i;
2624
2625 for (i=0; freq_map[i].kind != ICAL_NO_RECURRENCE ; i++) {
2626 if ( strcasecmp(str,freq_map[i].str) == 0){
2627 return freq_map[i].kind;
2628 }
2629 }
2630 return ICAL_NO_RECURRENCE;
2631 }
2632
2633 /** Fill an array with the 'count' number of occurrences generated by
2634 * the rrule. Note that the times are returned in UTC, but the times
2635 * are calculated in local time. YOu will have to convert the results
2636 * back into local time before using them.
2637 */
2638
icalrecur_expand_recurrence(char * rule,time_t start,int count,time_t * array)2639 int icalrecur_expand_recurrence(char* rule, time_t start,
2640 int count, time_t* array)
2641 {
2642 struct icalrecurrencetype recur;
2643 icalrecur_iterator* ritr;
2644 time_t tt;
2645 struct icaltimetype icstart, next;
2646 int i = 0;
2647
2648 memset(array, 0, count*sizeof(time_t));
2649
2650 icstart = icaltime_from_timet_with_zone(start,0,0);
2651
2652 recur = icalrecurrencetype_from_string(rule);
2653 ritr = icalrecur_iterator_new(recur,icstart);
2654 if(ritr) {
2655 for(next = icalrecur_iterator_next(ritr);
2656 !icaltime_is_null_time(next) && i < count;
2657 next = icalrecur_iterator_next(ritr)){
2658
2659 tt = icaltime_as_timet(next);
2660
2661 if (tt >= start ){
2662 array[i++] = tt;
2663 }
2664 }
2665 icalrecur_iterator_free(ritr);
2666 }
2667
2668
2669 return 1;
2670 }
2671