Recurrence rule extensions

Terms and concepts are from RFC 5545 (the iCalendar specification).

Overall design
--------------

Calcurse is extended with full support for BYMONTH, BYDAY and BYMONTHDAY
recurrence rule (rrule) parts. The three rule parts are lists of,
respectively, months, weekdays and monthdays. The lists are added to
'struct rpt' as linked lists of integers, and the data file format is
extended accordingly (details below). Load and save of the lists follow
the pattern of the existing list of exception dates, also in 'struct
rpt'.

The function recur_item_find_occurence() is split into a front-end and a
back-end. The back-end, called find_occurrence(), is the original
function extended with rrule reductions; the front-end retains the
original name and performs rrule expansions. Front-end plus back-end are
backwards compatible and require no changes in calling functions.

There is no user interface in this patch.

Data file extensions
--------------------

The BYMONTH, BYDAY and BYMONTHDAY lists are added to that part of an
item line which describes the recurrence rule (the "{...}" part). Each
list is - like the list of exception days - a space-separated string of
values identified by the initial character.  Each list is optional and,
if present, must follow the until date and precede the exception day
list. The lists must appear in order BYMONTHDAY list, BYDAY list and
BYMONTH list.

The possible list values are

- BYMONTH: m1, m2, ..., m12
- BYDAY: w0, w1, ..., w6, w7, w-7, w8, w-8, ..., w377, w-377
- BYMONTHDAY: d1, d2, ..., d31, d-1, d-2, ..., d-31

which are interpreted as (cf. RFC 5545)

- BYMONTH: January, February, ..., December.
- BYDAY: SU, MO, ..., SA, +1SU, -1SU, +1MO, -1MO, ..., +53SA, -53SA
- BYMONTHDAY: the first, the second, ..., the 31st, the last,
  the last but one, ..., the last but 30 day of the month

Examples:

Thursday, TH, is w4; Saturday, SA, is w6.

The seventh Thursday, +7TH, is w53 (7 * 7 + 4 = 53); the last but second
Saturday, -2SA, is w-20 (2 * 7 + 6 = 20); the last day of the month is
d-1.

Note that the values w-1, w-2, ..., w-6 are not used.

A recurrent appointment with a BYDAY rule part:

06/23/2019 @ 12:00 -> 06/23/2019 @ 13:00 {1W w0 w6} |every week on Sunday and Saturday

An event with a BYDAY and a BYMONTH rule part:

10/27/2019 [1] {1Y w-7 m10} every year on last Sunday in October

An event with until date, a BYMONTH rule part and an exception day:

06/23/2019 [1] {1Y -> 08/31/2021 m5 m6 m7 !07/23/2020} every year on the 23rd in May, June and July for three years, starting on Sunday, 23 June 2019, but not on 23 July 2020.

Recurrence set expansion and reduction
---------------------------------------

In calcurse a recurrence rule is a quadruple (s, d, r, e) consisting of
start, duration, repetition pattern and exception days and is
implemented as:

	(time_t start, long dur, struct rpt *rpt, llist_t *exc)

In RFC 5545 parlance, a recurrence rule defines a recurrence set
consisting of all recurrence instances (occurrences) not earlier than
start which match the rule pattern. With this concept in mind,
recur_item_find_occurremce() may be thought of as a membership function
for a recurrence set. The call

	recur_item_find_occurrence(s, d, r, e, day, occurrence)

returns true if day belongs to the recurrence set of (s, d, r, e); if so
occurrence points to the recurrence instance (the set member).

For a recurrence rule with only the basic DAYLY, WEEKLY, MONTHLY or
YEARLY type and frequency the recurrence set consists of periodically
repeated instances.  The BYxxx rule parts modify the recurrence set by
reducing or expanding it as specified by RFC 5545.

Expansion is implemented in the front-end by modifications of start
and/or frequency of the rule (s, d, r, e), often several times, in such
a way that the desired recurrence instances are included in the
recurrence set. This is possible because the front-end as the very first
thing checks for early days (day < s). When day is known not to be
early, start (s) can safely be moved backwards. Likewise, if frequency
must be changed, the front-end checks whether the frequency repetition
applies to the week, month or year of day.

Reduction is easier and is performed in the back-end along with the
existing validity checks. It consists in checking whether month, day of
month or weekday of a found occurrence is on the appropriate list.

Signed-off-by: Lars Henriksen <LarsHenriksen@get2net.dk>
Signed-off-by: Lukas Fleischer <lfleischer@calcurse.org>

6 files changed, 847 insertions, 25 deletions

diff --git a/src/calcurse.h b/src/calcurse.h
index a2fea09..6b3905b 100644
--- a/src/calcurse.h
+++ b/src/calcurse.h
@@ -148,6 +148,12 @@
 
 /* Calendar window. */
 #define CALHEIGHT       8
+/*
+ * Week day numbering (0, 1,..., 6) which depends on the first day of the week.
+ * The argument (d) is the "Sunday"-numbering of member tm_wday in struct tm.
+ */
+#define WDAY(d) \
+    (ui_calendar_week_begins_on_monday() ? ((d ? d : WEEKINDAYS) - 1) : d)
 
 /* Key definitions. */
 #define CTRLVAL         0x1F
@@ -395,6 +401,9 @@ struct rpt {
 	enum recur_type type;	/* FREQ */
 	int freq;		/* INTERVAL */
 	time_t until;		/* UNTIL */
+	llist_t bymonth;	/* BYMONTH list */
+	llist_t bywday;		/* BY(WEEK)DAY list */
+	llist_t bymonthday;	/* BYMONTHDAY list */
 	llist_t exc;		/* EXDATE's */
 };
 
