src/libical/icalrecur.c

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