src/applications/calendar/parser/data/PhutilCalendarRecurrenceRule.php

   1 <?php
   2
   3 final class PhutilCalendarRecurrenceRule
   4   extends PhutilCalendarRecurrenceSource {
   5
   6   private $startDateTime;
   7   private $frequency;
   8   private $frequencyScale;
   9   private $interval = 1;
  10   private $bySecond = array();
  11   private $byMinute = array();
  12   private $byHour = array();
  13   private $byDay = array();
  14   private $byMonthDay = array();
  15   private $byYearDay = array();
  16   private $byWeekNumber = array();
  17   private $byMonth = array();
  18   private $bySetPosition = array();
  19   private $weekStart = self::WEEKDAY_MONDAY;
  20   private $count;
  21   private $until;
  22
  23   private $cursorSecond;
  24   private $cursorMinute;
  25   private $cursorHour;
  26   private $cursorHourState;
  27   private $cursorWeek;
  28   private $cursorWeekday;
  29   private $cursorWeekState;
  30   private $cursorDay;
  31   private $cursorDayState;
  32   private $cursorMonth;
  33   private $cursorYear;
  34
  35   private $setSeconds;
  36   private $setMinutes;
  37   private $setHours;
  38   private $setDays;
  39   private $setMonths;
  40   private $setWeeks;
  41   private $setYears;
  42
  43   private $stateSecond;
  44   private $stateMinute;
  45   private $stateHour;
  46   private $stateDay;
  47   private $stateWeek;
  48   private $stateMonth;
  49   private $stateYear;
  50
  51   private $baseYear;
  52   private $isAllDay;
  53   private $activeSet = array();
  54   private $nextSet = array();
  55   private $minimumEpoch;
  56
  57   const FREQUENCY_SECONDLY = 'SECONDLY';
  58   const FREQUENCY_MINUTELY = 'MINUTELY';
  59   const FREQUENCY_HOURLY = 'HOURLY';
  60   const FREQUENCY_DAILY = 'DAILY';
  61   const FREQUENCY_WEEKLY = 'WEEKLY';
  62   const FREQUENCY_MONTHLY = 'MONTHLY';
  63   const FREQUENCY_YEARLY = 'YEARLY';
  64
  65   const SCALE_SECONDLY = 1;
  66   const SCALE_MINUTELY = 2;
  67   const SCALE_HOURLY = 3;
  68   const SCALE_DAILY = 4;
  69   const SCALE_WEEKLY = 5;
  70   const SCALE_MONTHLY = 6;
  71   const SCALE_YEARLY = 7;
  72
  73   const WEEKDAY_SUNDAY = 'SU';
  74   const WEEKDAY_MONDAY = 'MO';
  75   const WEEKDAY_TUESDAY = 'TU';
  76   const WEEKDAY_WEDNESDAY = 'WE';
  77   const WEEKDAY_THURSDAY = 'TH';
  78   const WEEKDAY_FRIDAY = 'FR';
  79   const WEEKDAY_SATURDAY = 'SA';
  80
  81   const WEEKINDEX_SUNDAY = 0;
  82   const WEEKINDEX_MONDAY = 1;
  83   const WEEKINDEX_TUESDAY = 2;
  84   const WEEKINDEX_WEDNESDAY = 3;
  85   const WEEKINDEX_THURSDAY = 4;
  86   const WEEKINDEX_FRIDAY = 5;
  87   const WEEKINDEX_SATURDAY = 6;
  88
  89   public function toDictionary() {
  90     $parts = array();
  91
  92     $parts['FREQ'] = $this->getFrequency();
  93
  94     $interval = $this->getInterval();
  95     if ($interval != 1) {
  96       $parts['INTERVAL'] = $interval;
  97     }
  98
  99     $by_second = $this->getBySecond();
 100     if ($by_second) {
 101       $parts['BYSECOND'] = $by_second;
 102     }
 103
 104     $by_minute = $this->getByMinute();
 105     if ($by_minute) {
 106       $parts['BYMINUTE'] = $by_minute;
 107     }
 108
 109     $by_hour = $this->getByHour();
 110     if ($by_hour) {
 111       $parts['BYHOUR'] = $by_hour;
 112     }
 113
 114     $by_day = $this->getByDay();
 115     if ($by_day) {
 116       $parts['BYDAY'] = $by_day;
 117     }
 118
 119     $by_month = $this->getByMonth();
 120     if ($by_month) {
 121       $parts['BYMONTH'] = $by_month;
 122     }
 123
 124     $by_monthday = $this->getByMonthDay();
 125     if ($by_monthday) {
 126       $parts['BYMONTHDAY'] = $by_monthday;
 127     }
 128
 129     $by_yearday = $this->getByYearDay();
 130     if ($by_yearday) {
 131       $parts['BYYEARDAY'] = $by_yearday;
 132     }
 133
 134     $by_weekno = $this->getByWeekNumber();
 135     if ($by_weekno) {
 136       $parts['BYWEEKNO'] = $by_weekno;
 137     }
 138
 139     $by_setpos = $this->getBySetPosition();
 140     if ($by_setpos) {
 141       $parts['BYSETPOS'] = $by_setpos;
 142     }
 143
 144     $wkst = $this->getWeekStart();
 145     if ($wkst != self::WEEKDAY_MONDAY) {
 146       $parts['WKST'] = $wkst;
 147     }
 148
 149     $count = $this->getCount();
 150     if ($count) {
 151       $parts['COUNT'] = $count;
 152     }
 153
 154     $until = $this->getUntil();
 155     if ($until) {
 156       $parts['UNTIL'] = $until->getISO8601();
 157     }
 158
 159     return $parts;
 160   }
 161
 162   public static function newFromDictionary(array $dict) {
 163     static $expect;
 164     if ($expect === null) {
 165       $expect = array_fuse(
 166         array(
 167           'FREQ',
 168           'INTERVAL',
 169           'BYSECOND',
 170           'BYMINUTE',
 171           'BYHOUR',
 172           'BYDAY',
 173           'BYMONTH',
 174           'BYMONTHDAY',
 175           'BYYEARDAY',
 176           'BYWEEKNO',
 177           'BYSETPOS',
 178           'WKST',
 179           'UNTIL',
 180           'COUNT',
 181         ));
 182     }
 183
 184     foreach ($dict as $key => $value) {
 185       if (empty($expect[$key])) {
 186         throw new Exception(
 187           pht(
 188             'RRULE dictionary includes unknown key "%s". Expected keys '.
 189             'are: %s.',
 190             $key,
 191             implode(', ', array_keys($expect))));
 192       }
 193     }
 194
 195     $rrule = id(new self())
 196       ->setFrequency(idx($dict, 'FREQ'))
 197       ->setInterval(idx($dict, 'INTERVAL', 1))
 198       ->setBySecond(idx($dict, 'BYSECOND', array()))
 199       ->setByMinute(idx($dict, 'BYMINUTE', array()))
 200       ->setByHour(idx($dict, 'BYHOUR', array()))
 201       ->setByDay(idx($dict, 'BYDAY', array()))
 202       ->setByMonth(idx($dict, 'BYMONTH', array()))
 203       ->setByMonthDay(idx($dict, 'BYMONTHDAY', array()))
 204       ->setByYearDay(idx($dict, 'BYYEARDAY', array()))
 205       ->setByWeekNumber(idx($dict, 'BYWEEKNO', array()))
 206       ->setBySetPosition(idx($dict, 'BYSETPOS', array()))
 207       ->setWeekStart(idx($dict, 'WKST', self::WEEKDAY_MONDAY));
 208
 209     $count = idx($dict, 'COUNT');
 210     if ($count) {
 211       $rrule->setCount($count);
 212     }
 213
 214     $until = idx($dict, 'UNTIL');
 215     if ($until) {
 216       $until = PhutilCalendarAbsoluteDateTime::newFromISO8601($until);
 217       $rrule->setUntil($until);
 218     }
 219
 220     return $rrule;
 221   }
 222
 223   public function toRRULE() {
 224     $dict = $this->toDictionary();
 225
 226     $parts = array();
 227     foreach ($dict as $key => $value) {
 228       if (is_array($value)) {
 229         $value = implode(',', $value);
 230       }
 231       $parts[] = "{$key}={$value}";
 232     }
 233
 234     return implode(';', $parts);
 235   }
 236
 237   public static function newFromRRULE($rrule) {
 238     $parts = explode(';', $rrule);
 239
 240     $dict = array();
 241     foreach ($parts as $part) {
 242       list($key, $value) = explode('=', $part, 2);
 243       switch ($key) {
 244         case 'FREQ':
 245         case 'INTERVAL':
 246         case 'WKST':
 247         case 'COUNT':
 248         case 'UNTIL';
 249           break;
 250         default:
 251           $value = explode(',', $value);
 252           break;
 253       }
 254       $dict[$key] = $value;
 255     }
 256
 257     $int_lists = array_fuse(
 258       array(
 259         // NOTE: "BYDAY" is absent, and takes a list like "MO, TU, WE".
 260         'BYSECOND',
 261         'BYMINUTE',
 262         'BYHOUR',
 263         'BYMONTH',
 264         'BYMONTHDAY',
 265         'BYYEARDAY',
 266         'BYWEEKNO',
 267         'BYSETPOS',
 268       ));
 269
 270     $int_values = array_fuse(
 271       array(
 272         'COUNT',
 273         'INTERVAL',
 274       ));
 275
 276     foreach ($dict as $key => $value) {
 277       if (isset($int_values[$key])) {
 278         // None of these values may be negative.
 279         if (!preg_match('/^\d+\z/', $value)) {
 280           throw new Exception(
 281             pht(
 282               'Unexpected value "%s" in "%s" RULE property: expected an '.
 283               'integer.',
 284               $value,
 285               $key));
 286         }
 287         $dict[$key] = (int)$value;
 288       }
 289
 290       if (isset($int_lists[$key])) {
 291         foreach ($value as $k => $v) {
 292           if (!preg_match('/^-?\d+\z/', $v)) {
 293             throw new Exception(
 294               pht(
 295                 'Unexpected value "%s" in "%s" RRULE property: expected '.
 296                 'only integers.',
 297                 $v,
 298                 $key));
 299           }
 300           $value[$k] = (int)$v;
 301         }
 302         $dict[$key] = $value;
 303       }
 304     }
 305
 306     return self::newFromDictionary($dict);
 307   }
 308
 309   private static function getAllWeekdayConstants() {
 310     return array_keys(self::getWeekdayIndexMap());
 311   }
 312
 313   private static function getWeekdayIndexMap() {
 314     static $map = array(
 315       self::WEEKDAY_SUNDAY => self::WEEKINDEX_SUNDAY,
 316       self::WEEKDAY_MONDAY => self::WEEKINDEX_MONDAY,
 317       self::WEEKDAY_TUESDAY => self::WEEKINDEX_TUESDAY,
 318       self::WEEKDAY_WEDNESDAY => self::WEEKINDEX_WEDNESDAY,
 319       self::WEEKDAY_THURSDAY => self::WEEKINDEX_THURSDAY,
 320       self::WEEKDAY_FRIDAY => self::WEEKINDEX_FRIDAY,
 321       self::WEEKDAY_SATURDAY => self::WEEKINDEX_SATURDAY,
 322     );
 323
 324     return $map;
 325   }
 326
 327   private static function getWeekdayIndex($weekday) {
 328     $map = self::getWeekdayIndexMap();
 329     if (!isset($map[$weekday])) {
 330       $constants = array_keys($map);
 331       throw new Exception(
 332         pht(
 333           'Weekday "%s" is not a valid weekday constant. Valid constants '.
 334           'are: %s.',
 335           $weekday,
 336           implode(', ', $constants)));
 337     }
 338
 339     return $map[$weekday];
 340   }
 341
 342   public function setStartDateTime(PhutilCalendarDateTime $start) {
 343     $this->startDateTime = $start;
 344     return $this;
 345   }
 346
 347   public function getStartDateTime() {
 348     return $this->startDateTime;
 349   }
 350
 351   public function setCount($count) {
 352     if ($count < 1) {
 353       throw new Exception(
 354         pht(
 355           'RRULE COUNT value "%s" is invalid: count must be at least 1.',
 356           $count));
 357     }
 358
 359     $this->count = $count;
 360     return $this;
 361   }
 362
 363   public function getCount() {
 364     return $this->count;
 365   }
 366
 367   public function setUntil(PhutilCalendarDateTime $until) {
 368     $this->until = $until;
 369     return $this;
 370   }
 371
 372   public function getUntil() {
 373     return $this->until;
 374   }
 375
 376   public function setFrequency($frequency) {
 377     static $map = array(
 378       self::FREQUENCY_SECONDLY => self::SCALE_SECONDLY,
 379       self::FREQUENCY_MINUTELY => self::SCALE_MINUTELY,
 380       self::FREQUENCY_HOURLY => self::SCALE_HOURLY,
 381       self::FREQUENCY_DAILY => self::SCALE_DAILY,
 382       self::FREQUENCY_WEEKLY => self::SCALE_WEEKLY,
 383       self::FREQUENCY_MONTHLY => self::SCALE_MONTHLY,
 384       self::FREQUENCY_YEARLY => self::SCALE_YEARLY,
 385     );
 386
 387     if (empty($map[$frequency])) {
 388       throw new Exception(
 389         pht(
 390           'RRULE FREQ "%s" is invalid. Valid frequencies are: %s.',
 391           $frequency,
 392           implode(', ', array_keys($map))));
 393     }
 394
 395     $this->frequency = $frequency;
 396     $this->frequencyScale = $map[$frequency];
 397
 398     return $this;
 399   }
 400
 401   public function getFrequency() {
 402     return $this->frequency;
 403   }
 404
 405   public function getFrequencyScale() {
 406     return $this->frequencyScale;
 407   }
 408
 409   public function setInterval($interval) {
 410     if (!is_int($interval)) {
 411       throw new Exception(
 412         pht(
 413           'RRULE INTERVAL "%s" is invalid: interval must be an integer.',
 414           $interval));
 415     }
 416
 417     if ($interval < 1) {
 418       throw new Exception(
 419         pht(
 420           'RRULE INTERVAL "%s" is invalid: interval must be 1 or more.',
 421           $interval));
 422     }
 423
 424     $this->interval = $interval;
 425     return $this;
 426   }
 427
 428   public function getInterval() {
 429     return $this->interval;
 430   }
 431
 432   public function setBySecond(array $by_second) {
 433     $this->assertByRange('BYSECOND', $by_second, 0, 60);
 434     $this->bySecond = array_fuse($by_second);
 435     return $this;
 436   }
 437
 438   public function getBySecond() {
 439     return $this->bySecond;
 440   }
 441
 442   public function setByMinute(array $by_minute) {
 443     $this->assertByRange('BYMINUTE', $by_minute, 0, 59);
 444     $this->byMinute = array_fuse($by_minute);
 445     return $this;
 446   }
 447
 448   public function getByMinute() {
 449     return $this->byMinute;
 450   }
 451
 452   public function setByHour(array $by_hour) {
 453     $this->assertByRange('BYHOUR', $by_hour, 0, 23);
 454     $this->byHour = array_fuse($by_hour);
 455     return $this;
 456   }
 457
 458   public function getByHour() {
 459     return $this->byHour;
 460   }
 461
 462   public function setByDay(array $by_day) {
 463     $constants = self::getAllWeekdayConstants();
 464     $constants = implode('|', $constants);
 465
 466     $pattern = '/^(?:[+-]?([1-9]\d?))?('.$constants.')\z/';
 467     foreach ($by_day as $key => $value) {
 468       $matches = null;
 469       if (!preg_match($pattern, $value, $matches)) {
 470         throw new Exception(
 471           pht(
 472             'RRULE BYDAY value "%s" is invalid: rule part must be in the '.
 473             'expected form (like "MO", "-3TH", or "+2SU").',
 474             $value));
 475       }
 476
 477       // The maximum allowed value is 53, which corresponds to "the 53rd
 478       // Monday every year" or similar when evaluated against a YEARLY rule.
 479
 480       $maximum = 53;
 481       $magnitude = (int)$matches[1];
 482       if ($magnitude > $maximum) {
 483         throw new Exception(
 484           pht(
 485             'RRULE BYDAY value "%s" has an offset with magnitude "%s", but '.
 486             'the maximum permitted value is "%s".',
 487             $value,
 488             $magnitude,
 489             $maximum));
 490       }
 491
 492       // Normalize "+3FR" into "3FR".
 493       $by_day[$key] = ltrim($value, '+');
 494     }
 495
 496     $this->byDay = array_fuse($by_day);
 497     return $this;
 498   }
 499
 500   public function getByDay() {
 501     return $this->byDay;
 502   }
 503
 504   public function setByMonthDay(array $by_month_day) {
 505     $this->assertByRange('BYMONTHDAY', $by_month_day, -31, 31, false);
 506     $this->byMonthDay = array_fuse($by_month_day);
 507     return $this;
 508   }
 509
 510   public function getByMonthDay() {
 511     return $this->byMonthDay;
 512   }
 513
 514   public function setByYearDay($by_year_day) {
 515     $this->assertByRange('BYYEARDAY', $by_year_day, -366, 366, false);
 516     $this->byYearDay = array_fuse($by_year_day);
 517     return $this;
 518   }
 519
 520   public function getByYearDay() {
 521     return $this->byYearDay;
 522   }
 523
 524   public function setByMonth(array $by_month) {
 525     $this->assertByRange('BYMONTH', $by_month, 1, 12);
 526     $this->byMonth = array_fuse($by_month);
 527     return $this;
 528   }
 529
 530   public function getByMonth() {
 531     return $this->byMonth;
 532   }
 533
 534   public function setByWeekNumber(array $by_week_number) {
 535     $this->assertByRange('BYWEEKNO', $by_week_number, -53, 53, false);
 536     $this->byWeekNumber = array_fuse($by_week_number);
 537     return $this;
 538   }
 539
 540   public function getByWeekNumber() {
 541     return $this->byWeekNumber;
 542   }
 543
 544   public function setBySetPosition(array $by_set_position) {
 545     $this->assertByRange('BYSETPOS', $by_set_position, -366, 366, false);
 546     $this->bySetPosition = $by_set_position;
 547     return $this;
 548   }
 549
 550   public function getBySetPosition() {
 551     return $this->bySetPosition;
 552   }
 553
 554   public function setWeekStart($week_start) {
 555     // Make sure this is a valid weekday constant.
 556     self::getWeekdayIndex($week_start);
 557
 558     $this->weekStart = $week_start;
 559     return $this;
 560   }
 561
 562   public function getWeekStart() {
 563     return $this->weekStart;
 564   }
 565
 566   public function resetSource() {
 567     $frequency = $this->getFrequency();
 568
 569     if ($this->getByMonthDay()) {
 570       switch ($frequency) {
 571         case self::FREQUENCY_WEEKLY:
 572           // RFC5545: "The BYMONTHDAY rule part MUST NOT be specified when the
 573           // FREQ rule part is set to WEEKLY."
 574           throw new Exception(
 575             pht(
 576               'RRULE specifies BYMONTHDAY with FREQ set to WEEKLY, which '.
 577               'violates RFC5545.'));
 578           break;
 579         default:
 580           break;
 581       }
 582
 583     }
 584
 585     if ($this->getByYearDay()) {
 586       switch ($frequency) {
 587         case self::FREQUENCY_DAILY:
 588         case self::FREQUENCY_WEEKLY:
 589         case self::FREQUENCY_MONTHLY:
 590           // RFC5545: "The BYYEARDAY rule part MUST NOT be specified when the
 591           // FREQ rule part is set to DAILY, WEEKLY, or MONTHLY."
 592           throw new Exception(
 593             pht(
 594               'RRULE specifies BYYEARDAY with FREQ of DAILY, WEEKLY or '.
 595               'MONTHLY, which violates RFC5545.'));
 596         default:
 597           break;
 598       }
 599     }
 600
 601     // TODO
 602     // RFC5545: "The BYDAY rule part MUST NOT be specified with a numeric
 603     // value when the FREQ rule part is not set to MONTHLY or YEARLY."
 604     // RFC5545: "Furthermore, the BYDAY rule part MUST NOT be specified with a
 605     // numeric value with the FREQ rule part set to YEARLY when the BYWEEKNO
 606     // rule part is specified."
 607
 608
 609     $date = $this->getStartDateTime();
 610
 611     $this->cursorSecond = $date->getSecond();
 612     $this->cursorMinute = $date->getMinute();
 613     $this->cursorHour = $date->getHour();
 614
 615     $this->cursorDay = $date->getDay();
 616     $this->cursorMonth = $date->getMonth();
 617     $this->cursorYear = $date->getYear();
 618
 619     $year_map = $this->getYearMap($this->cursorYear, $this->getWeekStart());
 620     $key = $this->cursorMonth.'M'.$this->cursorDay.'D';
 621     $this->cursorWeek = $year_map['info'][$key]['week'];
 622     $this->cursorWeekday = $year_map['info'][$key]['weekday'];
 623
 624     $this->setSeconds = array();
 625     $this->setMinutes = array();
 626     $this->setHours = array();
 627     $this->setDays = array();
 628     $this->setMonths = array();
 629     $this->setYears = array();
 630
 631     $this->stateSecond = null;
 632     $this->stateMinute = null;
 633     $this->stateHour = null;
 634     $this->stateDay = null;
 635     $this->stateWeek = null;
 636     $this->stateMonth = null;
 637     $this->stateYear = null;
 638
 639     // If we have a BYSETPOS, we need to generate the entire set before we
 640     // can filter it and return results. Normally, we start generating at
 641     // the start date, but we need to go back one interval to generate
 642     // BYSETPOS events so we can make sure the entire set is generated.
 643     if ($this->getBySetPosition()) {
 644       $interval = $this->getInterval();
 645       switch ($frequency) {
 646         case self::FREQUENCY_YEARLY:
 647           $this->cursorYear -= $interval;
 648           break;
 649         case self::FREQUENCY_MONTHLY:
 650           $this->cursorMonth -= $interval;
 651           $this->rewindMonth();
 652           break;
 653         case self::FREQUENCY_WEEKLY:
 654           $this->cursorWeek -= $interval;
 655           $this->rewindWeek();
 656           break;
 657         case self::FREQUENCY_DAILY:
 658           $this->cursorDay -= $interval;
 659           $this->rewindDay();
 660           break;
 661         case self::FREQUENCY_HOURLY:
 662           $this->cursorHour -= $interval;
 663           $this->rewindHour();
 664           break;
 665         case self::FREQUENCY_MINUTELY:
 666           $this->cursorMinute -= $interval;
 667           $this->rewindMinute();
 668           break;
 669         case self::FREQUENCY_SECONDLY:
 670         default:
 671           throw new Exception(
 672             pht(
 673               'RRULE specifies BYSETPOS with FREQ "%s", but this is invalid.',
 674               $frequency));
 675       }
 676     }
 677
 678     // We can generate events from before the cursor when evaluating rules
 679     // with BYSETPOS or FREQ=WEEKLY.
 680     $this->minimumEpoch = $this->getStartDateTime()->getEpoch();
 681
 682     $cursor_state = array(
 683       'year' => $this->cursorYear,
 684       'month' => $this->cursorMonth,
 685       'week' => $this->cursorWeek,
 686       'day' => $this->cursorDay,
 687       'hour' => $this->cursorHour,
 688     );
 689
 690     $this->cursorDayState = $cursor_state;
 691     $this->cursorWeekState = $cursor_state;
 692     $this->cursorHourState = $cursor_state;
 693
 694     $by_hour = $this->getByHour();
 695     $by_minute = $this->getByMinute();
 696     $by_second = $this->getBySecond();
 697
 698     $scale = $this->getFrequencyScale();
 699
 700     // We return all-day events if the start date is an all-day event and we
 701     // don't have more granular selectors or a more granular frequency.
 702     $this->isAllDay = $date->getIsAllDay()
 703       && !$by_hour
 704       && !$by_minute
 705       && !$by_second
 706       && ($scale > self::SCALE_HOURLY);
 707   }
 708
 709   public function getNextEvent($cursor) {
 710     while (true) {
 711       $event = $this->generateNextEvent();
 712       if (!$event) {
 713         break;
 714       }
 715
 716       $epoch = $event->getEpoch();
 717       if ($this->minimumEpoch) {
 718         if ($epoch < $this->minimumEpoch) {
 719           continue;
 720         }
 721       }
 722
 723       if ($epoch < $cursor) {
 724         continue;
 725       }
 726
 727       break;
 728     }
 729
 730     return $event;
 731   }
 732
 733   private function generateNextEvent() {
 734     if ($this->activeSet) {
 735       return array_pop($this->activeSet);
 736     }
 737
 738     $this->baseYear = $this->cursorYear;
 739
 740     $by_setpos = $this->getBySetPosition();
 741     if ($by_setpos) {
 742       $old_state = $this->getSetPositionState();
 743     }
 744
 745     while (!$this->activeSet) {
 746       $this->activeSet = $this->nextSet;
 747       $this->nextSet = array();
 748
 749       while (true) {
 750         if ($this->isAllDay) {
 751           $this->nextDay();
 752         } else {
 753           $this->nextSecond();
 754         }
 755
 756         $result = id(new PhutilCalendarAbsoluteDateTime())
 757           ->setTimezone($this->getStartDateTime()->getTimezone())
 758           ->setViewerTimezone($this->getViewerTimezone())
 759           ->setYear($this->stateYear)
 760           ->setMonth($this->stateMonth)
 761           ->setDay($this->stateDay);
 762
 763         if ($this->isAllDay) {
 764           $result->setIsAllDay(true);
 765         } else {
 766           $result
 767             ->setHour($this->stateHour)
 768             ->setMinute($this->stateMinute)
 769             ->setSecond($this->stateSecond);
 770         }
 771
 772         // If we don't have BYSETPOS, we're all done. We put this into the
 773         // set and will immediately return it.
 774         if (!$by_setpos) {
 775           $this->activeSet[] = $result;
 776           break;
 777         }
 778
 779         // Otherwise, check if we've completed a set. The set is complete if
 780         // the state has moved past the span we were examining (for example,
 781         // with a YEARLY event, if the state is now in the next year).
 782         $new_state = $this->getSetPositionState();
 783         if ($new_state == $old_state) {
 784           $this->activeSet[] = $result;
 785           continue;
 786         }
 787
 788         $this->activeSet = $this->applySetPos($this->activeSet, $by_setpos);
 789         $this->activeSet = array_reverse($this->activeSet);
 790         $this->nextSet[] = $result;
 791         $old_state = $new_state;
 792         break;
 793       }
 794     }
 795
 796     return array_pop($this->activeSet);
 797   }
 798
 799
 800   protected function nextSecond() {
 801     if ($this->setSeconds) {
 802       $this->stateSecond = array_pop($this->setSeconds);
 803       return;
 804     }
 805
 806     $frequency = $this->getFrequency();
 807     $interval = $this->getInterval();
 808     $is_secondly = ($frequency == self::FREQUENCY_SECONDLY);
 809     $by_second = $this->getBySecond();
 810
 811     while (!$this->setSeconds) {
 812       $this->nextMinute();
 813
 814       if ($is_secondly || $by_second) {
 815         $seconds = $this->newSecondsSet(
 816           ($is_secondly ? $interval : 1),
 817           $by_second);
 818       } else {
 819         $seconds = array(
 820           $this->cursorSecond,
 821         );
 822       }
 823
 824       $this->setSeconds = array_reverse($seconds);
 825     }
 826
 827     $this->stateSecond = array_pop($this->setSeconds);
 828   }
 829
 830   protected function nextMinute() {
 831     if ($this->setMinutes) {
 832       $this->stateMinute = array_pop($this->setMinutes);
 833       return;
 834     }
 835
 836     $frequency = $this->getFrequency();
 837     $interval = $this->getInterval();
 838     $scale = $this->getFrequencyScale();
 839     $is_minutely = ($frequency === self::FREQUENCY_MINUTELY);
 840     $by_minute = $this->getByMinute();
 841
 842     while (!$this->setMinutes) {
 843       $this->nextHour();
 844
 845       if ($is_minutely || $by_minute) {
 846         $minutes = $this->newMinutesSet(
 847           ($is_minutely ? $interval : 1),
 848           $by_minute);
 849       } else if ($scale < self::SCALE_MINUTELY) {
 850         $minutes = $this->newMinutesSet(
 851           1,
 852           array());
 853       } else {
 854         $minutes = array(
 855           $this->cursorMinute,
 856         );
 857       }
 858
 859       $this->setMinutes = array_reverse($minutes);
 860     }
 861
 862     $this->stateMinute = array_pop($this->setMinutes);
 863   }
 864
 865   protected function nextHour() {
 866     if ($this->setHours) {
 867       $this->stateHour = array_pop($this->setHours);
 868       return;
 869     }
 870
 871     $frequency = $this->getFrequency();
 872     $interval = $this->getInterval();
 873     $scale = $this->getFrequencyScale();
 874     $is_hourly = ($frequency === self::FREQUENCY_HOURLY);
 875     $by_hour = $this->getByHour();
 876
 877     while (!$this->setHours) {
 878       $this->nextDay();
 879
 880       $is_dynamic = $is_hourly
 881         || $by_hour
 882         || ($scale < self::SCALE_HOURLY);
 883
 884       if ($is_dynamic) {
 885         $hours = $this->newHoursSet(
 886           ($is_hourly ? $interval : 1),
 887           $by_hour);
 888       } else {
 889         $hours = array(
 890           $this->cursorHour,
 891         );
 892       }
 893
 894       $this->setHours = array_reverse($hours);
 895     }
 896
 897     $this->stateHour = array_pop($this->setHours);
 898   }
 899
 900   protected function nextDay() {
 901     if ($this->setDays) {
 902       $info = array_pop($this->setDays);
 903       $this->setDayState($info);
 904       return;
 905     }
 906
 907     $frequency = $this->getFrequency();
 908     $interval = $this->getInterval();
 909     $scale = $this->getFrequencyScale();
 910     $is_daily = ($frequency === self::FREQUENCY_DAILY);
 911     $is_weekly = ($frequency === self::FREQUENCY_WEEKLY);
 912
 913     $by_day = $this->getByDay();
 914     $by_monthday = $this->getByMonthDay();
 915     $by_yearday = $this->getByYearDay();
 916     $by_weekno = $this->getByWeekNumber();
 917     $by_month = $this->getByMonth();
 918     $week_start = $this->getWeekStart();
 919
 920     while (!$this->setDays) {
 921       if ($is_weekly) {
 922         $this->nextWeek();
 923       } else {
 924         $this->nextMonth();
 925       }
 926
 927       // NOTE: We normally handle BYMONTH when iterating months, but it acts
 928       // like a filter if FREQ=WEEKLY.
 929
 930       $is_dynamic = $is_daily
 931         || $is_weekly
 932         || $by_day
 933         || $by_monthday
 934         || $by_yearday
 935         || $by_weekno
 936         || ($by_month && $is_weekly)
 937         || ($scale < self::SCALE_DAILY);
 938
 939       if ($is_dynamic) {
 940         $weeks = $this->newDaysSet(
 941           ($is_daily ? $interval : 1),
 942           $by_day,
 943           $by_monthday,
 944           $by_yearday,
 945           $by_weekno,
 946           $by_month,
 947           $week_start);
 948       } else {
 949         // The cursor day may not actually exist in the current month, so
 950         // make sure the day is valid before we generate a set which contains
 951         // it.
 952         $year_map = $this->getYearMap($this->stateYear, $week_start);
 953         if ($this->cursorDay > $year_map['monthDays'][$this->stateMonth]) {
 954           $weeks = array(
 955             array(),
 956           );
 957         } else {
 958           $key = $this->stateMonth.'M'.$this->cursorDay.'D';
 959           $weeks = array(
 960             array($year_map['info'][$key]),
 961           );
 962         }
 963       }
 964
 965       // Unpack the weeks into days.
 966       $days = array_mergev($weeks);
 967
 968       $this->setDays = array_reverse($days);
 969     }
 970
 971     $info = array_pop($this->setDays);
 972     $this->setDayState($info);
 973   }
 974
 975   private function setDayState(array $info) {
 976     $this->stateDay = $info['monthday'];
 977     $this->stateWeek = $info['week'];
 978     $this->stateMonth = $info['month'];
 979   }
 980
 981   protected function nextMonth() {
 982     if ($this->setMonths) {
 983       $this->stateMonth = array_pop($this->setMonths);
 984       return;
 985     }
 986
 987     $frequency = $this->getFrequency();
 988     $interval = $this->getInterval();
 989     $scale = $this->getFrequencyScale();
 990     $is_monthly = ($frequency === self::FREQUENCY_MONTHLY);
 991
 992     $by_month = $this->getByMonth();
 993
 994     // If we have a BYMONTHDAY, we consider that set of days in every month.
 995     // For example, "FREQ=YEARLY;BYMONTHDAY=3" means "the third day of every
 996     // month", so we need to expand the month set if the constraint is present.
 997     $by_monthday = $this->getByMonthDay();
 998
 999     // Likewise, we need to generate all months if we have BYYEARDAY or
1000     // BYWEEKNO or BYDAY.
1001     $by_yearday = $this->getByYearDay();
1002     $by_weekno = $this->getByWeekNumber();
1003     $by_day = $this->getByDay();
1004
1005     while (!$this->setMonths) {
1006       $this->nextYear();
1007
1008       $is_dynamic = $is_monthly
1009         || $by_month
1010         || $by_monthday
1011         || $by_yearday
1012         || $by_weekno
1013         || $by_day
1014         || ($scale < self::SCALE_MONTHLY);
1015
1016       if ($is_dynamic) {
1017         $months = $this->newMonthsSet(
1018           ($is_monthly ? $interval : 1),
1019           $by_month);
1020       } else {
1021         $months = array(
1022           $this->cursorMonth,
1023         );
1024       }
1025
1026       $this->setMonths = array_reverse($months);
1027     }
1028
1029     $this->stateMonth = array_pop($this->setMonths);
1030   }
1031
1032   protected function nextWeek() {
1033     if ($this->setWeeks) {
1034       $this->stateWeek = array_pop($this->setWeeks);
1035       return;
1036     }
1037
1038     $frequency = $this->getFrequency();
1039     $interval = $this->getInterval();
1040     $scale = $this->getFrequencyScale();
1041     $by_weekno = $this->getByWeekNumber();
1042
1043     while (!$this->setWeeks) {
1044       $this->nextYear();
1045
1046       $weeks = $this->newWeeksSet(
1047         $interval,
1048         $by_weekno);
1049
1050       $this->setWeeks = array_reverse($weeks);
1051     }
1052
1053     $this->stateWeek = array_pop($this->setWeeks);
1054   }
1055
1056   protected function nextYear() {
1057     $this->stateYear = $this->cursorYear;
1058
1059     $frequency = $this->getFrequency();
1060     $is_yearly = ($frequency === self::FREQUENCY_YEARLY);
1061
1062     if ($is_yearly) {
1063       $interval = $this->getInterval();
1064     } else {
1065       $interval = 1;
1066     }
1067
1068     $this->cursorYear = $this->cursorYear + $interval;
1069
1070     if ($this->cursorYear > ($this->baseYear + 100)) {
1071       throw new Exception(
1072         pht(
1073           'RRULE evaluation failed to generate more events in the next 100 '.
1074           'years. This RRULE is likely invalid or degenerate.'));
1075     }
1076
1077   }
1078
1079   private function newSecondsSet($interval, $set) {
1080     // TODO: This doesn't account for leap seconds. In theory, it probably
1081     // should, although this shouldn't impact any real events.
1082     $seconds_in_minute = 60;
1083
1084     if ($this->cursorSecond >= $seconds_in_minute) {
1085       $this->cursorSecond -= $seconds_in_minute;
1086       return array();
1087     }
1088
1089     list($cursor, $result) = $this->newIteratorSet(
1090       $this->cursorSecond,
1091       $interval,
1092       $set,
1093       $seconds_in_minute);
1094
1095     $this->cursorSecond = ($cursor - $seconds_in_minute);
1096
1097     return $result;
1098   }
1099
1100   private function newMinutesSet($interval, $set) {
1101     // NOTE: This value is legitimately a constant! Amazing!
1102     $minutes_in_hour = 60;
1103
1104     if ($this->cursorMinute >= $minutes_in_hour) {
1105       $this->cursorMinute -= $minutes_in_hour;
1106       return array();
1107     }
1108
1109     list($cursor, $result) = $this->newIteratorSet(
1110       $this->cursorMinute,
1111       $interval,
1112       $set,
1113       $minutes_in_hour);
1114
1115     $this->cursorMinute = ($cursor - $minutes_in_hour);
1116
1117     return $result;
1118   }
1119
1120   private function newHoursSet($interval, $set) {
1121     // TODO: This doesn't account for hours caused by daylight savings time.
1122     // It probably should, although this seems unlikely to impact any real
1123     // events.
1124     $hours_in_day = 24;
1125
1126     // If the hour cursor is behind the current time, we need to forward it in
1127     // INTERVAL increments so we end up with the right offset.
1128     list($skip, $this->cursorHourState) = $this->advanceCursorState(
1129       $this->cursorHourState,
1130       self::SCALE_HOURLY,
1131       $interval,
1132       $this->getWeekStart());
1133
1134     if ($skip) {
1135       return array();
1136     }
1137
1138     list($cursor, $result) = $this->newIteratorSet(
1139       $this->cursorHour,
1140       $interval,
1141       $set,
1142       $hours_in_day);
1143
1144     $this->cursorHour = ($cursor - $hours_in_day);
1145
1146     return $result;
1147   }
1148
1149   private function newWeeksSet($interval, $set) {
1150     $week_start = $this->getWeekStart();
1151
1152     list($skip, $this->cursorWeekState) = $this->advanceCursorState(
1153       $this->cursorWeekState,
1154       self::SCALE_WEEKLY,
1155       $interval,
1156       $week_start);
1157
1158     if ($skip) {
1159       return array();
1160     }
1161
1162     $year_map = $this->getYearMap($this->stateYear, $week_start);
1163
1164     $result = array();
1165     while (true) {
1166       if (!isset($year_map['weekMap'][$this->cursorWeek])) {
1167         break;
1168       }
1169       $result[] = $this->cursorWeek;
1170       $this->cursorWeek += $interval;
1171     }
1172
1173     $this->cursorWeek -= $year_map['weekCount'];
1174
1175     return $result;
1176   }
1177
1178   private function newDaysSet(
1179     $interval_day,
1180     $by_day,
1181     $by_monthday,
1182     $by_yearday,
1183     $by_weekno,
1184     $by_month,
1185     $week_start) {
1186
1187     $frequency = $this->getFrequency();
1188     $is_yearly = ($frequency == self::FREQUENCY_YEARLY);
1189     $is_monthly = ($frequency == self::FREQUENCY_MONTHLY);
1190     $is_weekly = ($frequency == self::FREQUENCY_WEEKLY);
1191
1192     $selection = array();
1193     if ($is_weekly) {
1194       $year_map = $this->getYearMap($this->stateYear, $week_start);
1195
1196       if (isset($year_map['weekMap'][$this->stateWeek])) {
1197         foreach ($year_map['weekMap'][$this->stateWeek] as $key) {
1198           $selection[] = $year_map['info'][$key];
1199         }
1200       }
1201     } else {
1202       // If the day cursor is behind the current year and month, we need to
1203       // forward it in INTERVAL increments so we end up with the right offset
1204       // in the current month.
1205       list($skip, $this->cursorDayState) = $this->advanceCursorState(
1206         $this->cursorDayState,
1207         self::SCALE_DAILY,
1208         $interval_day,
1209         $week_start);
1210
1211       if (!$skip) {
1212         $year_map = $this->getYearMap($this->stateYear, $week_start);
1213         while (true) {
1214           $month_idx = $this->stateMonth;
1215           $month_days = $year_map['monthDays'][$month_idx];
1216           if ($this->cursorDay > $month_days) {
1217             // NOTE: The year map is now out of date, but we're about to break
1218             // out of the loop anyway so it doesn't matter.
1219             break;
1220           }
1221
1222           $day_idx = $this->cursorDay;
1223
1224           $key = "{$month_idx}M{$day_idx}D";
1225           $selection[] = $year_map['info'][$key];
1226
1227           $this->cursorDay += $interval_day;
1228         }
1229       }
1230     }
1231
1232     // As a special case, BYDAY applies to relative month offsets if BYMONTH
1233     // is present in a YEARLY rule.
1234     if ($is_yearly) {
1235       if ($this->getByMonth()) {
1236         $is_yearly = false;
1237         $is_monthly = true;
1238       }
1239     }
1240
1241     // As a special case, BYDAY makes us examine all week days. This doesn't
1242     // check BYMONTHDAY or BYYEARDAY because they are not valid with WEEKLY.
1243     $filter_weekday = true;
1244     if ($is_weekly) {
1245       if ($by_day) {
1246         $filter_weekday = false;
1247       }
1248     }
1249
1250     $weeks = array();
1251     foreach ($selection as $key => $info) {
1252       if ($is_weekly) {
1253         if ($filter_weekday) {
1254           if ($info['weekday'] != $this->cursorWeekday) {
1255             continue;
1256           }
1257         }
1258       } else {
1259         if ($info['month'] != $this->stateMonth) {
1260           continue;
1261         }
1262       }
1263
1264       if ($by_day) {
1265         if (empty($by_day[$info['weekday']])) {
1266           if ($is_yearly) {
1267             if (empty($by_day[$info['weekday.yearly']]) &&
1268                 empty($by_day[$info['-weekday.yearly']])) {
1269               continue;
1270             }
1271           } else if ($is_monthly) {
1272             if (empty($by_day[$info['weekday.monthly']]) &&
1273                 empty($by_day[$info['-weekday.monthly']])) {
1274               continue;
1275             }
1276           } else {
1277             continue;
1278           }
1279         }
1280       }
1281
1282       if ($by_monthday) {
1283         if (empty($by_monthday[$info['monthday']]) &&
1284             empty($by_monthday[$info['-monthday']])) {
1285           continue;
1286         }
1287       }
1288
1289       if ($by_yearday) {
1290         if (empty($by_yearday[$info['yearday']]) &&
1291             empty($by_yearday[$info['-yearday']])) {
1292           continue;
1293         }
1294       }
1295
1296       if ($by_weekno) {
1297         if (empty($by_weekno[$info['week']]) &&
1298             empty($by_weekno[$info['-week']])) {
1299           continue;
1300         }
1301       }
1302
1303       if ($by_month) {
1304         if (empty($by_month[$info['month']])) {
1305           continue;
1306         }
1307       }
1308
1309       $weeks[$info['week']][] = $info;
1310     }
1311
1312     return array_values($weeks);
1313   }
1314
1315   private function newMonthsSet($interval, $set) {
1316     // NOTE: This value is also a real constant! Wow!
1317     $months_in_year = 12;
1318
1319     if ($this->cursorMonth > $months_in_year) {
1320       $this->cursorMonth -= $months_in_year;
1321       return array();
1322     }
1323
1324     list($cursor, $result) = $this->newIteratorSet(
1325       $this->cursorMonth,
1326       $interval,
1327       $set,
1328       $months_in_year + 1);
1329
1330     $this->cursorMonth = ($cursor - $months_in_year);
1331
1332     return $result;
1333   }
1334
1335   public static function getYearMap($year, $week_start) {
1336     static $maps = array();
1337
1338     $key = "{$year}/{$week_start}";
1339     if (isset($maps[$key])) {
1340       return $maps[$key];
1341     }
1342
1343     $map = self::newYearMap($year, $week_start);
1344     $maps[$key] = $map;
1345
1346     return $maps[$key];
1347   }
1348
1349   private static function newYearMap($year, $weekday_start) {
1350     $weekday_index = self::getWeekdayIndex($weekday_start);
1351
1352     $is_leap = (($year % 4 === 0) && ($year % 100 !== 0)) ||
1353                ($year % 400 === 0);
1354
1355     // There may be some clever way to figure out which day of the week a given
1356     // year starts on and avoid the cost of a DateTime construction, but I
1357     // wasn't able to turn it up and we only need to do this once per year.
1358     $datetime = new DateTime("{$year}-01-01", new DateTimeZone('UTC'));
1359     $weekday = (int)$datetime->format('w');
1360
1361     if ($is_leap) {
1362       $max_day = 366;
1363     } else {
1364       $max_day = 365;
1365     }
1366
1367     $month_days = array(
1368       1 => 31,
1369       2 => $is_leap ? 29 : 28,
1370       3 => 31,
1371       4 => 30,
1372       5 => 31,
1373       6 => 30,
1374       7 => 31,
1375       8 => 31,
1376       9 => 30,
1377       10 => 31,
1378       11 => 30,
1379       12 => 31,
1380     );
1381
1382     // Per the spec, the first week of the year must contain at least four
1383     // days. If the week starts on a Monday but the year starts on a Saturday,
1384     // the first couple of days don't count as a week. In this case, the first
1385     // week will begin on January 3.
1386     $first_week_size = 0;
1387     $first_weekday = $weekday;
1388     for ($year_day = 1; $year_day <= $max_day; $year_day++) {
1389       $first_weekday = ($first_weekday + 1) % 7;
1390       $first_week_size++;
1391       if ($first_weekday === $weekday_index) {
1392         break;
1393       }
1394     }
1395
1396     if ($first_week_size >= 4) {
1397       $week_number = 1;
1398     } else {
1399       $week_number = 0;
1400     }
1401
1402     $info_map = array();
1403
1404     $weekday_map = self::getWeekdayIndexMap();
1405     $weekday_map = array_flip($weekday_map);
1406
1407     $yearly_counts = array();
1408     $monthly_counts = array();
1409
1410     $month_number = 1;
1411     $month_day = 1;
1412     for ($year_day = 1; $year_day <= $max_day; $year_day++) {
1413       $key = "{$month_number}M{$month_day}D";
1414
1415       $short_day = $weekday_map[$weekday];
1416       if (empty($yearly_counts[$short_day])) {
1417         $yearly_counts[$short_day] = 0;
1418       }
1419       $yearly_counts[$short_day]++;
1420
1421       if (empty($monthly_counts[$month_number][$short_day])) {
1422         $monthly_counts[$month_number][$short_day] = 0;
1423       }
1424       $monthly_counts[$month_number][$short_day]++;
1425
1426       $info = array(
1427         'year' => $year,
1428         'key' => $key,
1429         'month' => $month_number,
1430         'monthday' => $month_day,
1431         '-monthday' => -$month_days[$month_number] + $month_day - 1,
1432         'yearday' => $year_day,
1433         '-yearday' => -$max_day + $year_day - 1,
1434         'week' => $week_number,
1435         'weekday' => $short_day,
1436         'weekday.yearly' => $yearly_counts[$short_day],
1437         'weekday.monthly' => $monthly_counts[$month_number][$short_day],
1438       );
1439
1440       $info_map[$key] = $info;
1441
1442       $weekday = ($weekday + 1) % 7;
1443       if ($weekday === $weekday_index) {
1444         $week_number++;
1445       }
1446
1447       $month_day = ($month_day + 1);
1448       if ($month_day > $month_days[$month_number]) {
1449         $month_day = 1;
1450         $month_number++;
1451       }
1452     }
1453
1454     // Check how long the final week is. If it doesn't have four days, this
1455     // is really the first week of the next year.
1456     $final_week = array();
1457     foreach ($info_map as $key => $info) {
1458       if ($info['week'] == $week_number) {
1459         $final_week[] = $key;
1460       }
1461     }
1462
1463     if (count($final_week) < 4) {
1464       $week_number = $week_number - 1;
1465       $next_year = self::getYearMap($year + 1, $weekday_start);
1466       $next_year_weeks = $next_year['weekCount'];
1467     } else {
1468       $next_year_weeks = null;
1469     }
1470
1471     if ($first_week_size < 4) {
1472       $last_year = self::getYearMap($year - 1, $weekday_start);
1473       $last_year_weeks = $last_year['weekCount'];
1474     } else {
1475       $last_year_weeks = null;
1476     }
1477
1478     // Now that we know how many weeks the year has, we can compute the
1479     // negative offsets.
1480     foreach ($info_map as $key => $info) {
1481       $week = $info['week'];
1482
1483       if ($week === 0) {
1484         // If this day is part of the first partial week of the year, give
1485         // it the week number of the last week of the prior year instead.
1486         $info['week'] = $last_year_weeks;
1487         $info['-week'] = -1;
1488       } else if ($week > $week_number) {
1489         // If this day is part of the last partial week of the year, give
1490         // it week numbers from the next year.
1491         $info['week'] = 1;
1492         $info['-week'] = -$next_year_weeks;
1493       } else {
1494         $info['-week'] = -$week_number + $week - 1;
1495       }
1496
1497       // Do all the arithmetic to figure out if this is the -19th Thursday
1498       // in the year and such.
1499       $month_number = $info['month'];
1500       $short_day = $info['weekday'];
1501       $monthly_count = $monthly_counts[$month_number][$short_day];
1502       $monthly_index = $info['weekday.monthly'];
1503       $info['-weekday.monthly'] = -$monthly_count + $monthly_index - 1;
1504       $info['-weekday.monthly'] .= $short_day;
1505       $info['weekday.monthly'] .= $short_day;
1506
1507       $yearly_count = $yearly_counts[$short_day];
1508       $yearly_index = $info['weekday.yearly'];
1509       $info['-weekday.yearly'] = -$yearly_count + $yearly_index - 1;
1510       $info['-weekday.yearly'] .= $short_day;
1511       $info['weekday.yearly'] .= $short_day;
1512
1513       $info_map[$key] = $info;
1514     }
1515
1516     $week_map = array();
1517     foreach ($info_map as $key => $info) {
1518       $week_map[$info['week']][] = $key;
1519     }
1520
1521     return array(
1522       'info' => $info_map,
1523       'weekCount' => $week_number,
1524       'dayCount' => $max_day,
1525       'monthDays' => $month_days,
1526       'weekMap' => $week_map,
1527     );
1528   }
1529
1530   private function newIteratorSet($cursor, $interval, $set, $limit) {
1531     if ($interval < 1) {
1532       throw new Exception(
1533         pht(
1534           'Invalid iteration interval ("%d"), must be at least 1.',
1535           $interval));
1536     }
1537
1538     $result = array();
1539     $seen = array();
1540
1541     $ii = $cursor;
1542     while (true) {
1543       if (!$set || isset($set[$ii])) {
1544         $result[] = $ii;
1545       }
1546
1547       $ii = ($ii + $interval);
1548
1549       if ($ii >= $limit) {
1550         break;
1551       }
1552     }
1553
1554     sort($result);
1555     $result = array_values($result);
1556
1557     return array($ii, $result);
1558   }
1559
1560   private function applySetPos(array $values, array $setpos) {
1561     $select = array();
1562
1563     $count = count($values);
1564     foreach ($setpos as $pos) {
1565       if ($pos > 0 && $pos <= $count) {
1566         $select[] = ($pos - 1);
1567       } else if ($pos < 0 && $pos >= -$count) {
1568         $select[] = ($count + $pos);
1569       }
1570     }
1571
1572     sort($select);
1573     $select = array_unique($select);
1574
1575     return array_select_keys($values, $select);
1576   }
1577
1578   private function assertByRange(
1579     $source,
1580     array $values,
1581     $min,
1582     $max,
1583     $allow_zero = true) {
1584
1585     foreach ($values as $value) {
1586       if (!is_int($value)) {
1587         throw new Exception(
1588           pht(
1589             'Value "%s" in RRULE "%s" parameter is invalid: values must be '.
1590             'integers.',
1591             $value,
1592             $source));
1593       }
1594
1595       if ($value < $min || $value > $max) {
1596         throw new Exception(
1597           pht(
1598             'Value "%s" in RRULE "%s" parameter is invalid: it must be '.
1599             'between %s and %s.',
1600             $value,
1601             $source,
1602             $min,
1603             $max));
1604       }
1605
1606       if (!$value && !$allow_zero) {
1607         throw new Exception(
1608           pht(
1609             'Value "%s" in RRULE "%s" parameter is invalid: it must not '.
1610             'be zero.',
1611             $value,
1612             $source));
1613       }
1614     }
1615   }
1616
1617   private function getSetPositionState() {
1618     $scale = $this->getFrequencyScale();
1619
1620     $parts = array();
1621     $parts[] = $this->stateYear;
1622
1623     if ($scale == self::SCALE_WEEKLY) {
1624       $parts[] = $this->stateWeek;
1625     } else {
1626       if ($scale < self::SCALE_YEARLY) {
1627         $parts[] = $this->stateMonth;
1628       }
1629       if ($scale < self::SCALE_MONTHLY) {
1630         $parts[] = $this->stateDay;
1631       }
1632       if ($scale < self::SCALE_DAILY) {
1633         $parts[] = $this->stateHour;
1634       }
1635       if ($scale < self::SCALE_HOURLY) {
1636         $parts[] = $this->stateMinute;
1637       }
1638     }
1639
1640     return implode('/', $parts);
1641   }
1642
1643   private function rewindMonth() {
1644     while ($this->cursorMonth < 1) {
1645       $this->cursorYear--;
1646       $this->cursorMonth += 12;
1647     }
1648   }
1649
1650   private function rewindWeek() {
1651     $week_start = $this->getWeekStart();
1652     while ($this->cursorWeek < 1) {
1653       $this->cursorYear--;
1654       $year_map = $this->getYearMap($this->cursorYear, $week_start);
1655       $this->cursorWeek += $year_map['weekCount'];
1656     }
1657   }
1658
1659   private function rewindDay() {
1660     $week_start = $this->getWeekStart();
1661     while ($this->cursorDay < 1) {
1662       $year_map = $this->getYearMap($this->cursorYear, $week_start);
1663       $this->cursorDay += $year_map['monthDays'][$this->cursorMonth];
1664       $this->cursorMonth--;
1665       $this->rewindMonth();
1666     }
1667   }
1668
1669   private function rewindHour() {
1670     while ($this->cursorHour < 0) {
1671       $this->cursorHour += 24;
1672       $this->cursorDay--;
1673       $this->rewindDay();
1674     }
1675   }
1676
1677   private function rewindMinute() {
1678     while ($this->cursorMinute < 0) {
1679       $this->cursorMinute += 60;
1680       $this->cursorHour--;
1681       $this->rewindHour();
1682     }
1683   }
1684
1685   private function advanceCursorState(
1686     array $cursor,
1687     $scale,
1688     $interval,
1689     $week_start) {
1690
1691     $state = array(
1692       'year' => $this->stateYear,
1693       'month' => $this->stateMonth,
1694       'week' => $this->stateWeek,
1695       'day' => $this->stateDay,
1696       'hour' => $this->stateHour,
1697     );
1698
1699     // In the common case when the interval is 1, we'll visit every possible
1700     // value so we don't need to do any math and can just jump to the first
1701     // hour, day, etc.
1702     if ($interval == 1) {
1703       if ($this->isCursorBehind($cursor, $state, $scale)) {
1704         switch ($scale) {
1705           case self::SCALE_DAILY:
1706             $this->cursorDay = 1;
1707             break;
1708           case self::SCALE_HOURLY:
1709             $this->cursorHour = 0;
1710             break;
1711           case self::SCALE_WEEKLY:
1712             $this->cursorWeek = 1;
1713             break;
1714         }
1715       }
1716
1717       return array(false, $state);
1718     }
1719
1720     $year_map = $this->getYearMap($cursor['year'], $week_start);
1721     while ($this->isCursorBehind($cursor, $state, $scale)) {
1722       switch ($scale) {
1723         case self::SCALE_DAILY:
1724           $cursor['day'] += $interval;
1725           break;
1726         case self::SCALE_HOURLY:
1727           $cursor['hour'] += $interval;
1728           break;
1729         case self::SCALE_WEEKLY:
1730           $cursor['week'] += $interval;
1731           break;
1732       }
1733
1734       if ($scale <= self::SCALE_HOURLY) {
1735         while ($cursor['hour'] >= 24) {
1736           $cursor['hour'] -= 24;
1737           $cursor['day']++;
1738         }
1739       }
1740
1741       if ($scale == self::SCALE_WEEKLY) {
1742         while ($cursor['week'] > $year_map['weekCount']) {
1743           $cursor['week'] -= $year_map['weekCount'];
1744           $cursor['year']++;
1745           $year_map = $this->getYearMap($cursor['year'], $week_start);
1746         }
1747       }
1748
1749       if ($scale <= self::SCALE_DAILY) {
1750         while ($cursor['day'] > $year_map['monthDays'][$cursor['month']]) {
1751           $cursor['day'] -= $year_map['monthDays'][$cursor['month']];
1752           $cursor['month']++;
1753           if ($cursor['month'] > 12) {
1754             $cursor['month'] -= 12;
1755             $cursor['year']++;
1756             $year_map = $this->getYearMap($cursor['year'], $week_start);
1757           }
1758         }
1759       }
1760     }
1761
1762     switch ($scale) {
1763       case self::SCALE_DAILY:
1764         $this->cursorDay = $cursor['day'];
1765         break;
1766       case self::SCALE_HOURLY:
1767         $this->cursorHour = $cursor['hour'];
1768         break;
1769       case self::SCALE_WEEKLY:
1770         $this->cursorWeek = $cursor['week'];
1771         break;
1772     }
1773
1774     $skip = $this->isCursorBehind($state, $cursor, $scale);
1775
1776     return array($skip, $cursor);
1777   }
1778
1779   private function isCursorBehind(array $cursor, array $state, $scale) {
1780     if ($cursor['year'] < $state['year']) {
1781       return true;
1782     } else if ($cursor['year'] > $state['year']) {
1783       return false;
1784     }
1785
1786     if ($scale == self::SCALE_WEEKLY) {
1787       return false;
1788     }
1789
1790     if ($cursor['month'] < $state['month']) {
1791       return true;
1792     } else if ($cursor['month'] > $state['month']) {
1793       return false;
1794     }
1795
1796     if ($scale >= self::SCALE_DAILY) {
1797       return false;
1798     }
1799
1800     if ($cursor['day'] < $state['day']) {
1801       return true;
1802     } else if ($cursor['day'] > $state['day']) {
1803       return false;
1804     }
1805
1806     if ($scale >= self::SCALE_HOURLY) {
1807       return false;
1808     }
1809
1810     if ($cursor['hour'] < $state['hour']) {
1811       return true;
1812     } else if ($cursor['hour'] > $state['hour']) {
1813       return false;
1814     }
1815
1816     return false;
1817   }
1818
1819
1820 }