@@ -1076,6 +1085,9 @@ void recur_event_add_exc(struct recur_event *, time_t);
 void recur_apoint_add_exc(struct recur_apoint *, time_t);
 void recur_event_erase(struct recur_event *);
 void recur_apoint_erase(struct recur_apoint *);
+void recur_bymonth(llist_t *, FILE *);
+void recur_bywday(enum recur_type, llist_t *, FILE *);
+void recur_bymonthday(llist_t *, FILE *);
 void recur_exc_scan(llist_t *, FILE *);
 void recur_apoint_check_next(struct notify_app *, time_t, time_t);
 void recur_apoint_switch_notify(struct recur_apoint *);
@@ -1240,6 +1252,9 @@ int hash_matches(const char *, const char *);
 int show_dialogs(void);
 long overflow_add(long, long, long *);
 long overflow_mul(long, long, long *);
+time_t next_wday(time_t, int);
+int wday_per_year(int, int);
+int wday_per_month(int, int, int);
 
 /* vars.c */
 extern int col, row;
diff --git a/src/ical.c b/src/ical.c
index fa9a663..b94108f 100644
--- a/src/ical.c
+++ b/src/ical.c
@@ -387,6 +387,9 @@ ical_store_event(char *mesg, char *note, long day, long end,
 		rpt.type = irpt->type;
 		rpt.freq = irpt->freq;
 		rpt.until = irpt->until;
+		LLIST_INIT(&rpt.bymonth);
+		LLIST_INIT(&rpt.bywday);
+		LLIST_INIT(&rpt.bymonthday);
 		rpt.exc = *exc;
 		rev = recur_event_new(mesg, note, day, EVENTID, &rpt);
 		mem_free(irpt);
@@ -414,6 +417,9 @@ ical_store_event(char *mesg, char *note, long day, long end,
 	rpt.type = RECUR_DAILY;
 	rpt.freq = 1;
 	rpt.until = end;
+	LLIST_INIT(&rpt.bymonth);
+	LLIST_INIT(&rpt.bywday);
+	LLIST_INIT(&rpt.bymonthday);
 	rpt.exc = *exc;
 	rev = recur_event_new(mesg, note, day, EVENTID, &rpt);
 	if (fmt_rev)
@@ -440,6 +446,9 @@ ical_store_apoint(char *mesg, char *note, long start, long dur,
 		rpt.type = irpt->type;
 		rpt.freq = irpt->freq;
 		rpt.until = irpt->until;
+		LLIST_INIT(&rpt.bymonth);
+		LLIST_INIT(&rpt.bywday);
+		LLIST_INIT(&rpt.bymonthday);
 		rpt.exc = *exc;
 		rapt = recur_apoint_new(mesg, note, start, dur, state, &rpt);
 		mem_free(irpt);
diff --git a/src/io.c b/src/io.c
index b9c2d3b..1caa6d3 100644
--- a/src/io.c
+++ b/src/io.c
@@ -644,7 +644,7 @@ void io_load_app(struct item_filter *filter)
 				     &until.tm_mon, &until.tm_mday,
 				     &until.tm_year) != 3)
 					io_load_error(path_apts, line,
-						      _("syntax error in item repetition"));
+						      _("syntax error in until date"));
 				if (!check_date(until.tm_year, until.tm_mon,
 						until.tm_mday))
 					io_load_error(path_apts, line,
@@ -659,6 +659,30 @@ void io_load_app(struct item_filter *filter)
 				c = getc(data_file);
 			} else
 				rpt.until = 0;
