1 /* //device/content/providers/pim/RecurrenceProcessor.java 2 ** 3 ** Copyright 2006, The Android Open Source Project 4 ** 5 ** Licensed under the Apache License, Version 2.0 (the "License"); 6 ** you may not use this file except in compliance with the License. 7 ** You may obtain a copy of the License at 8 ** 9 ** http://www.apache.org/licenses/LICENSE-2.0 10 ** 11 ** Unless required by applicable law or agreed to in writing, software 12 ** distributed under the License is distributed on an "AS IS" BASIS, 13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 ** See the License for the specific language governing permissions and 15 ** limitations under the License. 16 */ 17 18 package com.android.calendarcommon2; 19 20 import android.text.format.Time; 21 import android.util.Log; 22 23 import java.util.TreeSet; 24 25 public class RecurrenceProcessor 26 { 27 // these are created once and reused. 28 private Time mIterator = new Time(Time.TIMEZONE_UTC); 29 private Time mUntil = new Time(Time.TIMEZONE_UTC); 30 private StringBuilder mStringBuilder = new StringBuilder(); 31 private Time mGenerated = new Time(Time.TIMEZONE_UTC); 32 private DaySet mDays = new DaySet(false); 33 // Give up after this many loops. This is roughly 1 second of expansion. 34 private static final int MAX_ALLOWED_ITERATIONS = 2000; 35 36 public RecurrenceProcessor() 37 { 38 } 39 40 private static final String TAG = "RecurrenceProcessor"; 41 42 private static final boolean SPEW = false; 43 44 /** 45 * Returns the time (millis since epoch) of the last occurrence, 46 * or -1 if the event repeats forever. If there are no occurrences 47 * (because the exrule or exdates cancel all the occurrences) and the 48 * event does not repeat forever, then 0 is returned. 49 * 50 * This computes a conservative estimate of the last occurrence. That is, 51 * the time of the actual last occurrence might be earlier than the time 52 * returned by this method. 53 * 54 * @param dtstart the time of the first occurrence 55 * @param recur the recurrence 56 * @return an estimate of the time (in UTC milliseconds) of the last 57 * occurrence, which may be greater than the actual last occurrence 58 * @throws DateException 59 */ 60 public long getLastOccurence(Time dtstart, 61 RecurrenceSet recur) throws DateException { 62 return getLastOccurence(dtstart, null /* no limit */, recur); 63 } 64 65 /** 66 * Returns the time (millis since epoch) of the last occurrence, 67 * or -1 if the event repeats forever. If there are no occurrences 68 * (because the exrule or exdates cancel all the occurrences) and the 69 * event does not repeat forever, then 0 is returned. 70 * 71 * This computes a conservative estimate of the last occurrence. That is, 72 * the time of the actual last occurrence might be earlier than the time 73 * returned by this method. 74 * 75 * @param dtstart the time of the first occurrence 76 * @param maxtime the max possible time of the last occurrence. null means no limit 77 * @param recur the recurrence 78 * @return an estimate of the time (in UTC milliseconds) of the last 79 * occurrence, which may be greater than the actual last occurrence 80 * @throws DateException 81 */ 82 public long getLastOccurence(Time dtstart, Time maxtime, 83 RecurrenceSet recur) throws DateException { 84 long lastTime = -1; 85 boolean hasCount = false; 86 87 // first see if there are any "until"s specified. if so, use the latest 88 // until / rdate. 89 if (recur.rrules != null) { 90 for (EventRecurrence rrule : recur.rrules) { 91 if (rrule.count != 0) { 92 hasCount = true; 93 } else if (rrule.until != null) { 94 // according to RFC 2445, until must be in UTC. 95 mIterator.parse(rrule.until); 96 long untilTime = mIterator.toMillis(false /* use isDst */); 97 if (untilTime > lastTime) { 98 lastTime = untilTime; 99 } 100 } 101 } 102 if (lastTime != -1 && recur.rdates != null) { 103 for (long dt : recur.rdates) { 104 if (dt > lastTime) { 105 lastTime = dt; 106 } 107 } 108 } 109 110 // If there were only "until"s and no "count"s, then return the 111 // last "until" date or "rdate". 112 if (lastTime != -1 && !hasCount) { 113 return lastTime; 114 } 115 } else if (recur.rdates != null && 116 recur.exrules == null && recur.exdates == null) { 117 // if there are only rdates, we can just pick the last one. 118 for (long dt : recur.rdates) { 119 if (dt > lastTime) { 120 lastTime = dt; 121 } 122 } 123 return lastTime; 124 } 125 126 // Expand the complete recurrence if there were any counts specified, 127 // or if there were rdates specified. 128 if (hasCount || recur.rdates != null || maxtime != null) { 129 // The expansion might not contain any dates if the exrule or 130 // exdates cancel all the generated dates. 131 long[] dates = expand(dtstart, recur, 132 dtstart.toMillis(false /* use isDst */) /* range start */, 133 (maxtime != null) ? 134 maxtime.toMillis(false /* use isDst */) : -1 /* range end */); 135 136 // The expansion might not contain any dates if exrule or exdates 137 // cancel all the generated dates. 138 if (dates.length == 0) { 139 return 0; 140 } 141 return dates[dates.length - 1]; 142 } 143 return -1; 144 } 145 146 /** 147 * a -- list of values 148 * N -- number of values to use in a 149 * v -- value to check for 150 */ 151 private static boolean listContains(int[] a, int N, int v) 152 { 153 for (int i=0; i<N; i++) { 154 if (a[i] == v) { 155 return true; 156 } 157 } 158 return false; 159 } 160 161 /** 162 * a -- list of values 163 * N -- number of values to use in a 164 * v -- value to check for 165 * max -- if a value in a is negative, add that negative value 166 * to max and compare that instead; this is how we deal with 167 * negative numbers being offsets from the end value 168 */ 169 private static boolean listContains(int[] a, int N, int v, int max) 170 { 171 for (int i=0; i<N; i++) { 172 int w = a[i]; 173 if (w > 0) { 174 if (w == v) { 175 return true; 176 } 177 } else { 178 max += w; // w is negative 179 if (max == v) { 180 return true; 181 } 182 } 183 } 184 return false; 185 } 186 187 /** 188 * Filter out the ones for events whose BYxxx rule is for 189 * a period greater than or equal to the period of the FREQ. 190 * 191 * Returns 0 if the event should not be filtered out 192 * Returns something else (a rule number which is useful for debugging) 193 * if the event should not be returned 194 */ 195 private static int filter(EventRecurrence r, Time iterator) 196 { 197 boolean found; 198 int freq = r.freq; 199 200 if (EventRecurrence.MONTHLY >= freq) { 201 // BYMONTH 202 if (r.bymonthCount > 0) { 203 found = listContains(r.bymonth, r.bymonthCount, 204 iterator.month + 1); 205 if (!found) { 206 return 1; 207 } 208 } 209 } 210 if (EventRecurrence.WEEKLY >= freq) { 211 // BYWEEK -- this is just a guess. I wonder how many events 212 // acutally use BYWEEKNO. 213 if (r.byweeknoCount > 0) { 214 found = listContains(r.byweekno, r.byweeknoCount, 215 iterator.getWeekNumber(), 216 iterator.getActualMaximum(Time.WEEK_NUM)); 217 if (!found) { 218 return 2; 219 } 220 } 221 } 222 if (EventRecurrence.DAILY >= freq) { 223 // BYYEARDAY 224 if (r.byyeardayCount > 0) { 225 found = listContains(r.byyearday, r.byyeardayCount, 226 iterator.yearDay, iterator.getActualMaximum(Time.YEAR_DAY)); 227 if (!found) { 228 return 3; 229 } 230 } 231 // BYMONTHDAY 232 if (r.bymonthdayCount > 0 ) { 233 found = listContains(r.bymonthday, r.bymonthdayCount, 234 iterator.monthDay, 235 iterator.getActualMaximum(Time.MONTH_DAY)); 236 if (!found) { 237 return 4; 238 } 239 } 240 // BYDAY -- when filtering, we ignore the number field, because it 241 // only is meaningful when creating more events. 242 byday: 243 if (r.bydayCount > 0) { 244 int a[] = r.byday; 245 int N = r.bydayCount; 246 int v = EventRecurrence.timeDay2Day(iterator.weekDay); 247 for (int i=0; i<N; i++) { 248 if (a[i] == v) { 249 break byday; 250 } 251 } 252 return 5; 253 } 254 } 255 if (EventRecurrence.HOURLY >= freq) { 256 // BYHOUR 257 found = listContains(r.byhour, r.byhourCount, 258 iterator.hour, 259 iterator.getActualMaximum(Time.HOUR)); 260 if (!found) { 261 return 6; 262 } 263 } 264 if (EventRecurrence.MINUTELY >= freq) { 265 // BYMINUTE 266 found = listContains(r.byminute, r.byminuteCount, 267 iterator.minute, 268 iterator.getActualMaximum(Time.MINUTE)); 269 if (!found) { 270 return 7; 271 } 272 } 273 if (EventRecurrence.SECONDLY >= freq) { 274 // BYSECOND 275 found = listContains(r.bysecond, r.bysecondCount, 276 iterator.second, 277 iterator.getActualMaximum(Time.SECOND)); 278 if (!found) { 279 return 8; 280 } 281 } 282 283 if (r.bysetposCount > 0) { 284 bysetpos: 285 // BYSETPOS - we only handle rules like FREQ=MONTHLY;BYDAY=MO,TU,WE,TH,FR;BYSETPOS=-1 286 if (freq == EventRecurrence.MONTHLY && r.bydayCount > 0) { 287 // Check for stuff like BYDAY=1TU 288 for (int i = r.bydayCount - 1; i >= 0; i--) { 289 if (r.bydayNum[i] != 0) { 290 if (Log.isLoggable(TAG, Log.VERBOSE)) { 291 Log.v(TAG, "BYSETPOS not supported with these rules: " + r); 292 } 293 break bysetpos; 294 } 295 } 296 if (!filterMonthlySetPos(r, iterator)) { 297 // Not allowed, filter it out. 298 return 9; 299 } 300 } else { 301 if (Log.isLoggable(TAG, Log.VERBOSE)) { 302 Log.v(TAG, "BYSETPOS not supported with these rules: " + r); 303 } 304 } 305 // BYSETPOS was defined but we don't know how to handle it. Do no filtering based 306 // on it. 307 } 308 309 // if we got to here, we didn't filter it out 310 return 0; 311 } 312 313 /** 314 * Filters out instances that don't match the BYSETPOS clause of a monthly recurrence rule. 315 * This is an awkward and inefficient way to go about it. 316 * 317 * @returns true if this instance should be kept 318 */ 319 private static boolean filterMonthlySetPos(EventRecurrence r, Time instance) { 320 /* 321 * Compute the day of the week for the first day of the month. "instance" has a 322 * day number and a DotW, so we compute the DotW of the 1st from that. Note DotW 323 * is 0-6, where 0=SUNDAY. 324 * 325 * The basic calculation is to take the instance's "day of the week" number, subtract 326 * (day of the month - 1) mod 7, and then make sure it's positive. We can simplify 327 * that with some algebra. 328 */ 329 int dotw = (instance.weekDay - instance.monthDay + 36) % 7; 330 331 /* 332 * The byday[] values are specified as bits, so we can just OR them all 333 * together. 334 */ 335 int bydayMask = 0; 336 for (int i = 0; i < r.bydayCount; i++) { 337 bydayMask |= r.byday[i]; 338 } 339 340 /* 341 * Generate a set according to the BYDAY rules. For each day of the month, determine 342 * if its day of the week is included. If so, append it to the day set. 343 */ 344 int maxDay = instance.getActualMaximum(Time.MONTH_DAY); 345 int daySet[] = new int[maxDay]; 346 int daySetLength = 0; 347 348 for (int md = 1; md <= maxDay; md++) { 349 // For each month day, see if it's part of the set. (This makes some assumptions 350 // about the exact form of the DotW constants.) 351 int dayBit = EventRecurrence.SU << dotw; 352 if ((bydayMask & dayBit) != 0) { 353 daySet[daySetLength++] = md; 354 } 355 356 dotw++; 357 if (dotw == 7) 358 dotw = 0; 359 } 360 361 /* 362 * Now walk through the BYSETPOS list and see if the instance is equal to any of the 363 * specified daySet entries. 364 */ 365 for (int i = r.bysetposCount - 1; i >= 0; i--) { 366 int index = r.bysetpos[i]; 367 if (index > 0) { 368 if (index > daySetLength) { 369 continue; // out of range 370 } 371 if (daySet[index-1] == instance.monthDay) { 372 return true; 373 } 374 } else if (index < 0) { 375 if (daySetLength + index < 0) { 376 continue; // out of range 377 } 378 if (daySet[daySetLength + index] == instance.monthDay) { 379 return true; 380 } 381 } else { 382 // should have been caught by parser 383 throw new RuntimeException("invalid bysetpos value"); 384 } 385 } 386 387 return false; 388 } 389 390 391 private static final int USE_ITERATOR = 0; 392 private static final int USE_BYLIST = 1; 393 394 /** 395 * Return whether we should make this list from the BYxxx list or 396 * from the component of the iterator. 397 */ 398 int generateByList(int count, int freq, int byFreq) 399 { 400 if (byFreq >= freq) { 401 return USE_ITERATOR; 402 } else { 403 if (count == 0) { 404 return USE_ITERATOR; 405 } else { 406 return USE_BYLIST; 407 } 408 } 409 } 410 411 private static boolean useBYX(int freq, int freqConstant, int count) 412 { 413 return freq > freqConstant && count > 0; 414 } 415 416 public static class DaySet 417 { 418 public DaySet(boolean zulu) 419 { 420 mTime = new Time(Time.TIMEZONE_UTC); 421 } 422 423 void setRecurrence(EventRecurrence r) 424 { 425 mYear = 0; 426 mMonth = -1; 427 mR = r; 428 } 429 430 boolean get(Time iterator, int day) 431 { 432 int realYear = iterator.year; 433 int realMonth = iterator.month; 434 435 Time t = null; 436 437 if (SPEW) { 438 Log.i(TAG, "get called with iterator=" + iterator 439 + " " + iterator.month 440 + "/" + iterator.monthDay 441 + "/" + iterator.year + " day=" + day); 442 } 443 if (day < 1 || day > 28) { 444 // if might be past the end of the month, we need to normalize it 445 t = mTime; 446 t.set(day, realMonth, realYear); 447 unsafeNormalize(t); 448 realYear = t.year; 449 realMonth = t.month; 450 day = t.monthDay; 451 if (SPEW) { 452 Log.i(TAG, "normalized t=" + t + " " + t.month 453 + "/" + t.monthDay 454 + "/" + t.year); 455 } 456 } 457 458 /* 459 if (true || SPEW) { 460 Log.i(TAG, "set t=" + t + " " + realMonth + "/" + day + "/" + realYear); 461 } 462 */ 463 if (realYear != mYear || realMonth != mMonth) { 464 if (t == null) { 465 t = mTime; 466 t.set(day, realMonth, realYear); 467 unsafeNormalize(t); 468 if (SPEW) { 469 Log.i(TAG, "set t=" + t + " " + t.month 470 + "/" + t.monthDay 471 + "/" + t.year 472 + " realMonth=" + realMonth + " mMonth=" + mMonth); 473 } 474 } 475 mYear = realYear; 476 mMonth = realMonth; 477 mDays = generateDaysList(t, mR); 478 if (SPEW) { 479 Log.i(TAG, "generated days list"); 480 } 481 } 482 return (mDays & (1<<day)) != 0; 483 } 484 485 /** 486 * Fill in a bit set containing the days of the month on which this 487 * will occur. 488 * 489 * Only call this if the r.freq > DAILY. Otherwise, we should be 490 * processing the BYDAY, BYMONTHDAY, etc. as filters instead. 491 * 492 * monthOffset may be -1, 0 or 1 493 */ 494 private static int generateDaysList(Time generated, EventRecurrence r) 495 { 496 int days = 0; 497 498 int i, count, v; 499 int[] byday, bydayNum, bymonthday; 500 int j, lastDayThisMonth; 501 int first; // Time.SUNDAY, etc 502 int k; 503 504 lastDayThisMonth = generated.getActualMaximum(Time.MONTH_DAY); 505 506 // BYDAY 507 count = r.bydayCount; 508 if (count > 0) { 509 // calculate the day of week for the first of this month (first) 510 j = generated.monthDay; 511 while (j >= 8) { 512 j -= 7; 513 } 514 first = generated.weekDay; 515 if (first >= j) { 516 first = first - j + 1; 517 } else { 518 first = first - j + 8; 519 } 520 521 // What to do if the event is weekly: 522 // This isn't ideal, but we'll generate a month's worth of events 523 // and the code that calls this will only use the ones that matter 524 // for the current week. 525 byday = r.byday; 526 bydayNum = r.bydayNum; 527 for (i=0; i<count; i++) { 528 v = bydayNum[i]; 529 j = EventRecurrence.day2TimeDay(byday[i]) - first + 1; 530 if (j <= 0) { 531 j += 7; 532 } 533 if (v == 0) { 534 // v is 0, each day in the month/week 535 for (; j<=lastDayThisMonth; j+=7) { 536 if (SPEW) Log.i(TAG, "setting " + j + " for rule " 537 + v + "/" + EventRecurrence.day2TimeDay(byday[i])); 538 days |= 1 << j; 539 } 540 } 541 else if (v > 0) { 542 // v is positive, count from the beginning of the month 543 // -1 b/c the first one should add 0 544 j += 7*(v-1); 545 if (j <= lastDayThisMonth) { 546 if (SPEW) Log.i(TAG, "setting " + j + " for rule " 547 + v + "/" + EventRecurrence.day2TimeDay(byday[i])); 548 // if it's impossible, we drop it 549 days |= 1 << j; 550 } 551 } 552 else { 553 // v is negative, count from the end of the month 554 // find the last one 555 for (; j<=lastDayThisMonth; j+=7) { 556 } 557 // v is negative 558 // should do +1 b/c the last one should add 0, but we also 559 // skipped the j -= 7 b/c the loop to find the last one 560 // overshot by one week 561 j += 7*v; 562 if (j >= 1) { 563 if (SPEW) Log.i(TAG, "setting " + j + " for rule " 564 + v + "/" + EventRecurrence.day2TimeDay(byday[i])); 565 days |= 1 << j; 566 } 567 } 568 } 569 } 570 571 // BYMONTHDAY 572 // Q: What happens if we have BYMONTHDAY and BYDAY? 573 // A: I didn't see it in the spec, so in lieu of that, we'll 574 // intersect the two. That seems reasonable to me. 575 if (r.freq > EventRecurrence.WEEKLY) { 576 count = r.bymonthdayCount; 577 if (count != 0) { 578 bymonthday = r.bymonthday; 579 if (r.bydayCount == 0) { 580 for (i=0; i<count; i++) { 581 v = bymonthday[i]; 582 if (v >= 0) { 583 days |= 1 << v; 584 } else { 585 j = lastDayThisMonth + v + 1; // v is negative 586 if (j >= 1 && j <= lastDayThisMonth) { 587 days |= 1 << j; 588 } 589 } 590 } 591 } else { 592 // This is O(lastDayThisMonth*count), which is really 593 // O(count) with a decent sized constant. 594 for (j=1; j<=lastDayThisMonth; j++) { 595 next_day : { 596 if ((days&(1<<j)) != 0) { 597 for (i=0; i<count; i++) { 598 if (bymonthday[i] == j) { 599 break next_day; 600 } 601 } 602 days &= ~(1<<j); 603 } 604 } 605 } 606 } 607 } 608 } 609 return days; 610 } 611 612 private EventRecurrence mR; 613 private int mDays; 614 private Time mTime; 615 private int mYear; 616 private int mMonth; 617 } 618 619 /** 620 * Expands the recurrence within the given range using the given dtstart 621 * value. Returns an array of longs where each element is a date in UTC 622 * milliseconds. The return value is never null. If there are no dates 623 * then an array of length zero is returned. 624 * 625 * @param dtstart a Time object representing the first occurrence 626 * @param recur the recurrence rules, including RRULE, RDATES, EXRULE, and 627 * EXDATES 628 * @param rangeStartMillis the beginning of the range to expand, in UTC 629 * milliseconds 630 * @param rangeEndMillis the non-inclusive end of the range to expand, in 631 * UTC milliseconds; use -1 for the entire range. 632 * @return an array of dates, each date is in UTC milliseconds 633 * @throws DateException 634 * @throws android.util.TimeFormatException if recur cannot be parsed 635 */ 636 public long[] expand(Time dtstart, 637 RecurrenceSet recur, 638 long rangeStartMillis, 639 long rangeEndMillis) throws DateException { 640 String timezone = dtstart.timezone; 641 mIterator.clear(timezone); 642 mGenerated.clear(timezone); 643 644 // We don't need to clear the mUntil (and it wouldn't do any good to 645 // do so) because the "until" date string is specified in UTC and that 646 // sets the timezone in the mUntil Time object. 647 648 mIterator.set(rangeStartMillis); 649 long rangeStartDateValue = normDateTimeComparisonValue(mIterator); 650 651 long rangeEndDateValue; 652 if (rangeEndMillis != -1) { 653 mIterator.set(rangeEndMillis); 654 rangeEndDateValue = normDateTimeComparisonValue(mIterator); 655 } else { 656 rangeEndDateValue = Long.MAX_VALUE; 657 } 658 659 TreeSet<Long> dtSet = new TreeSet<Long>(); 660 661 if (recur.rrules != null) { 662 for (EventRecurrence rrule : recur.rrules) { 663 expand(dtstart, rrule, rangeStartDateValue, 664 rangeEndDateValue, true /* add */, dtSet); 665 } 666 } 667 if (recur.rdates != null) { 668 for (long dt : recur.rdates) { 669 // The dates are stored as milliseconds. We need to convert 670 // them to year/month/day values in the local timezone. 671 mIterator.set(dt); 672 long dtvalue = normDateTimeComparisonValue(mIterator); 673 dtSet.add(dtvalue); 674 } 675 } 676 if (recur.exrules != null) { 677 for (EventRecurrence exrule : recur.exrules) { 678 expand(dtstart, exrule, rangeStartDateValue, 679 rangeEndDateValue, false /* remove */, dtSet); 680 } 681 } 682 if (recur.exdates != null) { 683 for (long dt : recur.exdates) { 684 // The dates are stored as milliseconds. We need to convert 685 // them to year/month/day values in the local timezone. 686 mIterator.set(dt); 687 long dtvalue = normDateTimeComparisonValue(mIterator); 688 dtSet.remove(dtvalue); 689 } 690 } 691 if (dtSet.isEmpty()) { 692 // this can happen if the recurrence does not occur within the 693 // expansion window. 694 return new long[0]; 695 } 696 697 // The values in dtSet are represented in a special form that is useful 698 // for fast comparisons and that is easy to generate from year/month/day 699 // values. We need to convert these to UTC milliseconds and also to 700 // ensure that the dates are valid. 701 int len = dtSet.size(); 702 long[] dates = new long[len]; 703 int i = 0; 704 for (Long val: dtSet) { 705 setTimeFromLongValue(mIterator, val); 706 dates[i++] = mIterator.toMillis(true /* ignore isDst */); 707 } 708 return dates; 709 } 710 711 /** 712 * Run the recurrence algorithm. Processes events defined in the local 713 * timezone of the event. Return a list of iCalendar DATETIME 714 * strings containing the start date/times of the occurrences; the output 715 * times are defined in the local timezone of the event. 716 * 717 * If you want all of the events, pass Long.MAX_VALUE for rangeEndDateValue. If you pass 718 * Long.MAX_VALUE for rangeEnd, and the event doesn't have a COUNT or UNTIL field, 719 * you'll get a DateException. 720 * 721 * @param dtstart the dtstart date as defined in RFC2445. This 722 * {@link Time} should be in the timezone of the event. 723 * @param r the parsed recurrence, as defiend in RFC2445 724 * @param rangeStartDateValue the first date-time you care about, inclusive 725 * @param rangeEndDateValue the last date-time you care about, not inclusive (so 726 * if you care about everything up through and including 727 * Dec 22 1995, set last to Dec 23, 1995 00:00:00 728 * @param add Whether or not we should add to out, or remove from out. 729 * @param out the TreeSet you'd like to fill with the events 730 * @throws DateException 731 * @throws android.util.TimeFormatException if r cannot be parsed. 732 */ 733 public void expand(Time dtstart, 734 EventRecurrence r, 735 long rangeStartDateValue, 736 long rangeEndDateValue, 737 boolean add, 738 TreeSet<Long> out) throws DateException { 739 unsafeNormalize(dtstart); 740 long dtstartDateValue = normDateTimeComparisonValue(dtstart); 741 int count = 0; 742 743 // add the dtstart instance to the recurrence, if within range. 744 // For example, if dtstart is Mar 1, 2010 and the range is Jan 1 - Apr 1, 745 // then add it here and increment count. If the range is earlier or later, 746 // then don't add it here. In that case, count will be incremented later 747 // inside the loop. It is important that count gets incremented exactly 748 // once here or in the loop for dtstart. 749 // 750 // NOTE: if DTSTART is not synchronized with the recurrence rule, the first instance 751 // we return will not fit the RRULE pattern. 752 if (add && dtstartDateValue >= rangeStartDateValue 753 && dtstartDateValue < rangeEndDateValue) { 754 out.add(dtstartDateValue); 755 ++count; 756 } 757 758 Time iterator = mIterator; 759 Time until = mUntil; 760 StringBuilder sb = mStringBuilder; 761 Time generated = mGenerated; 762 DaySet days = mDays; 763 764 try { 765 766 days.setRecurrence(r); 767 if (rangeEndDateValue == Long.MAX_VALUE && r.until == null && r.count == 0) { 768 throw new DateException( 769 "No range end provided for a recurrence that has no UNTIL or COUNT."); 770 } 771 772 // the top-level frequency 773 int freqField; 774 int freqAmount = r.interval; 775 int freq = r.freq; 776 switch (freq) 777 { 778 case EventRecurrence.SECONDLY: 779 freqField = Time.SECOND; 780 break; 781 case EventRecurrence.MINUTELY: 782 freqField = Time.MINUTE; 783 break; 784 case EventRecurrence.HOURLY: 785 freqField = Time.HOUR; 786 break; 787 case EventRecurrence.DAILY: 788 freqField = Time.MONTH_DAY; 789 break; 790 case EventRecurrence.WEEKLY: 791 freqField = Time.MONTH_DAY; 792 freqAmount = 7 * r.interval; 793 if (freqAmount <= 0) { 794 freqAmount = 7; 795 } 796 break; 797 case EventRecurrence.MONTHLY: 798 freqField = Time.MONTH; 799 break; 800 case EventRecurrence.YEARLY: 801 freqField = Time.YEAR; 802 break; 803 default: 804 throw new DateException("bad freq=" + freq); 805 } 806 if (freqAmount <= 0) { 807 freqAmount = 1; 808 } 809 810 int bymonthCount = r.bymonthCount; 811 boolean usebymonth = useBYX(freq, EventRecurrence.MONTHLY, bymonthCount); 812 boolean useDays = freq >= EventRecurrence.WEEKLY && 813 (r.bydayCount > 0 || r.bymonthdayCount > 0); 814 int byhourCount = r.byhourCount; 815 boolean usebyhour = useBYX(freq, EventRecurrence.HOURLY, byhourCount); 816 int byminuteCount = r.byminuteCount; 817 boolean usebyminute = useBYX(freq, EventRecurrence.MINUTELY, byminuteCount); 818 int bysecondCount = r.bysecondCount; 819 boolean usebysecond = useBYX(freq, EventRecurrence.SECONDLY, bysecondCount); 820 821 // initialize the iterator 822 iterator.set(dtstart); 823 if (freqField == Time.MONTH) { 824 if (useDays) { 825 // if it's monthly, and we're going to be generating 826 // days, set the iterator day field to 1 because sometimes 827 // we'll skip months if it's greater than 28. 828 // XXX Do we generate days for MONTHLY w/ BYHOUR? If so, 829 // we need to do this then too. 830 iterator.monthDay = 1; 831 } 832 } 833 834 long untilDateValue; 835 if (r.until != null) { 836 // Ensure that the "until" date string is specified in UTC. 837 String untilStr = r.until; 838 // 15 is length of date-time without trailing Z e.g. "20090204T075959" 839 // A string such as 20090204 is a valid UNTIL (see RFC 2445) and the 840 // Z should not be added. 841 if (untilStr.length() == 15) { 842 untilStr = untilStr + 'Z'; 843 } 844 // The parse() method will set the timezone to UTC 845 until.parse(untilStr); 846 847 // We need the "until" year/month/day values to be in the same 848 // timezone as all the generated dates so that we can compare them 849 // using the values returned by normDateTimeComparisonValue(). 850 until.switchTimezone(dtstart.timezone); 851 untilDateValue = normDateTimeComparisonValue(until); 852 } else { 853 untilDateValue = Long.MAX_VALUE; 854 } 855 856 sb.ensureCapacity(15); 857 sb.setLength(15); // TODO: pay attention to whether or not the event 858 // is an all-day one. 859 860 if (SPEW) { 861 Log.i(TAG, "expand called w/ rangeStart=" + rangeStartDateValue 862 + " rangeEnd=" + rangeEndDateValue); 863 } 864 865 // go until the end of the range or we're done with this event 866 boolean eventEnded = false; 867 int failsafe = 0; // Avoid infinite loops 868 events: { 869 while (true) { 870 int monthIndex = 0; 871 if (failsafe++ > MAX_ALLOWED_ITERATIONS) { // Give up after about 1 second of processing 872 throw new DateException("Recurrence processing stuck: " + r.toString()); 873 } 874 875 unsafeNormalize(iterator); 876 877 int iteratorYear = iterator.year; 878 int iteratorMonth = iterator.month + 1; 879 int iteratorDay = iterator.monthDay; 880 int iteratorHour = iterator.hour; 881 int iteratorMinute = iterator.minute; 882 int iteratorSecond = iterator.second; 883 884 // year is never expanded -- there is no BYYEAR 885 generated.set(iterator); 886 887 if (SPEW) Log.i(TAG, "year=" + generated.year); 888 889 do { // month 890 int month = usebymonth 891 ? r.bymonth[monthIndex] 892 : iteratorMonth; 893 month--; 894 if (SPEW) Log.i(TAG, " month=" + month); 895 896 int dayIndex = 1; 897 int lastDayToExamine = 0; 898 899 // Use this to handle weeks that overlap the end of the month. 900 // Keep the year and month that days is for, and generate it 901 // when needed in the loop 902 if (useDays) { 903 // Determine where to start and end, don't worry if this happens 904 // to be before dtstart or after the end, because that will be 905 // filtered in the inner loop 906 if (freq == EventRecurrence.WEEKLY) { 907 /* 908 * iterator.weekDay indicates the day of the week (0-6, SU-SA). 909 * Because dayIndex might start in the middle of a week, and we're 910 * interested in treating a week as a unit, we want to move 911 * backward to the start of the week. (This could make the 912 * dayIndex negative, which will be corrected by normalization 913 * later on.) 914 * 915 * The day that starts the week is determined by WKST, which 916 * defaults to MO. 917 * 918 * Example: dayIndex is Tuesday the 8th, and weeks start on 919 * Thursdays. Tuesday is day 2, Thursday is day 4, so we 920 * want to move back (2 - 4 + 7) % 7 = 5 days to the previous 921 * Thursday. If weeks started on Mondays, we would only 922 * need to move back (2 - 1 + 7) % 7 = 1 day. 923 */ 924 int weekStartAdj = (iterator.weekDay - 925 EventRecurrence.day2TimeDay(r.wkst) + 7) % 7; 926 dayIndex = iterator.monthDay - weekStartAdj; 927 lastDayToExamine = dayIndex + 6; 928 } else { 929 lastDayToExamine = generated 930 .getActualMaximum(Time.MONTH_DAY); 931 } 932 if (SPEW) Log.i(TAG, "dayIndex=" + dayIndex 933 + " lastDayToExamine=" + lastDayToExamine 934 + " days=" + days); 935 } 936 937 do { // day 938 int day; 939 if (useDays) { 940 if (!days.get(iterator, dayIndex)) { 941 dayIndex++; 942 continue; 943 } else { 944 day = dayIndex; 945 } 946 } else { 947 day = iteratorDay; 948 } 949 if (SPEW) Log.i(TAG, " day=" + day); 950 951 // hour 952 int hourIndex = 0; 953 do { 954 int hour = usebyhour 955 ? r.byhour[hourIndex] 956 : iteratorHour; 957 if (SPEW) Log.i(TAG, " hour=" + hour + " usebyhour=" + usebyhour); 958 959 // minute 960 int minuteIndex = 0; 961 do { 962 int minute = usebyminute 963 ? r.byminute[minuteIndex] 964 : iteratorMinute; 965 if (SPEW) Log.i(TAG, " minute=" + minute); 966 967 // second 968 int secondIndex = 0; 969 do { 970 int second = usebysecond 971 ? r.bysecond[secondIndex] 972 : iteratorSecond; 973 if (SPEW) Log.i(TAG, " second=" + second); 974 975 // we do this here each time, because if we distribute it, we find the 976 // month advancing extra times, as we set the month to the 32nd, 33rd, etc. 977 // days. 978 generated.set(second, minute, hour, day, month, iteratorYear); 979 unsafeNormalize(generated); 980 981 long genDateValue = normDateTimeComparisonValue(generated); 982 // sometimes events get generated (BYDAY, BYHOUR, etc.) that 983 // are before dtstart. Filter these. I believe this is correct, 984 // but Google Calendar doesn't seem to always do this. 985 if (genDateValue >= dtstartDateValue) { 986 // filter and then add 987 // TODO: we don't check for stop conditions (like 988 // passing the "end" date) unless the filter 989 // allows the event. Could stop sooner. 990 int filtered = filter(r, generated); 991 if (0 == filtered) { 992 993 // increase the count as long 994 // as this isn't the same 995 // as the first instance 996 // specified by the DTSTART 997 // (for RRULEs -- additive). 998 // This condition must be the complement of the 999 // condition for incrementing count at the 1000 // beginning of the method, so if we don't 1001 // increment count there, we increment it here. 1002 // For example, if add is set and dtstartDateValue 1003 // is inside the start/end range, then it was added 1004 // and count was incremented at the beginning. 1005 // If dtstartDateValue is outside the range or add 1006 // is not set, then we must increment count here. 1007 if (!(dtstartDateValue == genDateValue 1008 && add 1009 && dtstartDateValue >= rangeStartDateValue 1010 && dtstartDateValue < rangeEndDateValue)) { 1011 ++count; 1012 } 1013 // one reason we can stop is that 1014 // we're past the until date 1015 if (genDateValue > untilDateValue) { 1016 if (SPEW) { 1017 Log.i(TAG, "stopping b/c until=" 1018 + untilDateValue 1019 + " generated=" 1020 + genDateValue); 1021 } 1022 break events; 1023 } 1024 // or we're past rangeEnd 1025 if (genDateValue >= rangeEndDateValue) { 1026 if (SPEW) { 1027 Log.i(TAG, "stopping b/c rangeEnd=" 1028 + rangeEndDateValue 1029 + " generated=" + generated); 1030 } 1031 break events; 1032 } 1033 1034 if (genDateValue >= rangeStartDateValue) { 1035 if (SPEW) { 1036 Log.i(TAG, "adding date=" + generated + " filtered=" + filtered); 1037 } 1038 if (add) { 1039 out.add(genDateValue); 1040 } else { 1041 out.remove(genDateValue); 1042 } 1043 } 1044 // another is that count is high enough 1045 if (r.count > 0 && r.count == count) { 1046 //Log.i(TAG, "stopping b/c count=" + count); 1047 break events; 1048 } 1049 } 1050 } 1051 secondIndex++; 1052 } while (usebysecond && secondIndex < bysecondCount); 1053 minuteIndex++; 1054 } while (usebyminute && minuteIndex < byminuteCount); 1055 hourIndex++; 1056 } while (usebyhour && hourIndex < byhourCount); 1057 dayIndex++; 1058 } while (useDays && dayIndex <= lastDayToExamine); 1059 monthIndex++; 1060 } while (usebymonth && monthIndex < bymonthCount); 1061 1062 // Add freqAmount to freqField until we get another date that we want. 1063 // We don't want to "generate" dates with the iterator. 1064 // XXX: We do this for days, because there is a varying number of days 1065 // per month 1066 int oldDay = iterator.monthDay; 1067 generated.set(iterator); // just using generated as a temporary. 1068 int n = 1; 1069 while (true) { 1070 int value = freqAmount * n; 1071 switch (freqField) { 1072 case Time.SECOND: 1073 iterator.second += value; 1074 break; 1075 case Time.MINUTE: 1076 iterator.minute += value; 1077 break; 1078 case Time.HOUR: 1079 iterator.hour += value; 1080 break; 1081 case Time.MONTH_DAY: 1082 iterator.monthDay += value; 1083 break; 1084 case Time.MONTH: 1085 iterator.month += value; 1086 break; 1087 case Time.YEAR: 1088 iterator.year += value; 1089 break; 1090 case Time.WEEK_DAY: 1091 iterator.monthDay += value; 1092 break; 1093 case Time.YEAR_DAY: 1094 iterator.monthDay += value; 1095 break; 1096 default: 1097 throw new RuntimeException("bad field=" + freqField); 1098 } 1099 1100 unsafeNormalize(iterator); 1101 if (freqField != Time.YEAR && freqField != Time.MONTH) { 1102 break; 1103 } 1104 if (iterator.monthDay == oldDay) { 1105 break; 1106 } 1107 n++; 1108 iterator.set(generated); 1109 } 1110 } 1111 } 1112 } 1113 catch (DateException e) { 1114 Log.w(TAG, "DateException with r=" + r + " rangeStart=" + rangeStartDateValue 1115 + " rangeEnd=" + rangeEndDateValue); 1116 throw e; 1117 } 1118 catch (RuntimeException t) { 1119 Log.w(TAG, "RuntimeException with r=" + r + " rangeStart=" + rangeStartDateValue 1120 + " rangeEnd=" + rangeEndDateValue); 1121 throw t; 1122 } 1123 } 1124 1125 /** 1126 * Normalizes the date fields to give a valid date, but if the time falls 1127 * in the invalid window during a transition out of Daylight Saving Time 1128 * when time jumps forward an hour, then the "normalized" value will be 1129 * invalid. 1130 * <p> 1131 * This method also computes the weekDay and yearDay fields. 1132 * 1133 * <p> 1134 * This method does not modify the fields isDst, or gmtOff. 1135 */ 1136 static void unsafeNormalize(Time date) { 1137 int second = date.second; 1138 int minute = date.minute; 1139 int hour = date.hour; 1140 int monthDay = date.monthDay; 1141 int month = date.month; 1142 int year = date.year; 1143 1144 int addMinutes = ((second < 0) ? (second - 59) : second) / 60; 1145 second -= addMinutes * 60; 1146 minute += addMinutes; 1147 int addHours = ((minute < 0) ? (minute - 59) : minute) / 60; 1148 minute -= addHours * 60; 1149 hour += addHours; 1150 int addDays = ((hour < 0) ? (hour - 23) : hour) / 24; 1151 hour -= addDays * 24; 1152 monthDay += addDays; 1153 1154 // We want to make "monthDay" positive. We do this by subtracting one 1155 // from the year and adding a year's worth of days to "monthDay" in 1156 // the following loop while "monthDay" <= 0. 1157 while (monthDay <= 0) { 1158 // If month is after Feb, then add this year's length so that we 1159 // include this year's leap day, if any. 1160 // Otherwise (the month is Feb or earlier), add last year's length. 1161 // Subtract one from the year in either case. This gives the same 1162 // effective date but makes monthDay (the day of the month) much 1163 // larger. Eventually (usually in one iteration) monthDay will 1164 // be positive. 1165 int days = month > 1 ? yearLength(year) : yearLength(year - 1); 1166 monthDay += days; 1167 year -= 1; 1168 } 1169 // At this point, monthDay >= 1. Normalize the month to the range [0,11]. 1170 if (month < 0) { 1171 int years = (month + 1) / 12 - 1; 1172 year += years; 1173 month -= 12 * years; 1174 } else if (month >= 12) { 1175 int years = month / 12; 1176 year += years; 1177 month -= 12 * years; 1178 } 1179 // At this point, month is in the range [0,11] and monthDay >= 1. 1180 // Now loop until the monthDay is in the correct range for the month. 1181 while (true) { 1182 // On January, check if we can jump forward a whole year. 1183 if (month == 0) { 1184 int yearLength = yearLength(year); 1185 if (monthDay > yearLength) { 1186 year++; 1187 monthDay -= yearLength; 1188 } 1189 } 1190 int monthLength = monthLength(year, month); 1191 if (monthDay > monthLength) { 1192 monthDay -= monthLength; 1193 month++; 1194 if (month >= 12) { 1195 month -= 12; 1196 year++; 1197 } 1198 } else break; 1199 } 1200 // At this point, monthDay <= the length of the current month and is 1201 // in the range [1,31]. 1202 1203 date.second = second; 1204 date.minute = minute; 1205 date.hour = hour; 1206 date.monthDay = monthDay; 1207 date.month = month; 1208 date.year = year; 1209 date.weekDay = weekDay(year, month, monthDay); 1210 date.yearDay = yearDay(year, month, monthDay); 1211 } 1212 1213 /** 1214 * Returns true if the given year is a leap year. 1215 * 1216 * @param year the given year to test 1217 * @return true if the given year is a leap year. 1218 */ 1219 static boolean isLeapYear(int year) { 1220 return (year % 4 == 0) && ((year % 100 != 0) || (year % 400 == 0)); 1221 } 1222 1223 /** 1224 * Returns the number of days in the given year. 1225 * 1226 * @param year the given year 1227 * @return the number of days in the given year. 1228 */ 1229 static int yearLength(int year) { 1230 return isLeapYear(year) ? 366 : 365; 1231 } 1232 1233 private static final int[] DAYS_PER_MONTH = { 31, 28, 31, 30, 31, 30, 31, 1234 31, 30, 31, 30, 31 }; 1235 private static final int[] DAYS_IN_YEAR_PRECEDING_MONTH = { 0, 31, 59, 90, 1236 120, 151, 180, 212, 243, 273, 304, 334 }; 1237 1238 /** 1239 * Returns the number of days in the given month of the given year. 1240 * 1241 * @param year the given year. 1242 * @param month the given month in the range [0,11] 1243 * @return the number of days in the given month of the given year. 1244 */ 1245 static int monthLength(int year, int month) { 1246 int n = DAYS_PER_MONTH[month]; 1247 if (n != 28) { 1248 return n; 1249 } 1250 return isLeapYear(year) ? 29 : 28; 1251 } 1252 1253 /** 1254 * Computes the weekday, a number in the range [0,6] where Sunday=0, from 1255 * the given year, month, and day. 1256 * 1257 * @param year the year 1258 * @param month the 0-based month in the range [0,11] 1259 * @param day the 1-based day of the month in the range [1,31] 1260 * @return the weekday, a number in the range [0,6] where Sunday=0 1261 */ 1262 static int weekDay(int year, int month, int day) { 1263 if (month <= 1) { 1264 month += 12; 1265 year -= 1; 1266 } 1267 return (day + (13 * month - 14) / 5 + year + year/4 - year/100 + year/400) % 7; 1268 } 1269 1270 /** 1271 * Computes the 0-based "year day", given the year, month, and day. 1272 * 1273 * @param year the year 1274 * @param month the 0-based month in the range [0,11] 1275 * @param day the 1-based day in the range [1,31] 1276 * @return the 0-based "year day", the number of days into the year 1277 */ 1278 static int yearDay(int year, int month, int day) { 1279 int yearDay = DAYS_IN_YEAR_PRECEDING_MONTH[month] + day - 1; 1280 if (month >= 2 && isLeapYear(year)) { 1281 yearDay += 1; 1282 } 1283 return yearDay; 1284 } 1285 1286 /** 1287 * Converts a normalized Time value to a 64-bit long. The mapping of Time 1288 * values to longs provides a total ordering on the Time values so that 1289 * two Time values can be compared efficiently by comparing their 64-bit 1290 * long values. This is faster than converting the Time values to UTC 1291 * millliseconds. 1292 * 1293 * @param normalized a Time object whose date and time fields have been 1294 * normalized 1295 * @return a 64-bit long value that can be used for comparing and ordering 1296 * dates and times represented by Time objects 1297 */ 1298 private static final long normDateTimeComparisonValue(Time normalized) { 1299 // 37 bits for the year, 4 bits for the month, 5 bits for the monthDay, 1300 // 5 bits for the hour, 6 bits for the minute, 6 bits for the second. 1301 return ((long)normalized.year << 26) + (normalized.month << 22) 1302 + (normalized.monthDay << 17) + (normalized.hour << 12) 1303 + (normalized.minute << 6) + normalized.second; 1304 } 1305 1306 private static final void setTimeFromLongValue(Time date, long val) { 1307 date.year = (int) (val >> 26); 1308 date.month = (int) (val >> 22) & 0xf; 1309 date.monthDay = (int) (val >> 17) & 0x1f; 1310 date.hour = (int) (val >> 12) & 0x1f; 1311 date.minute = (int) (val >> 6) & 0x3f; 1312 date.second = (int) (val & 0x3f); 1313 } 1314 } 1315