Differential D20774 Diff 49536 src/applications/calendar/parser/data/PhutilCalendarRecurrenceRule.php

Changeset View

Standalone View

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

This file was added.

				<?php

				final class PhutilCalendarRecurrenceRule
				extends PhutilCalendarRecurrenceSource {

				private $startDateTime;
				private $frequency;
				private $frequencyScale;
				private $interval = 1;
				private $bySecond = array();
				private $byMinute = array();
				private $byHour = array();
				private $byDay = array();
				private $byMonthDay = array();
				private $byYearDay = array();
				private $byWeekNumber = array();
				private $byMonth = array();
				private $bySetPosition = array();
				private $weekStart = self::WEEKDAY_MONDAY;
				private $count;
				private $until;

				private $cursorSecond;
				private $cursorMinute;
				private $cursorHour;
				private $cursorHourState;
				private $cursorWeek;
				private $cursorWeekday;
				private $cursorWeekState;
				private $cursorDay;
				private $cursorDayState;
				private $cursorMonth;
				private $cursorYear;

				private $setSeconds;
				private $setMinutes;
				private $setHours;
				private $setDays;
				private $setMonths;
				private $setWeeks;
				private $setYears;

				private $stateSecond;
				private $stateMinute;
				private $stateHour;
				private $stateDay;
				private $stateWeek;
				private $stateMonth;
				private $stateYear;

				private $baseYear;
				private $isAllDay;
				private $activeSet = array();
				private $nextSet = array();
				private $minimumEpoch;

				const FREQUENCY_SECONDLY = 'SECONDLY';
				const FREQUENCY_MINUTELY = 'MINUTELY';
				const FREQUENCY_HOURLY = 'HOURLY';
				const FREQUENCY_DAILY = 'DAILY';
				const FREQUENCY_WEEKLY = 'WEEKLY';
				const FREQUENCY_MONTHLY = 'MONTHLY';
				const FREQUENCY_YEARLY = 'YEARLY';

				const SCALE_SECONDLY = 1;
				const SCALE_MINUTELY = 2;
				const SCALE_HOURLY = 3;
				const SCALE_DAILY = 4;
				const SCALE_WEEKLY = 5;
				const SCALE_MONTHLY = 6;
				const SCALE_YEARLY = 7;

				const WEEKDAY_SUNDAY = 'SU';
				const WEEKDAY_MONDAY = 'MO';
				const WEEKDAY_TUESDAY = 'TU';
				const WEEKDAY_WEDNESDAY = 'WE';
				const WEEKDAY_THURSDAY = 'TH';
				const WEEKDAY_FRIDAY = 'FR';
				const WEEKDAY_SATURDAY = 'SA';

				const WEEKINDEX_SUNDAY = 0;
				const WEEKINDEX_MONDAY = 1;
				const WEEKINDEX_TUESDAY = 2;
				const WEEKINDEX_WEDNESDAY = 3;
				const WEEKINDEX_THURSDAY = 4;
				const WEEKINDEX_FRIDAY = 5;
				const WEEKINDEX_SATURDAY = 6;

				public function toDictionary() {
				$parts = array();

				$parts['FREQ'] = $this->getFrequency();

				$interval = $this->getInterval();
				if ($interval != 1) {
				$parts['INTERVAL'] = $interval;
				}

				$by_second = $this->getBySecond();
				if ($by_second) {
				$parts['BYSECOND'] = $by_second;
				}

				$by_minute = $this->getByMinute();
				if ($by_minute) {
				$parts['BYMINUTE'] = $by_minute;
				}

				$by_hour = $this->getByHour();
				if ($by_hour) {
				$parts['BYHOUR'] = $by_hour;
				}

				$by_day = $this->getByDay();
				if ($by_day) {
				$parts['BYDAY'] = $by_day;
				}

				$by_month = $this->getByMonth();
				if ($by_month) {
				$parts['BYMONTH'] = $by_month;
				}

				$by_monthday = $this->getByMonthDay();
				if ($by_monthday) {
				$parts['BYMONTHDAY'] = $by_monthday;
				}

				$by_yearday = $this->getByYearDay();
				if ($by_yearday) {
				$parts['BYYEARDAY'] = $by_yearday;
				}

				$by_weekno = $this->getByWeekNumber();
				if ($by_weekno) {
				$parts['BYWEEKNO'] = $by_weekno;
				}

				$by_setpos = $this->getBySetPosition();
				if ($by_setpos) {
				$parts['BYSETPOS'] = $by_setpos;
				}

				$wkst = $this->getWeekStart();
				if ($wkst != self::WEEKDAY_MONDAY) {
				$parts['WKST'] = $wkst;
				}

				$count = $this->getCount();
				if ($count) {
				$parts['COUNT'] = $count;
				}

				$until = $this->getUntil();
				if ($until) {
				$parts['UNTIL'] = $until->getISO8601();
				}

				return $parts;
				}

				public static function newFromDictionary(array $dict) {
				static $expect;
				if ($expect === null) {
				$expect = array_fuse(
				array(
				'FREQ',
				'INTERVAL',
				'BYSECOND',
				'BYMINUTE',
				'BYHOUR',
				'BYDAY',
				'BYMONTH',
				'BYMONTHDAY',
				'BYYEARDAY',
				'BYWEEKNO',
				'BYSETPOS',
				'WKST',
				'UNTIL',
				'COUNT',
				));
				}

				foreach ($dict as $key => $value) {
				if (empty($expect[$key])) {
				throw new Exception(
				pht(
				'RRULE dictionary includes unknown key "%s". Expected keys '.
				'are: %s.',
				$key,
				implode(', ', array_keys($expect))));
				}
				}

				$rrule = id(new self())
				->setFrequency(idx($dict, 'FREQ'))
				->setInterval(idx($dict, 'INTERVAL', 1))
				->setBySecond(idx($dict, 'BYSECOND', array()))
				->setByMinute(idx($dict, 'BYMINUTE', array()))
				->setByHour(idx($dict, 'BYHOUR', array()))
				->setByDay(idx($dict, 'BYDAY', array()))
				->setByMonth(idx($dict, 'BYMONTH', array()))
				->setByMonthDay(idx($dict, 'BYMONTHDAY', array()))
				->setByYearDay(idx($dict, 'BYYEARDAY', array()))
				->setByWeekNumber(idx($dict, 'BYWEEKNO', array()))
				->setBySetPosition(idx($dict, 'BYSETPOS', array()))
				->setWeekStart(idx($dict, 'WKST', self::WEEKDAY_MONDAY));

				$count = idx($dict, 'COUNT');
				if ($count) {
				$rrule->setCount($count);
				}

				$until = idx($dict, 'UNTIL');
				if ($until) {
				$until = PhutilCalendarAbsoluteDateTime::newFromISO8601($until);
				$rrule->setUntil($until);
				}

				return $rrule;
				}

				public function toRRULE() {
				$dict = $this->toDictionary();

				$parts = array();
				foreach ($dict as $key => $value) {
				if (is_array($value)) {
				$value = implode(',', $value);
				}
				$parts[] = "{$key}={$value}";
				}

				return implode(';', $parts);
				}

				public static function newFromRRULE($rrule) {
				$parts = explode(';', $rrule);

				$dict = array();
				foreach ($parts as $part) {
				list($key, $value) = explode('=', $part, 2);
				switch ($key) {
				case 'FREQ':
				case 'INTERVAL':
				case 'WKST':
				case 'COUNT':
				case 'UNTIL';
				break;
				default:
				$value = explode(',', $value);
				break;
				}
				$dict[$key] = $value;
				}

				$int_lists = array_fuse(
				array(
				// NOTE: "BYDAY" is absent, and takes a list like "MO, TU, WE".
				'BYSECOND',
				'BYMINUTE',
				'BYHOUR',
				'BYMONTH',
				'BYMONTHDAY',
				'BYYEARDAY',
				'BYWEEKNO',
				'BYSETPOS',
				));

				$int_values = array_fuse(
				array(
				'COUNT',
				'INTERVAL',
				));

				foreach ($dict as $key => $value) {
				if (isset($int_values[$key])) {
				// None of these values may be negative.
				if (!preg_match('/^\d+\z/', $value)) {
				throw new Exception(
				pht(
				'Unexpected value "%s" in "%s" RULE property: expected an '.
				'integer.',
				$value,
				$key));
				}
				$dict[$key] = (int)$value;
				}

				if (isset($int_lists[$key])) {
				foreach ($value as $k => $v) {
				if (!preg_match('/^-?\d+\z/', $v)) {
				throw new Exception(
				pht(
				'Unexpected value "%s" in "%s" RRULE property: expected '.
				'only integers.',
				$v,
				$key));
				}
				$value[$k] = (int)$v;
				}
				$dict[$key] = $value;
				}
				}

				return self::newFromDictionary($dict);
				}

				private static function getAllWeekdayConstants() {
				return array_keys(self::getWeekdayIndexMap());
				}

				private static function getWeekdayIndexMap() {
				static $map = array(
				self::WEEKDAY_SUNDAY => self::WEEKINDEX_SUNDAY,
				self::WEEKDAY_MONDAY => self::WEEKINDEX_MONDAY,
				self::WEEKDAY_TUESDAY => self::WEEKINDEX_TUESDAY,
				self::WEEKDAY_WEDNESDAY => self::WEEKINDEX_WEDNESDAY,
				self::WEEKDAY_THURSDAY => self::WEEKINDEX_THURSDAY,
				self::WEEKDAY_FRIDAY => self::WEEKINDEX_FRIDAY,
				self::WEEKDAY_SATURDAY => self::WEEKINDEX_SATURDAY,
				);

				return $map;
				}

				private static function getWeekdayIndex($weekday) {
				$map = self::getWeekdayIndexMap();
				if (!isset($map[$weekday])) {
				$constants = array_keys($map);
				throw new Exception(
				pht(
				'Weekday "%s" is not a valid weekday constant. Valid constants '.
				'are: %s.',
				$weekday,
				implode(', ', $constants)));
				}

				return $map[$weekday];
				}

				public function setStartDateTime(PhutilCalendarDateTime $start) {
				$this->startDateTime = $start;
				return $this;
				}

				public function getStartDateTime() {
				return $this->startDateTime;
				}

				public function setCount($count) {
				if ($count < 1) {
				throw new Exception(
				pht(
				'RRULE COUNT value "%s" is invalid: count must be at least 1.',
				$count));
				}

				$this->count = $count;
				return $this;
				}

				public function getCount() {
				return $this->count;
				}

				public function setUntil(PhutilCalendarDateTime $until) {
				$this->until = $until;
				return $this;
				}

				public function getUntil() {
				return $this->until;
				}

				public function setFrequency($frequency) {
				static $map = array(
				self::FREQUENCY_SECONDLY => self::SCALE_SECONDLY,
				self::FREQUENCY_MINUTELY => self::SCALE_MINUTELY,
				self::FREQUENCY_HOURLY => self::SCALE_HOURLY,
				self::FREQUENCY_DAILY => self::SCALE_DAILY,
				self::FREQUENCY_WEEKLY => self::SCALE_WEEKLY,
				self::FREQUENCY_MONTHLY => self::SCALE_MONTHLY,
				self::FREQUENCY_YEARLY => self::SCALE_YEARLY,
				);

				if (empty($map[$frequency])) {
				throw new Exception(
				pht(
				'RRULE FREQ "%s" is invalid. Valid frequencies are: %s.',
				$frequency,
				implode(', ', array_keys($map))));
				}

				$this->frequency = $frequency;
				$this->frequencyScale = $map[$frequency];

				return $this;
				}

				public function getFrequency() {
				return $this->frequency;
				}

				public function getFrequencyScale() {
				return $this->frequencyScale;
				}

				public function setInterval($interval) {
				if (!is_int($interval)) {
				throw new Exception(
				pht(
				'RRULE INTERVAL "%s" is invalid: interval must be an integer.',
				$interval));
				}

				if ($interval < 1) {
				throw new Exception(
				pht(
				'RRULE INTERVAL "%s" is invalid: interval must be 1 or more.',
				$interval));
				}

				$this->interval = $interval;
				return $this;
				}

				public function getInterval() {
				return $this->interval;
				}

				public function setBySecond(array $by_second) {
				$this->assertByRange('BYSECOND', $by_second, 0, 60);
				$this->bySecond = array_fuse($by_second);
				return $this;
				}

				public function getBySecond() {
				return $this->bySecond;
				}

				public function setByMinute(array $by_minute) {
				$this->assertByRange('BYMINUTE', $by_minute, 0, 59);
				$this->byMinute = array_fuse($by_minute);
				return $this;
				}

				public function getByMinute() {
				return $this->byMinute;
				}

				public function setByHour(array $by_hour) {
				$this->assertByRange('BYHOUR', $by_hour, 0, 23);
				$this->byHour = array_fuse($by_hour);
				return $this;
				}

				public function getByHour() {
				return $this->byHour;
				}

				public function setByDay(array $by_day) {
				$constants = self::getAllWeekdayConstants();
				$constants = implode('\|', $constants);

				$pattern = '/^(?:[+-]?([1-9]\d?))?('.$constants.')\z/';
				foreach ($by_day as $key => $value) {
				$matches = null;
				if (!preg_match($pattern, $value, $matches)) {
				throw new Exception(
				pht(
				'RRULE BYDAY value "%s" is invalid: rule part must be in the '.
				'expected form (like "MO", "-3TH", or "+2SU").',
				$value));
				}

				// The maximum allowed value is 53, which corresponds to "the 53rd
				// Monday every year" or similar when evaluated against a YEARLY rule.

				$maximum = 53;
				$magnitude = (int)$matches[1];
				if ($magnitude > $maximum) {
				throw new Exception(
				pht(
				'RRULE BYDAY value "%s" has an offset with magnitude "%s", but '.
				'the maximum permitted value is "%s".',
				$value,
				$magnitude,
				$maximum));
				}

				// Normalize "+3FR" into "3FR".
				$by_day[$key] = ltrim($value, '+');
				}

				$this->byDay = array_fuse($by_day);
				return $this;
				}

				public function getByDay() {
				return $this->byDay;
				}

				public function setByMonthDay(array $by_month_day) {
				$this->assertByRange('BYMONTHDAY', $by_month_day, -31, 31, false);
				$this->byMonthDay = array_fuse($by_month_day);
				return $this;
				}

				public function getByMonthDay() {
				return $this->byMonthDay;
				}

				public function setByYearDay($by_year_day) {
				$this->assertByRange('BYYEARDAY', $by_year_day, -366, 366, false);
				$this->byYearDay = array_fuse($by_year_day);
				return $this;
				}

				public function getByYearDay() {
				return $this->byYearDay;
				}

				public function setByMonth(array $by_month) {
				$this->assertByRange('BYMONTH', $by_month, 1, 12);
				$this->byMonth = array_fuse($by_month);
				return $this;
				}

				public function getByMonth() {
				return $this->byMonth;
				}

				public function setByWeekNumber(array $by_week_number) {
				$this->assertByRange('BYWEEKNO', $by_week_number, -53, 53, false);
				$this->byWeekNumber = array_fuse($by_week_number);
				return $this;
				}

				public function getByWeekNumber() {
				return $this->byWeekNumber;
				}

				public function setBySetPosition(array $by_set_position) {
				$this->assertByRange('BYSETPOS', $by_set_position, -366, 366, false);
				$this->bySetPosition = $by_set_position;
				return $this;
				}

				public function getBySetPosition() {
				return $this->bySetPosition;
				}

				public function setWeekStart($week_start) {
				// Make sure this is a valid weekday constant.
				self::getWeekdayIndex($week_start);

				$this->weekStart = $week_start;
				return $this;
				}

				public function getWeekStart() {
				return $this->weekStart;
				}

				public function resetSource() {
				$frequency = $this->getFrequency();

				if ($this->getByMonthDay()) {
				switch ($frequency) {
				case self::FREQUENCY_WEEKLY:
				// RFC5545: "The BYMONTHDAY rule part MUST NOT be specified when the
				// FREQ rule part is set to WEEKLY."
				throw new Exception(
				pht(
				'RRULE specifies BYMONTHDAY with FREQ set to WEEKLY, which '.
				'violates RFC5545.'));
				break;
				default:
				break;
				}

				}

				if ($this->getByYearDay()) {
				switch ($frequency) {
				case self::FREQUENCY_DAILY:
				case self::FREQUENCY_WEEKLY:
				case self::FREQUENCY_MONTHLY:
				// RFC5545: "The BYYEARDAY rule part MUST NOT be specified when the
				// FREQ rule part is set to DAILY, WEEKLY, or MONTHLY."
				throw new Exception(
				pht(
				'RRULE specifies BYYEARDAY with FREQ of DAILY, WEEKLY or '.
				'MONTHLY, which violates RFC5545.'));
				default:
				break;
				}
				}

				// TODO
				// RFC5545: "The BYDAY rule part MUST NOT be specified with a numeric
				// value when the FREQ rule part is not set to MONTHLY or YEARLY."
				// RFC5545: "Furthermore, the BYDAY rule part MUST NOT be specified with a
				// numeric value with the FREQ rule part set to YEARLY when the BYWEEKNO
				// rule part is specified."


				$date = $this->getStartDateTime();

				$this->cursorSecond = $date->getSecond();
				$this->cursorMinute = $date->getMinute();
				$this->cursorHour = $date->getHour();

				$this->cursorDay = $date->getDay();
				$this->cursorMonth = $date->getMonth();
				$this->cursorYear = $date->getYear();

				$year_map = $this->getYearMap($this->cursorYear, $this->getWeekStart());
				$key = $this->cursorMonth.'M'.$this->cursorDay.'D';
				$this->cursorWeek = $year_map['info'][$key]['week'];
				$this->cursorWeekday = $year_map['info'][$key]['weekday'];

				$this->setSeconds = array();
				$this->setMinutes = array();
				$this->setHours = array();
				$this->setDays = array();
				$this->setMonths = array();
				$this->setYears = array();

				$this->stateSecond = null;
				$this->stateMinute = null;
				$this->stateHour = null;
				$this->stateDay = null;
				$this->stateWeek = null;
				$this->stateMonth = null;
				$this->stateYear = null;

				// If we have a BYSETPOS, we need to generate the entire set before we
				// can filter it and return results. Normally, we start generating at
				// the start date, but we need to go back one interval to generate
				// BYSETPOS events so we can make sure the entire set is generated.
				if ($this->getBySetPosition()) {
				$interval = $this->getInterval();
				switch ($frequency) {
				case self::FREQUENCY_YEARLY:
				$this->cursorYear -= $interval;
				break;
				case self::FREQUENCY_MONTHLY:
				$this->cursorMonth -= $interval;
				$this->rewindMonth();
				break;
				case self::FREQUENCY_WEEKLY:
				$this->cursorWeek -= $interval;
				$this->rewindWeek();
				break;
				case self::FREQUENCY_DAILY:
				$this->cursorDay -= $interval;
				$this->rewindDay();
				break;
				case self::FREQUENCY_HOURLY:
				$this->cursorHour -= $interval;
				$this->rewindHour();
				break;
				case self::FREQUENCY_MINUTELY:
				$this->cursorMinute -= $interval;
				$this->rewindMinute();
				break;
				case self::FREQUENCY_SECONDLY:
				default:
				throw new Exception(
				pht(
				'RRULE specifies BYSETPOS with FREQ "%s", but this is invalid.',
				$frequency));
				}
				}

				// We can generate events from before the cursor when evaluating rules
				// with BYSETPOS or FREQ=WEEKLY.
				$this->minimumEpoch = $this->getStartDateTime()->getEpoch();

				$cursor_state = array(
				'year' => $this->cursorYear,
				'month' => $this->cursorMonth,
				'week' => $this->cursorWeek,
				'day' => $this->cursorDay,
				'hour' => $this->cursorHour,
				);

				$this->cursorDayState = $cursor_state;
				$this->cursorWeekState = $cursor_state;
				$this->cursorHourState = $cursor_state;

				$by_hour = $this->getByHour();
				$by_minute = $this->getByMinute();
				$by_second = $this->getBySecond();

				$scale = $this->getFrequencyScale();

				// We return all-day events if the start date is an all-day event and we
				// don't have more granular selectors or a more granular frequency.
				$this->isAllDay = $date->getIsAllDay()
				&& !$by_hour
				&& !$by_minute
				&& !$by_second
				&& ($scale > self::SCALE_HOURLY);
				}

				public function getNextEvent($cursor) {
				while (true) {
				$event = $this->generateNextEvent();
				if (!$event) {
				break;
				}

				$epoch = $event->getEpoch();
				if ($this->minimumEpoch) {
				if ($epoch < $this->minimumEpoch) {
				continue;
				}
				}

				if ($epoch < $cursor) {
				continue;
				}

				break;
				}

				return $event;
				}

				private function generateNextEvent() {
				if ($this->activeSet) {
				return array_pop($this->activeSet);
				}

				$this->baseYear = $this->cursorYear;

				$by_setpos = $this->getBySetPosition();
				if ($by_setpos) {
				$old_state = $this->getSetPositionState();
				}

				while (!$this->activeSet) {
				$this->activeSet = $this->nextSet;
				$this->nextSet = array();

				while (true) {
				if ($this->isAllDay) {
				$this->nextDay();
				} else {
				$this->nextSecond();
				}

				$result = id(new PhutilCalendarAbsoluteDateTime())
				->setTimezone($this->getStartDateTime()->getTimezone())
				->setViewerTimezone($this->getViewerTimezone())
				->setYear($this->stateYear)
				->setMonth($this->stateMonth)
				->setDay($this->stateDay);

				if ($this->isAllDay) {
				$result->setIsAllDay(true);
				} else {
				$result
				->setHour($this->stateHour)
				->setMinute($this->stateMinute)
				->setSecond($this->stateSecond);
				}

				// If we don't have BYSETPOS, we're all done. We put this into the
				// set and will immediately return it.
				if (!$by_setpos) {
				$this->activeSet[] = $result;
				break;
				}

				// Otherwise, check if we've completed a set. The set is complete if
				// the state has moved past the span we were examining (for example,
				// with a YEARLY event, if the state is now in the next year).
				$new_state = $this->getSetPositionState();
				if ($new_state == $old_state) {
				$this->activeSet[] = $result;
				continue;
				}

				$this->activeSet = $this->applySetPos($this->activeSet, $by_setpos);
				$this->activeSet = array_reverse($this->activeSet);
				$this->nextSet[] = $result;
				$old_state = $new_state;
				break;
				}
				}

				return array_pop($this->activeSet);
				}


				protected function nextSecond() {
				if ($this->setSeconds) {
				$this->stateSecond = array_pop($this->setSeconds);
				return;
				}

				$frequency = $this->getFrequency();
				$interval = $this->getInterval();
				$is_secondly = ($frequency == self::FREQUENCY_SECONDLY);
				$by_second = $this->getBySecond();

				while (!$this->setSeconds) {
				$this->nextMinute();

				if ($is_secondly \|\| $by_second) {
				$seconds = $this->newSecondsSet(
				($is_secondly ? $interval : 1),
				$by_second);
				} else {
				$seconds = array(
				$this->cursorSecond,
				);
				}

				$this->setSeconds = array_reverse($seconds);
				}

				$this->stateSecond = array_pop($this->setSeconds);
				}

				protected function nextMinute() {
				if ($this->setMinutes) {
				$this->stateMinute = array_pop($this->setMinutes);
				return;
				}

				$frequency = $this->getFrequency();
				$interval = $this->getInterval();
				$scale = $this->getFrequencyScale();
				$is_minutely = ($frequency === self::FREQUENCY_MINUTELY);
				$by_minute = $this->getByMinute();

				while (!$this->setMinutes) {
				$this->nextHour();

				if ($is_minutely \|\| $by_minute) {
				$minutes = $this->newMinutesSet(
				($is_minutely ? $interval : 1),
				$by_minute);
				} else if ($scale < self::SCALE_MINUTELY) {
				$minutes = $this->newMinutesSet(
				1,
				array());
				} else {
				$minutes = array(
				$this->cursorMinute,
				);
				}

				$this->setMinutes = array_reverse($minutes);
				}

				$this->stateMinute = array_pop($this->setMinutes);
				}

				protected function nextHour() {
				if ($this->setHours) {
				$this->stateHour = array_pop($this->setHours);
				return;
				}

				$frequency = $this->getFrequency();
				$interval = $this->getInterval();
				$scale = $this->getFrequencyScale();
				$is_hourly = ($frequency === self::FREQUENCY_HOURLY);
				$by_hour = $this->getByHour();

				while (!$this->setHours) {
				$this->nextDay();

				$is_dynamic = $is_hourly
				\|\| $by_hour
				\|\| ($scale < self::SCALE_HOURLY);

				if ($is_dynamic) {
				$hours = $this->newHoursSet(
				($is_hourly ? $interval : 1),
				$by_hour);
				} else {
				$hours = array(
				$this->cursorHour,
				);
				}

				$this->setHours = array_reverse($hours);
				}

				$this->stateHour = array_pop($this->setHours);
				}

				protected function nextDay() {
				if ($this->setDays) {
				$info = array_pop($this->setDays);
				$this->setDayState($info);
				return;
				}

				$frequency = $this->getFrequency();
				$interval = $this->getInterval();
				$scale = $this->getFrequencyScale();
				$is_daily = ($frequency === self::FREQUENCY_DAILY);
				$is_weekly = ($frequency === self::FREQUENCY_WEEKLY);

				$by_day = $this->getByDay();
				$by_monthday = $this->getByMonthDay();
				$by_yearday = $this->getByYearDay();
				$by_weekno = $this->getByWeekNumber();
				$by_month = $this->getByMonth();
				$week_start = $this->getWeekStart();

				while (!$this->setDays) {
				if ($is_weekly) {
				$this->nextWeek();
				} else {
				$this->nextMonth();
				}

				// NOTE: We normally handle BYMONTH when iterating months, but it acts
				// like a filter if FREQ=WEEKLY.

				$is_dynamic = $is_daily
				\|\| $is_weekly
				\|\| $by_day
				\|\| $by_monthday
				\|\| $by_yearday
				\|\| $by_weekno
				\|\| ($by_month && $is_weekly)
				\|\| ($scale < self::SCALE_DAILY);

				if ($is_dynamic) {
				$weeks = $this->newDaysSet(
				($is_daily ? $interval : 1),
				$by_day,
				$by_monthday,
				$by_yearday,
				$by_weekno,
				$by_month,
				$week_start);
				} else {
				// The cursor day may not actually exist in the current month, so
				// make sure the day is valid before we generate a set which contains
				// it.
				$year_map = $this->getYearMap($this->stateYear, $week_start);
				if ($this->cursorDay > $year_map['monthDays'][$this->stateMonth]) {
				$weeks = array(
				array(),
				);
				} else {
				$key = $this->stateMonth.'M'.$this->cursorDay.'D';
				$weeks = array(
				array($year_map['info'][$key]),
				);
				}
				}

				// Unpack the weeks into days.
				$days = array_mergev($weeks);

				$this->setDays = array_reverse($days);
				}

				$info = array_pop($this->setDays);
				$this->setDayState($info);
				}

				private function setDayState(array $info) {
				$this->stateDay = $info['monthday'];
				$this->stateWeek = $info['week'];
				$this->stateMonth = $info['month'];
				}

				protected function nextMonth() {
				if ($this->setMonths) {
				$this->stateMonth = array_pop($this->setMonths);
				return;
				}

				$frequency = $this->getFrequency();
				$interval = $this->getInterval();
				$scale = $this->getFrequencyScale();
				$is_monthly = ($frequency === self::FREQUENCY_MONTHLY);

				$by_month = $this->getByMonth();

				// If we have a BYMONTHDAY, we consider that set of days in every month.
				// For example, "FREQ=YEARLY;BYMONTHDAY=3" means "the third day of every
				// month", so we need to expand the month set if the constraint is present.
				$by_monthday = $this->getByMonthDay();

				// Likewise, we need to generate all months if we have BYYEARDAY or
				// BYWEEKNO or BYDAY.
				$by_yearday = $this->getByYearDay();
				$by_weekno = $this->getByWeekNumber();
				$by_day = $this->getByDay();

				while (!$this->setMonths) {
				$this->nextYear();

				$is_dynamic = $is_monthly
				\|\| $by_month
				\|\| $by_monthday
				\|\| $by_yearday
				\|\| $by_weekno
				\|\| $by_day
				\|\| ($scale < self::SCALE_MONTHLY);

				if ($is_dynamic) {
				$months = $this->newMonthsSet(
				($is_monthly ? $interval : 1),
				$by_month);
				} else {
				$months = array(
				$this->cursorMonth,
				);
				}

				$this->setMonths = array_reverse($months);
				}

				$this->stateMonth = array_pop($this->setMonths);
				}

				protected function nextWeek() {
				if ($this->setWeeks) {
				$this->stateWeek = array_pop($this->setWeeks);
				return;
				}

				$frequency = $this->getFrequency();
				$interval = $this->getInterval();
				$scale = $this->getFrequencyScale();
				$by_weekno = $this->getByWeekNumber();

				while (!$this->setWeeks) {
				$this->nextYear();

				$weeks = $this->newWeeksSet(
				$interval,
				$by_weekno);

				$this->setWeeks = array_reverse($weeks);
				}

				$this->stateWeek = array_pop($this->setWeeks);
				}

				protected function nextYear() {
				$this->stateYear = $this->cursorYear;

				$frequency = $this->getFrequency();
				$is_yearly = ($frequency === self::FREQUENCY_YEARLY);

				if ($is_yearly) {
				$interval = $this->getInterval();
				} else {
				$interval = 1;
				}

				$this->cursorYear = $this->cursorYear + $interval;

				if ($this->cursorYear > ($this->baseYear + 100)) {
				throw new Exception(
				pht(
				'RRULE evaluation failed to generate more events in the next 100 '.
				'years. This RRULE is likely invalid or degenerate.'));
				}

				}

				private function newSecondsSet($interval, $set) {
				// TODO: This doesn't account for leap seconds. In theory, it probably
				// should, although this shouldn't impact any real events.
				$seconds_in_minute = 60;

				if ($this->cursorSecond >= $seconds_in_minute) {
				$this->cursorSecond -= $seconds_in_minute;
				return array();
				}

				list($cursor, $result) = $this->newIteratorSet(
				$this->cursorSecond,
				$interval,
				$set,
				$seconds_in_minute);

				$this->cursorSecond = ($cursor - $seconds_in_minute);

				return $result;
				}

				private function newMinutesSet($interval, $set) {
				// NOTE: This value is legitimately a constant! Amazing!
				$minutes_in_hour = 60;

				if ($this->cursorMinute >= $minutes_in_hour) {
				$this->cursorMinute -= $minutes_in_hour;
				return array();
				}

				list($cursor, $result) = $this->newIteratorSet(
				$this->cursorMinute,
				$interval,
				$set,
				$minutes_in_hour);

				$this->cursorMinute = ($cursor - $minutes_in_hour);

				return $result;
				}

				private function newHoursSet($interval, $set) {
				// TODO: This doesn't account for hours caused by daylight savings time.
				// It probably should, although this seems unlikely to impact any real
				// events.
				$hours_in_day = 24;

				// If the hour cursor is behind the current time, we need to forward it in
				// INTERVAL increments so we end up with the right offset.
				list($skip, $this->cursorHourState) = $this->advanceCursorState(
				$this->cursorHourState,
				self::SCALE_HOURLY,
				$interval,
				$this->getWeekStart());

				if ($skip) {
				return array();
				}

				list($cursor, $result) = $this->newIteratorSet(
				$this->cursorHour,
				$interval,
				$set,
				$hours_in_day);

				$this->cursorHour = ($cursor - $hours_in_day);

				return $result;
				}

				private function newWeeksSet($interval, $set) {
				$week_start = $this->getWeekStart();

				list($skip, $this->cursorWeekState) = $this->advanceCursorState(
				$this->cursorWeekState,
				self::SCALE_WEEKLY,
				$interval,
				$week_start);

				if ($skip) {
				return array();
				}

				$year_map = $this->getYearMap($this->stateYear, $week_start);

				$result = array();
				while (true) {
				if (!isset($year_map['weekMap'][$this->cursorWeek])) {
				break;
				}
				$result[] = $this->cursorWeek;
				$this->cursorWeek += $interval;
				}

				$this->cursorWeek -= $year_map['weekCount'];

				return $result;
				}

				private function newDaysSet(
				$interval_day,
				$by_day,
				$by_monthday,
				$by_yearday,
				$by_weekno,
				$by_month,
				$week_start) {

				$frequency = $this->getFrequency();
				$is_yearly = ($frequency == self::FREQUENCY_YEARLY);
				$is_monthly = ($frequency == self::FREQUENCY_MONTHLY);
				$is_weekly = ($frequency == self::FREQUENCY_WEEKLY);

				$selection = array();
				if ($is_weekly) {
				$year_map = $this->getYearMap($this->stateYear, $week_start);

				if (isset($year_map['weekMap'][$this->stateWeek])) {
				foreach ($year_map['weekMap'][$this->stateWeek] as $key) {
				$selection[] = $year_map['info'][$key];
				}
				}
				} else {
				// If the day cursor is behind the current year and month, we need to
				// forward it in INTERVAL increments so we end up with the right offset
				// in the current month.
				list($skip, $this->cursorDayState) = $this->advanceCursorState(
				$this->cursorDayState,
				self::SCALE_DAILY,
				$interval_day,
				$week_start);

				if (!$skip) {
				$year_map = $this->getYearMap($this->stateYear, $week_start);
				while (true) {
				$month_idx = $this->stateMonth;
				$month_days = $year_map['monthDays'][$month_idx];
				if ($this->cursorDay > $month_days) {
				// NOTE: The year map is now out of date, but we're about to break
				// out of the loop anyway so it doesn't matter.
				break;
				}

				$day_idx = $this->cursorDay;

				$key = "{$month_idx}M{$day_idx}D";
				$selection[] = $year_map['info'][$key];

				$this->cursorDay += $interval_day;
				}
				}
				}

				// As a special case, BYDAY applies to relative month offsets if BYMONTH
				// is present in a YEARLY rule.
				if ($is_yearly) {
				if ($this->getByMonth()) {
				$is_yearly = false;
				$is_monthly = true;
				}
				}

				// As a special case, BYDAY makes us examine all week days. This doesn't
				// check BYMONTHDAY or BYYEARDAY because they are not valid with WEEKLY.
				$filter_weekday = true;
				if ($is_weekly) {
				if ($by_day) {
				$filter_weekday = false;
				}
				}

				$weeks = array();
				foreach ($selection as $key => $info) {
				if ($is_weekly) {
				if ($filter_weekday) {
				if ($info['weekday'] != $this->cursorWeekday) {
				continue;
				}
				}
				} else {
				if ($info['month'] != $this->stateMonth) {
				continue;
				}
				}

				if ($by_day) {
				if (empty($by_day[$info['weekday']])) {
				if ($is_yearly) {
				if (empty($by_day[$info['weekday.yearly']]) &&
				empty($by_day[$info['-weekday.yearly']])) {
				continue;
				}
				} else if ($is_monthly) {
				if (empty($by_day[$info['weekday.monthly']]) &&
				empty($by_day[$info['-weekday.monthly']])) {
				continue;
				}
				} else {
				continue;
				}
				}
				}

				if ($by_monthday) {
				if (empty($by_monthday[$info['monthday']]) &&
				empty($by_monthday[$info['-monthday']])) {
				continue;
				}
				}

				if ($by_yearday) {
				if (empty($by_yearday[$info['yearday']]) &&
				empty($by_yearday[$info['-yearday']])) {
				continue;
				}
				}

				if ($by_weekno) {
				if (empty($by_weekno[$info['week']]) &&
				empty($by_weekno[$info['-week']])) {
				continue;
				}
				}

				if ($by_month) {
				if (empty($by_month[$info['month']])) {
				continue;
				}
				}

				$weeks[$info['week']][] = $info;
				}

				return array_values($weeks);
				}

				private function newMonthsSet($interval, $set) {
				// NOTE: This value is also a real constant! Wow!
				$months_in_year = 12;

				if ($this->cursorMonth > $months_in_year) {
				$this->cursorMonth -= $months_in_year;
				return array();
				}

				list($cursor, $result) = $this->newIteratorSet(
				$this->cursorMonth,
				$interval,
				$set,
				$months_in_year + 1);

				$this->cursorMonth = ($cursor - $months_in_year);

				return $result;
				}

				public static function getYearMap($year, $week_start) {
				static $maps = array();

				$key = "{$year}/{$week_start}";
				if (isset($maps[$key])) {
				return $maps[$key];
				}

				$map = self::newYearMap($year, $week_start);
				$maps[$key] = $map;

				return $maps[$key];
				}

				private static function newYearMap($year, $weekday_start) {
				$weekday_index = self::getWeekdayIndex($weekday_start);

				$is_leap = (($year % 4 === 0) && ($year % 100 !== 0)) \|\|
				($year % 400 === 0);

				// There may be some clever way to figure out which day of the week a given
				// year starts on and avoid the cost of a DateTime construction, but I
				// wasn't able to turn it up and we only need to do this once per year.
				$datetime = new DateTime("{$year}-01-01", new DateTimeZone('UTC'));
				$weekday = (int)$datetime->format('w');

				if ($is_leap) {
				$max_day = 366;
				} else {
				$max_day = 365;
				}

				$month_days = array(
				1 => 31,
				2 => $is_leap ? 29 : 28,
				3 => 31,
				4 => 30,
				5 => 31,
				6 => 30,
				7 => 31,
				8 => 31,
				9 => 30,
				10 => 31,
				11 => 30,
				12 => 31,
				);

				// Per the spec, the first week of the year must contain at least four
				// days. If the week starts on a Monday but the year starts on a Saturday,
				// the first couple of days don't count as a week. In this case, the first
				// week will begin on January 3.
				$first_week_size = 0;
				$first_weekday = $weekday;
				for ($year_day = 1; $year_day <= $max_day; $year_day++) {
				$first_weekday = ($first_weekday + 1) % 7;
				$first_week_size++;
				if ($first_weekday === $weekday_index) {
				break;
				}
				}

				if ($first_week_size >= 4) {
				$week_number = 1;
				} else {
				$week_number = 0;
				}

				$info_map = array();

				$weekday_map = self::getWeekdayIndexMap();
				$weekday_map = array_flip($weekday_map);

				$yearly_counts = array();
				$monthly_counts = array();

				$month_number = 1;
				$month_day = 1;
				for ($year_day = 1; $year_day <= $max_day; $year_day++) {
				$key = "{$month_number}M{$month_day}D";

				$short_day = $weekday_map[$weekday];
				if (empty($yearly_counts[$short_day])) {
				$yearly_counts[$short_day] = 0;
				}
				$yearly_counts[$short_day]++;

				if (empty($monthly_counts[$month_number][$short_day])) {
				$monthly_counts[$month_number][$short_day] = 0;
				}
				$monthly_counts[$month_number][$short_day]++;

				$info = array(
				'year' => $year,
				'key' => $key,
				'month' => $month_number,
				'monthday' => $month_day,
				'-monthday' => -$month_days[$month_number] + $month_day - 1,
				'yearday' => $year_day,
				'-yearday' => -$max_day + $year_day - 1,
				'week' => $week_number,
				'weekday' => $short_day,
				'weekday.yearly' => $yearly_counts[$short_day],
				'weekday.monthly' => $monthly_counts[$month_number][$short_day],
				);

				$info_map[$key] = $info;

				$weekday = ($weekday + 1) % 7;
				if ($weekday === $weekday_index) {
				$week_number++;
				}

				$month_day = ($month_day + 1);
				if ($month_day > $month_days[$month_number]) {
				$month_day = 1;
				$month_number++;
				}
				}

				// Check how long the final week is. If it doesn't have four days, this
				// is really the first week of the next year.
				$final_week = array();
				foreach ($info_map as $key => $info) {
				if ($info['week'] == $week_number) {
				$final_week[] = $key;
				}
				}

				if (count($final_week) < 4) {
				$week_number = $week_number - 1;
				$next_year = self::getYearMap($year + 1, $weekday_start);
				$next_year_weeks = $next_year['weekCount'];
				} else {
				$next_year_weeks = null;
				}

				if ($first_week_size < 4) {
				$last_year = self::getYearMap($year - 1, $weekday_start);
				$last_year_weeks = $last_year['weekCount'];
				} else {
				$last_year_weeks = null;
				}

				// Now that we know how many weeks the year has, we can compute the
				// negative offsets.
				foreach ($info_map as $key => $info) {
				$week = $info['week'];

				if ($week === 0) {
				// If this day is part of the first partial week of the year, give
				// it the week number of the last week of the prior year instead.
				$info['week'] = $last_year_weeks;
				$info['-week'] = -1;
				} else if ($week > $week_number) {
				// If this day is part of the last partial week of the year, give
				// it week numbers from the next year.
				$info['week'] = 1;
				$info['-week'] = -$next_year_weeks;
				} else {
				$info['-week'] = -$week_number + $week - 1;
				}

				// Do all the arithmetic to figure out if this is the -19th Thursday
				// in the year and such.
				$month_number = $info['month'];
				$short_day = $info['weekday'];
				$monthly_count = $monthly_counts[$month_number][$short_day];
				$monthly_index = $info['weekday.monthly'];
				$info['-weekday.monthly'] = -$monthly_count + $monthly_index - 1;
				$info['-weekday.monthly'] .= $short_day;
				$info['weekday.monthly'] .= $short_day;

				$yearly_count = $yearly_counts[$short_day];
				$yearly_index = $info['weekday.yearly'];
				$info['-weekday.yearly'] = -$yearly_count + $yearly_index - 1;
				$info['-weekday.yearly'] .= $short_day;
				$info['weekday.yearly'] .= $short_day;

				$info_map[$key] = $info;
				}

				$week_map = array();
				foreach ($info_map as $key => $info) {
				$week_map[$info['week']][] = $key;
				}

				return array(
				'info' => $info_map,
				'weekCount' => $week_number,
				'dayCount' => $max_day,
				'monthDays' => $month_days,
				'weekMap' => $week_map,
				);
				}

				private function newIteratorSet($cursor, $interval, $set, $limit) {
				if ($interval < 1) {
				throw new Exception(
				pht(
				'Invalid iteration interval ("%d"), must be at least 1.',
				$interval));
				}

				$result = array();
				$seen = array();

				$ii = $cursor;
				while (true) {
				if (!$set \|\| isset($set[$ii])) {
				$result[] = $ii;
				}

				$ii = ($ii + $interval);

				if ($ii >= $limit) {
				break;
				}
				}

				sort($result);
				$result = array_values($result);

				return array($ii, $result);
				}

				private function applySetPos(array $values, array $setpos) {
				$select = array();

				$count = count($values);
				foreach ($setpos as $pos) {
				if ($pos > 0 && $pos <= $count) {
				$select[] = ($pos - 1);
				} else if ($pos < 0 && $pos >= -$count) {
				$select[] = ($count + $pos);
				}
				}

				sort($select);
				$select = array_unique($select);

				return array_select_keys($values, $select);
				}

				private function assertByRange(
				$source,
				array $values,
				$min,
				$max,
				$allow_zero = true) {

				foreach ($values as $value) {
				if (!is_int($value)) {
				throw new Exception(
				pht(
				'Value "%s" in RRULE "%s" parameter is invalid: values must be '.
				'integers.',
				$value,
				$source));
				}

				if ($value < $min \|\| $value > $max) {
				throw new Exception(
				pht(
				'Value "%s" in RRULE "%s" parameter is invalid: it must be '.
				'between %s and %s.',
				$value,
				$source,
				$min,
				$max));
				}

				if (!$value && !$allow_zero) {
				throw new Exception(
				pht(
				'Value "%s" in RRULE "%s" parameter is invalid: it must not '.
				'be zero.',
				$value,
				$source));
				}
				}
				}

				private function getSetPositionState() {
				$scale = $this->getFrequencyScale();

				$parts = array();
				$parts[] = $this->stateYear;

				if ($scale == self::SCALE_WEEKLY) {
				$parts[] = $this->stateWeek;
				} else {
				if ($scale < self::SCALE_YEARLY) {
				$parts[] = $this->stateMonth;
				}
				if ($scale < self::SCALE_MONTHLY) {
				$parts[] = $this->stateDay;
				}
				if ($scale < self::SCALE_DAILY) {
				$parts[] = $this->stateHour;
				}
				if ($scale < self::SCALE_HOURLY) {
				$parts[] = $this->stateMinute;
				}
				}

				return implode('/', $parts);
				}

				private function rewindMonth() {
				while ($this->cursorMonth < 1) {
				$this->cursorYear--;
				$this->cursorMonth += 12;
				}
				}

				private function rewindWeek() {
				$week_start = $this->getWeekStart();
				while ($this->cursorWeek < 1) {
				$this->cursorYear--;
				$year_map = $this->getYearMap($this->cursorYear, $week_start);
				$this->cursorWeek += $year_map['weekCount'];
				}
				}

				private function rewindDay() {
				$week_start = $this->getWeekStart();
				while ($this->cursorDay < 1) {
				$year_map = $this->getYearMap($this->cursorYear, $week_start);
				$this->cursorDay += $year_map['monthDays'][$this->cursorMonth];
				$this->cursorMonth--;
				$this->rewindMonth();
				}
				}

				private function rewindHour() {
				while ($this->cursorHour < 0) {
				$this->cursorHour += 24;
				$this->cursorDay--;
				$this->rewindDay();
				}
				}

				private function rewindMinute() {
				while ($this->cursorMinute < 0) {
				$this->cursorMinute += 60;
				$this->cursorHour--;
				$this->rewindHour();
				}
				}

				private function advanceCursorState(
				array $cursor,
				$scale,
				$interval,
				$week_start) {

				$state = array(
				'year' => $this->stateYear,
				'month' => $this->stateMonth,
				'week' => $this->stateWeek,
				'day' => $this->stateDay,
				'hour' => $this->stateHour,
				);

				// In the common case when the interval is 1, we'll visit every possible
				// value so we don't need to do any math and can just jump to the first
				// hour, day, etc.
				if ($interval == 1) {
				if ($this->isCursorBehind($cursor, $state, $scale)) {
				switch ($scale) {
				case self::SCALE_DAILY:
				$this->cursorDay = 1;
				break;
				case self::SCALE_HOURLY:
				$this->cursorHour = 0;
				break;
				case self::SCALE_WEEKLY:
				$this->cursorWeek = 1;
				break;
				}
				}

				return array(false, $state);
				}

				$year_map = $this->getYearMap($cursor['year'], $week_start);
				while ($this->isCursorBehind($cursor, $state, $scale)) {
				switch ($scale) {
				case self::SCALE_DAILY:
				$cursor['day'] += $interval;
				break;
				case self::SCALE_HOURLY:
				$cursor['hour'] += $interval;
				break;
				case self::SCALE_WEEKLY:
				$cursor['week'] += $interval;
				break;
				}

				if ($scale <= self::SCALE_HOURLY) {
				while ($cursor['hour'] >= 24) {
				$cursor['hour'] -= 24;
				$cursor['day']++;
				}
				}

				if ($scale == self::SCALE_WEEKLY) {
				while ($cursor['week'] > $year_map['weekCount']) {
				$cursor['week'] -= $year_map['weekCount'];
				$cursor['year']++;
				$year_map = $this->getYearMap($cursor['year'], $week_start);
				}
				}

				if ($scale <= self::SCALE_DAILY) {
				while ($cursor['day'] > $year_map['monthDays'][$cursor['month']]) {
				$cursor['day'] -= $year_map['monthDays'][$cursor['month']];
				$cursor['month']++;
				if ($cursor['month'] > 12) {
				$cursor['month'] -= 12;
				$cursor['year']++;
				$year_map = $this->getYearMap($cursor['year'], $week_start);
				}
				}
				}
				}

				switch ($scale) {
				case self::SCALE_DAILY:
				$this->cursorDay = $cursor['day'];
				break;
				case self::SCALE_HOURLY:
				$this->cursorHour = $cursor['hour'];
				break;
				case self::SCALE_WEEKLY:
				$this->cursorWeek = $cursor['week'];
				break;
				}

				$skip = $this->isCursorBehind($state, $cursor, $scale);

				return array($skip, $cursor);
				}

				private function isCursorBehind(array $cursor, array $state, $scale) {
				if ($cursor['year'] < $state['year']) {
				return true;
				} else if ($cursor['year'] > $state['year']) {
				return false;
				}

				if ($scale == self::SCALE_WEEKLY) {
				return false;
				}

				if ($cursor['month'] < $state['month']) {
				return true;
				} else if ($cursor['month'] > $state['month']) {
				return false;
				}

				if ($scale >= self::SCALE_DAILY) {
				return false;
				}

				if ($cursor['day'] < $state['day']) {
				return true;
				} else if ($cursor['day'] > $state['day']) {
				return false;
				}

				if ($scale >= self::SCALE_HOURLY) {
				return false;
				}

				if ($cursor['hour'] < $state['hour']) {
				return true;
				} else if ($cursor['hour'] > $state['hour']) {
				return false;
				}

				return false;
				}


				}