+			/* Optional bymonthday list */
+			if (c == 'd') {
+				if (rpt.type == RECUR_WEEKLY)
+					io_load_error(path_apts, line,
+						      _("BYMONTHDAY illegal with WEEKLY"));
+				ungetc(c, data_file);
+				recur_bymonthday(&rpt.bymonthday, data_file);
+				c = getc(data_file);
+			} else
+				LLIST_INIT(&rpt.bymonthday);
+			/* Optional bywday list */
+			if (c == 'w') {
+				ungetc(c, data_file);
+				recur_bywday(rpt.type, &rpt.bywday, data_file);
+				c = getc(data_file);
+			} else
+				LLIST_INIT(&rpt.bywday);
+			/* Optional bymonth list */
+			if (c == 'm') {
+				ungetc(c, data_file);
+				recur_bymonth(&rpt.bymonth, data_file);
+				c = getc(data_file);
+			} else
+				LLIST_INIT(&rpt.bymonth);
 			/* Optional exception dates */
 			if (c == '!') {
 				ungetc(c, data_file);
diff --git a/src/recur.c b/src/recur.c
index 168ba17..53c4f53 100644
--- a/src/recur.c
+++ b/src/recur.c
@@ -46,6 +46,39 @@
 llist_ts_t recur_alist_p;
 llist_t recur_elist;
 
+static void free_int(int *i)
+{
+	mem_free(i);
+}
+
+static void free_int_list(llist_t *ilist)
+{
+	LLIST_FREE_INNER(ilist, free_int);
+	LLIST_FREE(ilist);
+}
+
+static void int_list_dup(llist_t *l, llist_t *ilist)
+{
+	llist_item_t *i;
+	int *o, *p;
+
+	LLIST_INIT(l);
+
+	if (ilist->head) {
+		LLIST_FOREACH(ilist, i) {
+			p = LLIST_GET_DATA(i);
+			o = mem_malloc(sizeof(int));
+			*o = *p;
+			LLIST_ADD(l, o);
+		}
+	}
+}
+
+static int int_cmp(int *list, int *i)
+{
+	return *list == *i;
+}
+
 static void free_exc(struct excp *exc)
 {
 	mem_free(exc);
@@ -62,6 +95,11 @@ static int exc_cmp_day(struct excp *a, struct excp *b)
 	return a->st < b->st ? -1 : (a->st == b->st ? 0 : 1);
 }
 
+static int exc_inday(struct excp *exc, time_t *day_start)
+{
+	return (date_cmp_day(exc->st, *day_start) == 0);
+}
+
 static void recur_add_exc(llist_t * exc, time_t day)
 {
 	struct excp *o = mem_malloc(sizeof(struct excp));
@@ -273,6 +311,12 @@ struct recur_apoint *recur_apoint_new(char *mesg, char *note, time_t start,
 	rapt->state = state;
 	rapt->rpt = mem_malloc(sizeof(struct rpt));
 	*rapt->rpt = *rpt;
+	int_list_dup(&rapt->rpt->bymonth, &rpt->bymonth);
+	free_int_list(&rpt->bymonth);
+	int_list_dup(&rapt->rpt->bywday, &rpt->bywday);
+	free_int_list(&rpt->bywday);
+	int_list_dup(&rapt->rpt->bymonthday, &rpt->bymonthday);
+	free_int_list(&rpt->bymonthday);
 	/*
 	 * Note. The exception dates are in the list rapt->exc.
 	 * The (empty) list rapt->rpt->exc is not used.
@@ -300,6 +344,12 @@ struct recur_event *recur_event_new(char *mesg, char *note, time_t day,
 	rev->id = id;
 	rev->rpt = mem_malloc(sizeof(struct rpt));
 	*rev->rpt = *rpt;
+	int_list_dup(&rev->rpt->bymonth, &rpt->bymonth);
+	free_int_list(&rpt->bymonth);
+	int_list_dup(&rev->rpt->bywday, &rpt->bywday);
+	free_int_list(&rpt->bywday);
+	int_list_dup(&rev->rpt->bymonthday, &rpt->bymonthday);
+	free_int_list(&rpt->bymonthday);
 	/* Similarly as for recurrent appointment. */
 	recur_exc_dup(&rev->exc, &rpt->exc);
 	recur_free_exc_list(&rpt->exc);
@@ -367,6 +417,39 @@ int recur_char2def(char type)
 	return recur_def;
 }
 
+/* Write the bymonthday list. */
+static void bymonthday_append(struct string *s, llist_t *l)
+{
+	llist_item_t *i;
+
+	LLIST_FOREACH(l, i) {
+		int *day = LLIST_GET_DATA(i);
+		string_catf(s, " d%d", *day);
+	}
+}
+
+/* Write the bywday list. */
+static void bywday_append(struct string *s, llist_t *l)
+{
+	llist_item_t *i;
+
+	LLIST_FOREACH(l, i) {
+		int *wday = LLIST_GET_DATA(i);
+		string_catf(s, " w%d", *wday);
+	}
+}
+
+/* Write the bymonth list. */
+static void bymonth_append(struct string *s, llist_t *l)
+{
+	llist_item_t *i;
+
+	LLIST_FOREACH(l, i) {
+		int *mon = LLIST_GET_DATA(i);
+		string_catf(s, " m%d", *mon);
+	}
+}
+
 /* Write days for which recurrent items should not be repeated. */
 static void recur_exc_append(struct string *s, llist_t *lexc)
 {
@@ -546,6 +629,9 @@ char *recur_apoint_tostr(struct recur_apoint *o)
 			recur_def2char(o->rpt->type), lt.tm_mon + 1,
 			lt.tm_mday, 1900 + lt.tm_year);
 	}
+	bymonthday_append(&s, &o->rpt->bymonthday);
+	bywday_append(&s, &o->rpt->bywday);
+	bymonth_append(&s, &o->rpt->bymonth);
 	recur_exc_append(&s, &o->exc);
 	string_catf(&s, "} ");
 	if (o->note)
@@ -607,6 +693,9 @@ char *recur_event_tostr(struct recur_event *o)
 			recur_def2char(o->rpt->type), end_mon, end_day,
 			end_year);
 	}
+	bymonthday_append(&s, &o->rpt->bymonthday);
+	bywday_append(&s, &o->rpt->bywday);
+	bymonth_append(&s, &o->rpt->bymonth);
 	recur_exc_append(&s, &o->exc);
 	string_catf(&s, "} ");
 	if (o->note)
@@ -652,6 +741,20 @@ void recur_save_data(FILE * f)
 }
 
 /*
+ * Return the month day counted from the opposite end of the month.
+ */
+static int opp_mday(int year, int month, int day)
+{
+	EXIT_IF(day == 0, _("month day is zero"));
+
+	int m_days = days[month - 1] + (month == 2 && ISLEAP(year));
+	if (day > 0)
+		return day - 1 - m_days;
+	else
+		return day + 1 + m_days;
+}
+
+/*
  * The two following defines together with the diff_days, diff_months and
  * diff_years functions were provided by Lukas Fleischer to correct the wrong
  * calculation of recurrent dates after a turn of year.
@@ -702,45 +805,54 @@ static long diff_years(struct tm lt_start, struct tm lt_end)
 	return lt_end.tm_year - lt_start.tm_year;
 }
 
-static int exc_inday(struct excp *exc, time_t *day_start)
+/*
+ * Return true if 'mon' and 'mday' is month and day of t
+ * (after a call of mktime()).
+ */
+static int date_chk(time_t t, int mon, int mday)
 {
-	return (date_cmp_day(exc->st, *day_start) == 0);
+	struct tm tm;
+
+	localtime_r(&t, &tm);
+
+	return tm.tm_mon == mon && tm.tm_mday == mday;
 }
 
 /*
- * Return true if the recurrent item has an occurrence on the given day
- * and, if so, store the start date of that occurrence in a buffer.
+ * Return true if the rrule (start, dur, rpt, exc) has an occurrence on the
+ * given day. If so, save that occurrence in a (dynamic or static) buffer.
  */
-unsigned
-recur_item_find_occurrence(time_t start, long dur, struct rpt *rpt, llist_t *exc,
-			   time_t day_start, time_t *occurrence)
+static int find_occurrence(time_t start, long dur, struct rpt *rpt, llist_t *exc,
+			   time_t day, time_t *occurrence)
 {
 	/*
-	 * Duration fix.
+	 * Duration-on-day-d fix.
 	 * An item cannot end on midnight or else it is counted towards the next day.
 	 * An event (dur == -1) has no explicit duration, but is considered to last for
-	 * the entire day which depends on DST.
+	 * the entire day (d) which depends on DST.
 	 */
 #define DUR(d)	(dur == -1 ? DAYLEN((d)) - 1 : dur - 1)
 
 	long diff;
-	struct tm lt_day, lt_item, lt_occur;
-	time_t occ;
+	struct tm lt_day, lt_start, lt_occur;
+	time_t t;
+	int mday, order, pwday, nwday, mon;
 
 	/* Is the given day before the day of the first occurence? */
-	if (date_cmp_day(day_start, start) < 0)
+	if (date_cmp_day(day, start) < 0)
 		return 0;
+
 	/*
 	 * - or after the day of the last occurrence (which may stretch beyond
 	 * the until date)? Extraneous days are eliminated later.
 	 */
 	if (rpt->until &&
-	    date_cmp_day(NEXTDAY(rpt->until) + DUR(rpt->until), day_start) < 0)
+	    date_cmp_day(NEXTDAY(rpt->until) + DUR(rpt->until), day) < 0)
 		return 0;
 
-	localtime_r(&day_start, &lt_day); /* Given day. */
-	localtime_r(&start, &lt_item);    /* Original item. */
-	lt_occur = lt_item;		  /* First occurence. */
+	localtime_r(&day, &lt_day);	/* Given day. */
+	localtime_r(&start, &lt_start);	/* Original item. */
+	lt_occur = lt_start;		/* First occurence. */
 
 	/*
 	 * Update to the most recent occurrence before or on the selected day.
@@ -782,39 +894,584 @@ recur_item_find_occurrence(time_t start, long dur, struct rpt *rpt, llist_t *exc
 
 	/* Switch to calendar (Unix) time. */
 	lt_occur.tm_isdst = -1;
-	occ = mktime(&lt_occur);
+	t = mktime(&lt_occur);
 
 	/*
 	 * Impossible dates must be ignored (according to RFC 5545). Changing
 	 * only the year or the month may lead to dates like 29 February in
 	 * non-leap years or 31 November.
 	 */
-	if (rpt->type == RECUR_MONTHLY || rpt->type == RECUR_YEARLY) {
-		localtime_r(&occ, &lt_occur);
-		if (lt_occur.tm_mday != lt_item.tm_mday)
+	if ((rpt->type == RECUR_MONTHLY || rpt->type == RECUR_YEARLY) &&
+	    !date_chk(t, lt_occur.tm_mon, lt_start.tm_mday))
+			return 0;
+
+	/*
+	 * BYMONTHDAY reduction
+	 * A month day has two possible list forms.
+	 */
+	mday = opp_mday(lt_occur.tm_year + 1900, lt_occur.tm_mon + 1,
+		     lt_occur.tm_mday);
+	if (rpt->bymonthday.head &&
+	    rpt->type == RECUR_DAILY &&
+	    !LLIST_FIND_FIRST(&rpt->bymonthday, &lt_occur.tm_mday, int_cmp) &&
+	    !LLIST_FIND_FIRST(&rpt->bymonthday, &mday, int_cmp))
+		return 0;
+
+	/* BYDAY reduction for DAILY */
+	if (rpt->bywday.head && rpt->type == RECUR_DAILY &&
+	    !LLIST_FIND_FIRST(&rpt->bywday, &lt_occur.tm_wday, int_cmp))
+		return 0;
+
+	/*
+	 * BYDAY reduction for MONTHLY
+	 * A weekday has three possible list forms.
+	 */
+	if (rpt->bywday.head &&
+	    rpt->type == RECUR_MONTHLY && rpt->bymonthday.head) {
+		/* positive order */
+		order = (lt_occur.tm_mday + 6) / WEEKINDAYS;
+		pwday = order * WEEKINDAYS  + lt_occur.tm_wday;
+		/* negative order */
+		order = order
+			- wday_per_month(lt_occur.tm_mon + 1,
+					 lt_occur.tm_year + 1900,
+					 lt_occur.tm_wday)
+			- 1;
+		nwday = order * WEEKINDAYS - lt_occur.tm_wday;
+		if (!LLIST_FIND_FIRST(&rpt->bywday, &lt_occur.tm_wday, int_cmp) &&
+		    !LLIST_FIND_FIRST(&rpt->bywday, &pwday, int_cmp) &&
+		    !LLIST_FIND_FIRST(&rpt->bywday, &nwday, int_cmp))
 			return 0;
 	}
 
+	/*
+	 * BYDAY reduction for YEARLY
+	 * A weekday has three possible list forms.
+	 */
+	if (rpt->bywday.head &&
+	    rpt->type == RECUR_YEARLY && rpt->bymonthday.head) {
+		/* positive order */
+		order = lt_occur.tm_yday / WEEKINDAYS;
+		pwday = order * WEEKINDAYS  + lt_occur.tm_wday;
+		/* negative order */
+		order = order
+			- wday_per_year(lt_occur.tm_year + 1900,
+					lt_occur.tm_wday)
+			- 1;
+		nwday = order * WEEKINDAYS - lt_occur.tm_wday;
+		if (!LLIST_FIND_FIRST(&rpt->bywday, &lt_occur.tm_wday, int_cmp) &&
+		    !LLIST_FIND_FIRST(&rpt->bywday, &pwday, int_cmp) &&
+		    !LLIST_FIND_FIRST(&rpt->bywday, &nwday, int_cmp))
+			return 0;
+	}
+
+	/* BYMONTH reduction */
+	mon = lt_occur.tm_mon + 1;
+	if (rpt->bymonth.head &&
+	    rpt->type != RECUR_YEARLY &&
+	    !LLIST_FIND_FIRST(&rpt->bymonth, &mon, int_cmp))
+		return 0;
+
 	/* Exception day? */
-	if (LLIST_FIND_FIRST(exc, &occ, exc_inday))
+	if (LLIST_FIND_FIRST(exc, &t, exc_inday))
 		return 0;
 
 	/* Extraneous day? */
-	if (rpt->until && occ >= NEXTDAY(rpt->until))
+	if (rpt->until && t >= NEXTDAY(rpt->until))
 		return 0;
 
 	/* Does it span the given day? */
-	if (occ + DUR(occ) < day_start)
+	if (t + DUR(t) < day)
 		return 0;
 
 	if (occurrence)
-		*occurrence = occ;
+		*occurrence = t;
 
 	return 1;
 #undef ITEM_DUR
 }
 #undef DUR
 
+/*
+ * Return true if the rrule (s, d, r, e) has an occurrence, depending
+ * on the frequency, in the year, month or week of day.
+ */
+static int freq_chk(time_t day, time_t s, long d, struct rpt *r, llist_t *e)
+{
+	if (r->type == RECUR_DAILY)
+		EXIT(_("no daily frequency check"));
+
+	struct tm tm_start, tm_day;
+	struct rpt fc_rpt;
+	time_t fc_day, fc_s;
+
+	localtime_r(&s, &tm_start);
+	localtime_r(&day, &tm_day);
+
+	if (r->type == RECUR_WEEKLY) {
+		/* Set day to the weekly occurrence. */
+		fc_day = date_sec_change(
+			day,
+			0,
+			WDAY(tm_start.tm_wday) - WDAY(tm_day.tm_wday)
+		      );
+		fc_s = s;
+	} else {
+		/* The start day may be invalid in some months. */
+		tm_day.tm_mday = tm_start.tm_mday = 1;
+		if (r->type == RECUR_YEARLY)
+			tm_day.tm_mon = tm_start.tm_mon;
+		tm_day.tm_isdst = tm_start.tm_isdst = -1;
+		fc_day = mktime(&tm_day);
+		fc_s = mktime(&tm_start);
+	}
+	/* Turn all reductions off. */
+	fc_rpt = *r;
+	fc_rpt.until = 0;
+	fc_rpt.bymonth.head = fc_rpt.bywday.head = fc_rpt.bymonthday.head = NULL;
+
+	return find_occurrence(fc_s, d, &fc_rpt, e, fc_day, NULL);
+}
+
+/*
+ * Return true if the rrule (s, d, r, e) has an occurrence on 'day' after
+ * 'first'; if so, return it in occurrence.
+ */
+static int test_occurrence(time_t s, long d, struct rpt *r, llist_t *e,
+			   time_t first, time_t day, time_t *occurrence)
+{
+	time_t occ;
+
+	if (find_occurrence(s, d, r, e, day, &occ)) {
+		if (occ < first)
+			return 0;
+		if (occurrence)
+			*occurrence = occ;
+		return 1;
+	}
+	return 0;
+}
+
+#define NO_EXPANSION	-1
+static int expand_weekly(time_t start, long dur, struct rpt *rpt, llist_t *exc,
+			   time_t day, time_t *occurrence)
+{
+	struct tm tm_start;
+	llist_item_t *i;
+	int *w;
+	time_t w_start;
+
+	localtime_r(&start, &tm_start);
+
+	/* BYDAY expansion */
+	if (rpt->bywday.head) {
+		LLIST_FOREACH(&rpt->bywday, i) {
+			w = LLIST_GET_DATA(i);
+			if (*w < 0 || *w > 6)
+				continue;
+			/*
+			 * Modify rrule start with a new day in the same week as
+			 * start - taking first day of the week into account.
+			 */
+			w_start = date_sec_change(
+					start,
+					0,
+					WDAY(*w) - WDAY(tm_start.tm_wday)
+				);
+			if (test_occurrence(w_start, dur, rpt, exc,
+					    start, day, occurrence))
+				return 1;
+		}
+	} else
+		return NO_EXPANSION;
+
+	/* No occurrence */
+	return 0;
+}
+
+static int expand_monthly(time_t start, long dur, struct rpt *rpt, llist_t *exc,
+			   time_t day, time_t *occurrence)
+{
+	struct tm tm_start, tm_day;
+	llist_item_t *i;
+	int *w, mday, mon, valid;
+	time_t nstart;
+	struct rpt r = *rpt;
+
+	localtime_r(&day, &tm_day);
+
+	/*
+	 * The following three conditional alternatives are mutually exclusive
+	 * and cover all four cases of two booleans.
+	 */
+
+	/* BYMONTHDAY expansion */
+	if (rpt->bymonthday.head) {
+		LLIST_FOREACH(&rpt->bymonthday, i) {
+			mday = *(int *)LLIST_GET_DATA(i);
+
+			if (mday < 0)
+				mday = opp_mday(tm_day.tm_year + 1900,
+						tm_day.tm_mon + 1, mday);
+			/*
+			 * Modify rrule start with a new monthday.
+			 * If it is invalid (29, 30 or 31) in the start month,
+			 * the month is changed to an earlier one matching the
+			 * frequency.
+			 */
+			localtime_r(&start, &tm_start);
+			mon = tm_start.tm_mon;
+
+			tm_start.tm_mday = mday;
+			tm_start.tm_isdst = -1;
+			nstart = mktime(&tm_start);
+			valid = date_chk(nstart, mon, mday);
+			/* Never valid? */
+			if (!valid && !(rpt->freq % 12))
+				return 0;
+			/* Note. The loop will terminate! */
+			while (!valid) {
+				localtime_r(&start, &tm_start);
+				mon -= rpt->freq;
+				tm_start.tm_mon = mon;
+				tm_start.tm_mday = mday;
+				tm_start.tm_isdst = -1;
+				nstart = mktime(&tm_start);
+				valid = date_chk(nstart, (mon + 12) % 12, mday);
+			}
+			if (test_occurrence(nstart, dur, rpt, exc,
+					    start, day, occurrence))
+				return 1;
+		}
+	}
+	/* BYDAY special expansion for MONTHLY */
+	else if (rpt->bywday.head) {
+		/* The frequency is modified later. */
+		if (!freq_chk(day, start, dur, rpt, exc))
+			return 0;
+
+		LLIST_FOREACH(&rpt->bywday, i) {
+			w = LLIST_GET_DATA(i);
+
+			int order, wday;
+
+			localtime_r(&start, &tm_start);
+			/*
+			 * Construct a weekly rrule; BYMONTH-reduction in
+			 * find_occurrence() will reduce to the bymonth list.
+			 */
+			r.type = RECUR_WEEKLY;
+			if (*w > 6) {
+				/*
+				 * A single occurrence counting forwards from
+				 * the start of the month.
+				 */
+				order = *w / WEEKINDAYS;
+				wday = *w % WEEKINDAYS;
+				r.freq = order;
+				tm_start.tm_mday = 1;
+				tm_start.tm_mon = tm_day.tm_mon;
+				tm_start.tm_year = tm_day.tm_year;
+				tm_start.tm_isdst = -1;
+				/* Start in the week before the month. */
+				nstart = date_sec_change(
+					next_wday(mktime(&tm_start), wday),
+					0,
+					-WEEKINDAYS
+				);
+				r.until = date_sec_change(
+					update_time_in_date(nstart, 0, 0),
+					0,
+					r.freq * WEEKINDAYS
+				);
+				if (rpt->until && r.until > rpt->until)
+					return 0;
+			} else if (*w > -1) {
+				/* Expansion to each week. */
+				wday = *w % WEEKINDAYS;
+				r.freq = 1;
+				nstart = next_wday(start, wday);
+			} else if (*w < -6) {
+				/*
+				 * A single ocurrence counting backwards from
+				 * the end of the month.
+				 */
+				order = -(*w) / WEEKINDAYS;
+				wday = -(*w) % WEEKINDAYS;
+				r.freq = wday_per_month(
+						tm_day.tm_mon + 1,
+						tm_day.tm_year + 1900,
+						wday
+					 ) - order + 1;
+				tm_start.tm_mday = 1;
+				tm_start.tm_mon = tm_day.tm_mon;
+				tm_start.tm_year = tm_day.tm_year;
+				tm_start.tm_isdst = -1;
+				nstart = date_sec_change(
+					next_wday(mktime(&tm_start), wday),
+					0,
+					-WEEKINDAYS
+				);
+				r.until = date_sec_change(
+					update_time_in_date(nstart, 0, 0),
+					0,
+					r.freq * WEEKINDAYS
+				);
+				if (rpt->until && r.until > rpt->until)
+					return 0;
+			} else
+				EXIT(_("illegal BYDAY value"));
+
+			if (test_occurrence(nstart, dur, &r, exc,
+					    start, day, occurrence))
+				return 1;
+		}
+	}
+	else
+		return NO_EXPANSION;
+
+	/* No occurrence */
+	return 0;
+}
+
+static int expand_yearly(time_t start, long dur, struct rpt *rpt, llist_t *exc,
+			   time_t day, time_t *occurrence)
+{
+	struct tm tm_start, tm_day;
+	llist_item_t *i, *j;
+	int *m, *w, mday, wday, order;
+	time_t nstart;
+	struct rpt r;
+
+	localtime_r(&day, &tm_day);
+	/*
+	 * The following five conditional alternatives are mutually exclusive
+	 * and cover all eight cases of three booleans.
+	 */
+	/* BYMONTH expansion */
+	if (rpt->bymonth.head && !rpt->bymonthday.head && !rpt->bywday.head) {
+		LLIST_FOREACH(&rpt->bymonth, i) {
+			m = LLIST_GET_DATA(i);
+
+			/* Modify rrule start with new month. */
+			localtime_r(&start, &tm_start);
+			tm_start.tm_mon = *m - 1;
+			tm_start.tm_isdst = -1;
+			nstart = mktime(&tm_start);
+			if (!date_chk(nstart, *m - 1, tm_start.tm_mday))
+				continue;
+			if (find_occurrence(nstart, dur, rpt, exc, day,
+					    occurrence))
+				return 1;
+		}
+	} else
+	/* BYDAY special expansion for MONTHLY or YEARLY */
+	if (!rpt->bymonthday.head && rpt->bywday.head) {
+		/* Check needed because frequency is modified later. */
+		if (!freq_chk(day, start, dur, rpt, exc))
+			return 0;
+
+		LLIST_FOREACH(&rpt->bywday, i) {
+			w = LLIST_GET_DATA(i);
+
+			localtime_r(&start, &tm_start);
+			/*
+			 * Construct a suitable weekly rrule. BYMONTH
+			 * reduction in find_occurrence() will limit
+			 * occurrences if needed.
+			 */
+			r = *rpt;
+			r.type = RECUR_WEEKLY;
+			if (*w > 6) {
+				/*
+				 * Special expand: A single ocurrence counting
+				 * forward from the start of the month/year.
+				 * Start in the week before with a frequency
+				 * that matches the ordered weekday and with
+				 * until day that allows only one occurrence.
+				 */
+				order = *w / WEEKINDAYS;
+				wday = *w % WEEKINDAYS;
+				r.freq = order;
+				tm_start.tm_mday = 1;
+				if (rpt->bymonth.head)
+					tm_start.tm_mon = tm_day.tm_mon;
+				else
+					tm_start.tm_mon = 0;
+				tm_start.tm_year = tm_day.tm_year;
+				tm_start.tm_isdst = -1;
+				nstart = date_sec_change(
+					next_wday(mktime(&tm_start), wday),
+					0,
+					-WEEKINDAYS
+				);
+				r.until = date_sec_change(
+					update_time_in_date(nstart, 0, 0),
+					0,
+					r.freq * WEEKINDAYS
+				);
+				if (rpt->until && r.until > rpt->until)
+					return 0;
+			} else if (*w > -1) {
+				/* Expand to each week of the month/year. */
+				wday = *w % WEEKINDAYS;
+				r.freq = 1;
+				nstart = next_wday(start, wday);
+			} else if (*w < -6) {
+				/*
+				 * Special expand: A single ocurrence counting
+				 * backward from the end of the month/year.
+				 */
+				order = -(*w) / WEEKINDAYS;
+				wday = -(*w) % WEEKINDAYS;
+				if (rpt->bymonth.head) {
+					r.freq = wday_per_month(
+							tm_day.tm_mon + 1,
+							tm_day.tm_year + 1900,
+							wday
+						 ) - order + 1;
+					tm_start.tm_mon = tm_day.tm_mon;
+				} else {
+					r.freq = wday_per_year(
+							tm_day.tm_year + 1900,
+							wday
+						 ) - order + 1;
+					tm_start.tm_mon = 0;
+				}
+				tm_start.tm_mday = 1;
+				tm_start.tm_year = tm_day.tm_year;
+				tm_start.tm_isdst = -1;
+				nstart = date_sec_change(
+					next_wday(mktime(&tm_start), wday),
+					0,
+					-WEEKINDAYS
+				);
+				r.until = date_sec_change(
+					update_time_in_date(nstart, 0, 0),
+					0,
+					r.freq * WEEKINDAYS
+				);
+				if (rpt->until && r.until > rpt->until)
+					return 0;
+			} else
+				EXIT(_("illegal BYDAY value"));
+
+			if (test_occurrence(nstart, dur, &r, exc,
+					    start, day, occurrence))
+				return 1;
+		}
+	} else
+	/* BYMONTHDAY expansion */
+	if (!rpt->bymonth.head && rpt->bymonthday.head) {
+		LLIST_FOREACH(&rpt->bymonthday, i) {
+			mday = *(int *)LLIST_GET_DATA(i);
+			if (mday < 0)
+				mday = opp_mday(
+					   tm_day.tm_year + 1900,
+					   tm_day.tm_mon + 1, mday
+				       );
+			/* Modify rrule start with new monthday. */
+			localtime_r(&start, &tm_start);
+			tm_start.tm_mday = mday;
+			tm_start.tm_isdst = -1;
+			nstart = mktime(&tm_start);
+			if (!date_chk(nstart, tm_start.tm_mon, mday))
+				continue;
+			if (find_occurrence(nstart, dur, rpt, exc, day,
+					    occurrence))
+				return 1;
+		}
+	} else
+	/* BYMONTH and BYMONTHDAY expansion */
+	if (rpt->bymonth.head && rpt->bymonthday.head) {
+		LLIST_FOREACH(&rpt->bymonth, i) {
+			m = LLIST_GET_DATA(i);
+
+			LLIST_FOREACH(&rpt->bymonthday, j) {
+				mday = *(int *)LLIST_GET_DATA(j);
+				if (mday < 0)
+					mday = opp_mday(
+						   tm_day.tm_year + 1900,
+						   tm_day.tm_mon + 1, mday
+					       );
+				/* Modify start with new monthday and month. */
+				localtime_r(&start, &tm_start);
+				/* Number of days in February! */
+				if (*m == 2 && mday == 29 &&
+				    !ISLEAP(tm_start.tm_year + 1900) &&
+				    rpt->freq % 4) {
+					if (!freq_chk(day, start, dur, rpt, exc))
+						return 0;
+					tm_start.tm_year -= tm_start.tm_year % 4;
+				}
+				tm_start.tm_mday = mday;
+				tm_start.tm_mon = *m - 1;
+				tm_start.tm_isdst = -1;
+				nstart = mktime(&tm_start);
+				if (!date_chk(nstart, *m - 1, mday))
+					continue;
+				if (find_occurrence(nstart, dur, rpt, exc, day,
+						    occurrence))
+					return 1;
+			}
+		}
+	} else
+		return NO_EXPANSION;
+
+	/* No occurrence */
+	return 0;
+}
+
+/*
+ * Membership test for the recurrence set of the rrule (start, dur, rpt, exc).
+ *
+ * Return true if day belongs to the set. If so, the occurrence is saved in a
+ * buffer. A positive result is always the outcome of find_occurrence(), whereas
+ * a negative result may be arrived at in other ways.
+ *
+ * The basic (type, frequency)-check is in find_occurrence(). When recurrence
+ * set expansion and/or reduction (RFC 5545) is needed, expansion is done before
+ * call of find_occurrence(), while reduction takes place in find_occurrence().
+ *
+ * Recurrence set expansion is accomplished by a combination of calls of
+ * find_occurrence(), possibly with change of type, frequency and start.
+ */
+unsigned
+recur_item_find_occurrence(time_t start, long dur, struct rpt *rpt, llist_t *exc,
+			   time_t day, time_t *occurrence)
+{
+	int res;
+
+	/* To make it possible to set an earlier start without expanding the
+	 * recurrence set. */
+	if (date_cmp_day(day, start) < 0)
+		return 0;
+
+	switch (rpt->type) {
+	case RECUR_DAILY:
+		res = NO_EXPANSION;
+		break;
+	case RECUR_WEEKLY:
+		res = expand_weekly(start, dur, rpt, exc, day, occurrence);
+		break;
+	case RECUR_MONTHLY:
+		res = expand_monthly(start, dur, rpt, exc, day, occurrence);
+		break;
+	case RECUR_YEARLY:
+		res = expand_yearly(start, dur, rpt, exc, day, occurrence);
+		break;
+	default:
+		res = 0;
+	}
+
+	if (res == NO_EXPANSION)
+		return find_occurrence(start, dur, rpt, exc, day, occurrence);
+
+	/* The result of find_occurrence() is passed on. */
+	return res;
+}
+#undef NO_EXPANSION
+
 unsigned
 recur_apoint_find_occurrence(struct recur_apoint *rapt, time_t day_start,
 			     time_t *occurrence)
@@ -910,6 +1567,62 @@ void recur_apoint_erase(struct recur_apoint *rapt)
 	LLIST_TS_UNLOCK(&recur_alist_p);
 }
 
+/* Read monthday list. */
+void recur_bymonthday(llist_t *l, FILE *data_file)
+{
+	int c = 0, d;
+
+	LLIST_INIT(l);
+	while ((c = getc(data_file)) == 'd') {
+		ungetc(c, data_file);
+		if (fscanf(data_file, "d%d ", &d) != 1)
+			EXIT(_("syntax error in bymonthday"));
+		int *i = mem_malloc(sizeof(int));
+		*i = d;
+		LLIST_ADD(l, i);
+	}
+	ungetc(c, data_file);
+}
+
+/* Read weekday list. */
+void recur_bywday(enum recur_type type, llist_t *l, FILE *data_file)
+{
+	int c = 0, w;
+
+	type = !(type == RECUR_MONTHLY || type == RECUR_YEARLY);
+
+	LLIST_INIT(l);
+	while ((c = getc(data_file)) == 'w') {
+		ungetc(c, data_file);
+		if (fscanf(data_file, "w%d ", &w) != 1)
+			EXIT(_("syntax error in bywday"));
+		if (type && (w < 0 || w > 6))
+			EXIT(_("illegal BYDAY value"));
+		int *i = mem_malloc(sizeof(int));
+		*i = w;
+		LLIST_ADD(l, i);
+	}
+	ungetc(c, data_file);
+}
+
+/* Read month list. */
+void recur_bymonth(llist_t *l, FILE *data_file)
+{
+	int c = 0, m;
+
+	LLIST_INIT(l);
+	while ((c = getc(data_file)) == 'm') {
+		ungetc(c, data_file);
+		if (fscanf(data_file, "m%d ", &m) != 1)
+			EXIT(_("syntax error in bymonth"));
+		EXIT_IF(m < 1 || m > 12, _("illegal bymonth value"));
+		int *i = mem_malloc(sizeof(int));
+		*i = m;
+		LLIST_ADD(l, i);
+	}
+	ungetc(c, data_file);
+}
+
 /*
  * Read days for which recurrent items must not be repeated
  * (such days are called exceptions).
diff --git a/src/ui-day.c b/src/ui-day.c
index f2bcba5..3aa1e52 100644
--- a/src/ui-day.c
+++ b/src/ui-day.c
@@ -987,6 +987,9 @@ void ui_day_item_repeat(void)
 	rpt.type = type;
 	rpt.freq = freq;
 	rpt.until = until;
+	LLIST_INIT(&rpt.bymonth);
+	LLIST_INIT(&rpt.bywday);
+	LLIST_INIT(&rpt.bymonthday);
 	LLIST_INIT(&rpt.exc);
 	if (p->type == EVNT) {
 		struct event *ev = p->item.ev;
diff --git a/src/utils.c b/src/utils.c
index c19c800..5322db1 100644
--- a/src/utils.c
+++ b/src/utils.c
@@ -2009,3 +2009,61 @@ long overflow_mul(long x, long y, long *z)
 	*z = x * y;
 	return 0;
 }
+
+/*
+ * Return the upcoming weekday from day (possibly day itself).
+ */
+time_t next_wday(time_t day, int weekday)
+{
+	struct tm tm;
+
+	localtime_r(&day, &tm);
+	return date_sec_change(
+		day, 0, (weekday - tm.tm_wday + WEEKINDAYS) % WEEKINDAYS
+	);
+
+}
+
+/*
+ * Return the number of weekdays of the year.
+ */
+int wday_per_year(int year, int weekday)
+{
+	struct tm y_end;
+	struct date day;
+	int last_wday;
+
+	/* Find weekday and yearday of the last day of the year.  */
+	day.dd = 31;
+	day.mm = 12;
+	day.yyyy = year;
+	y_end = date2tm(day, 0, 0);
+	mktime(&y_end);
+
+	/* Find date of the last weekday of the year. */
+	last_wday = (y_end.tm_yday + 1) - (y_end.tm_wday - weekday + 7) % 7;
+
+	return last_wday / 7 + (last_wday % 7 > 0);
+}
+
+/*
+ * Return the number of weekdays in month of year.
+ */
+int wday_per_month(int month, int year, int weekday)
+{
+	struct tm m_end;
+	struct date day;
+	int last_wday, m_days = days[month - 1] + (month == 2 && ISLEAP(year) ? 1 : 0);
+
+	/* Find weekday of the last day of the month. */
+	day.dd = m_days;
+	day.mm = month;
+	day.yyyy = year;
+	m_end = date2tm(day, 0, 0);
+	mktime(&m_end);
+
+	/* Find date of the last weekday of the month. */
+	last_wday = m_days - (m_end.tm_wday - weekday + 7) % 7;
+
+	return last_wday / 7 + (last_wday % 7 > 0);
+}