Merge pull request #4904 from dobyrch/calendar-range-step

calendarspec: allow repetition values with ranges

4 files changed, 146 insertions, 120 deletions

diff --git a/man/systemd.time.xml b/man/systemd.time.xml
index c182d4f37a..d30c6cffc9 100644
--- a/man/systemd.time.xml
+++ b/man/systemd.time.xml
@@ -217,11 +217,12 @@
     <para>In the date and time specifications, any component may be
     specified as <literal>*</literal> in which case any value will
     match. Alternatively, each component can be specified as a list of
-    values separated by commas. Values may also be suffixed with
+    values separated by commas. Values may be suffixed with
     <literal>/</literal> and a repetition value, which indicates that
     the value itself and the value plus all multiples of the repetition value
-    are matched.  Each component may also contain a range of values
-    separated by <literal>..</literal>.</para>
+    are matched.  Two values separated by <literal>..</literal> may be used
+    to indicate a range of values; ranges may also be followed with
+    <literal>/</literal> and a repetition value.</para>
 
     <para>A date specification may use <literal>~</literal> to indicate the
     last day(s) in a month. For example, <literal>*-02~03</literal> means
@@ -281,7 +282,7 @@ Wed..Sat,Tue 12-10-15 1:2:3 → Tue..Sat 2012-10-15 01:02:03
      Sat,Sun 12-05 08:05:40 → Sat,Sun *-12-05 08:05:40
            Sat,Sun 08:05:40 → Sat,Sun *-*-* 08:05:40
            2003-03-05 05:40 → 2003-03-05 05:40:00
- 05:40:23.4200004/3.1700005 → 05:40:23.420000/3.170001
+ 05:40:23.4200004/3.1700005 → *-*-* 05:40:23.420000/3.170001
              2003-02..04-05 → 2003-02..04-05 00:00:00
        2003-03-05 05:40 UTC → 2003-03-05 05:40:00 UTC
                  2003-03-05 → 2003-03-05 00:00:00
diff --git a/src/basic/calendarspec.c b/src/basic/calendarspec.c
index adf79eb533..3e249505a5 100644
--- a/src/basic/calendarspec.c
+++ b/src/basic/calendarspec.c
@@ -33,11 +33,9 @@
 #include "parse-util.h"
 #include "string-util.h"
 
-/* Longest valid date/time range is 1970..2199 */
-#define MAX_RANGE_LEN   230
-#define MIN_YEAR       1970
-#define MAX_YEAR       2199
-#define BITS_WEEKDAYS   127
+#define BITS_WEEKDAYS 127
+#define MIN_YEAR 1970
+#define MAX_YEAR 2199
 
 static void free_chain(CalendarComponent *c) {
         CalendarComponent *n;
@@ -67,9 +65,14 @@ void calendar_spec_free(CalendarSpec *c) {
 static int component_compare(const void *_a, const void *_b) {
         CalendarComponent * const *a = _a, * const *b = _b;
 
-        if ((*a)->value < (*b)->value)
+        if ((*a)->start < (*b)->start)
                 return -1;
-        if ((*a)->value > (*b)->value)
+        if ((*a)->start > (*b)->start)
+                return 1;
+
+        if ((*a)->stop < (*b)->stop)
+                return -1;
+        if ((*a)->stop > (*b)->stop)
                 return 1;
 
         if ((*a)->repeat < (*b)->repeat)
@@ -80,15 +83,24 @@ static int component_compare(const void *_a, const void *_b) {
         return 0;
 }
 
-static void sort_chain(CalendarComponent **c) {
+static void normalize_chain(CalendarComponent **c) {
         unsigned n = 0, k;
         CalendarComponent **b, *i, **j, *next;
 
         assert(c);
 
-        for (i = *c; i; i = i->next)
+        for (i = *c; i; i = i->next) {
                 n++;
 
+                /*
+                 * While we're counting the chain, also normalize `stop`
+                 * so the length of the range is a multiple of `repeat`
+                 */
+                if (i->stop > i->start)
+                        i->stop -= (i->stop - i->start) % i->repeat;
+
+        }
+
         if (n <= 1)
                 return;
 
@@ -103,7 +115,7 @@ static void sort_chain(CalendarComponent **c) {
 
         /* Drop non-unique entries */
         for (k = n-1; k > 0; k--) {
-                if (b[k-1]->value == next->value &&
+                if (b[k-1]->start == next->start &&
                     b[k-1]->repeat == next->repeat) {
                         free(b[k-1]);
                         continue;
@@ -120,15 +132,19 @@ static void fix_year(CalendarComponent *c) {
         /* Turns 12 → 2012, 89 → 1989 */
 
         while (c) {
-                CalendarComponent *n = c->next;
+                if (c->start >= 0 && c->start < 70)
+                        c->start += 2000;
 
-                if (c->value >= 0 && c->value < 70)
-                        c->value += 2000;
+                if (c->stop >= 0 && c->stop < 70)
+                        c->stop += 2000;
 
-                if (c->value >= 70 && c->value < 100)
-                        c->value += 1900;
+                if (c->start >= 70 && c->start < 100)
+                        c->start += 1900;
 
-                c = n;
+                if (c->stop >= 70 && c->stop < 100)
+                        c->stop += 1900;
+
+                c = c->next;
         }
 }
 
@@ -143,12 +159,12 @@ int calendar_spec_normalize(CalendarSpec *c) {
 
         fix_year(c->year);
 
-        sort_chain(&c->year);
-        sort_chain(&c->month);
-        sort_chain(&c->day);
-        sort_chain(&c->hour);
-        sort_chain(&c->minute);
-        sort_chain(&c->microsecond);
+        normalize_chain(&c->year);
+        normalize_chain(&c->month);
+        normalize_chain(&c->day);
+        normalize_chain(&c->hour);
+        normalize_chain(&c->minute);
+        normalize_chain(&c->microsecond);
 
         return 0;
 }
@@ -157,20 +173,32 @@ _pure_ static bool chain_valid(CalendarComponent *c, int from, int to, bool end_
         if (!c)
                 return true;
 
-        if (c->value < from || c->value > to)
+        /* Forbid dates more than 28 days from the end of the month */
+        if (end_of_month)
+                to -= 3;
+
+        if (c->start < from || c->start > to)
                 return false;
 
         /*
          * c->repeat must be short enough so at least one repetition may
          * occur before the end of the interval.  For dates scheduled
-         * relative to the end of the month, c->value corresponds to the
-         * Nth last day of the month.
+         * relative to the end of the month, c->start and c->stop
+         * correspond to the Nth last day of the month.
          */
-        if (end_of_month && c->value - c->repeat < from)
-                return false;
+        if (c->stop >= 0) {
+                if (c->stop < from || c ->stop > to)
+                        return false;
 
-        if (!end_of_month && c->value + c->repeat > to)
-                return false;
+                if (c->start + c->repeat > c->stop)
+                        return false;
+        } else {
+                if (end_of_month && c->start - c->repeat < from)
+                        return false;
+
+                if (!end_of_month && c->start + c->repeat > to)
+                        return false;
+        }
 
         if (c->next)
                 return chain_valid(c->next, from, to, end_of_month);
@@ -255,7 +283,6 @@ static void format_weekdays(FILE *f, const CalendarSpec *c) {
 }
 
 static void format_chain(FILE *f, int space, const CalendarComponent *c, bool usec) {
-        const CalendarComponent *n, *p;
         int d = usec ? (int) USEC_PER_SEC : 1;
 
         assert(f);
@@ -265,41 +292,34 @@ static void format_chain(FILE *f, int space, const CalendarComponent *c, bool us
                 return;
         }
 
-        assert(c->value >= 0);
-
-        fprintf(f, "%0*i", space, c->value / d);
-        if (c->value % d != 0)
-                fprintf(f, ".%06i", c->value % d);
+        if (usec && c->start == 0 && c->repeat == USEC_PER_SEC && !c->next) {
+                fputc('*', f);
+                return;
+        }
 
-        if (c->repeat != 0)
-                fprintf(f, "/%i", c->repeat / d);
-        if (c->repeat % d != 0)
-                fprintf(f, ".%06i", c->repeat % d);
+        assert(c->start >= 0);
 
-        p = c;
-        for (;;) {
-                n = p->next;
+        fprintf(f, "%0*i", space, c->start / d);
+        if (c->start % d > 0)
+                fprintf(f, ".%06i", c->start % d);
 
-                if (!n || n->repeat || p->repeat)
-                        break;
+        if (c->stop > 0)
+                fprintf(f, "..%0*i", space, c->stop / d);
+        if (c->stop % d > 0)
+                fprintf(f, ".%06i", c->stop % d);
 
-                if (n->value - p->value != d)
-                       break;
-
-                p = n;
-        }
+        if (c->repeat > 0 && !(c->stop > 0 && c->repeat == d))
+                fprintf(f, "/%i", c->repeat / d);
+        if (c->repeat % d > 0)
+                fprintf(f, ".%06i", c->repeat % d);
 
-        if (p->value - c->value >= 2 * d) {
-                fputs("..", f);
-                format_chain(f, space, p, usec);
-        } else if (c->next) {
+        if (c->next) {
                 fputc(',', f);
                 format_chain(f, space, c->next, usec);
         }
 }
 
 int calendar_spec_to_string(const CalendarSpec *c, char **p) {
-        CalendarComponent *cc;
         char *buf = NULL;
         size_t sz = 0;
         FILE *f;
@@ -327,12 +347,7 @@ int calendar_spec_to_string(const CalendarSpec *c, char **p) {
         fputc(':', f);
         format_chain(f, 2, c->minute, false);
         fputc(':', f);
-
-        cc = c->microsecond;
-        if (cc && !cc->value && cc->repeat == USEC_PER_SEC && !cc->next)
-                fputc('*', f);
-        else
-                format_chain(f, 2, c->microsecond, true);
+        format_chain(f, 2, c->microsecond, true);
 
         if (c->utc)
                 fputs(" UTC", f);
@@ -462,7 +477,7 @@ static int parse_weekdays(const char **p, CalendarSpec *c) {
                         *p += 1;
                 }
 
-                /* Allow  a trailing comma but not an open range */
+                /* Allow a trailing comma but not an open range */
                 if (**p == 0 || **p == ' ') {
                         *p += strspn(*p, " ");
                         return l < 0 ? 0 : -EINVAL;
@@ -530,7 +545,8 @@ static int const_chain(int value, CalendarComponent **c) {
         if (!cc)
                 return -ENOMEM;
 
-        cc->value = value;
+        cc->start = value;
+        cc->stop = -1;
         cc->repeat = 0;
         cc->next = *c;
 
@@ -540,7 +556,7 @@ static int const_chain(int value, CalendarComponent **c) {
 }
 
 static int prepend_component(const char **p, bool usec, CalendarComponent **c) {
-        unsigned long i, value, range_end, range_inc, repeat = 0;
+        unsigned long start, stop = -1, repeat = 0;
         CalendarComponent *cc;
         int r;
         const char *e;
@@ -550,10 +566,19 @@ static int prepend_component(const char **p, bool usec, CalendarComponent **c) {
 
         e = *p;
 
-        r = parse_component_decimal(&e, usec, &value);
+        r = parse_component_decimal(&e, usec, &start);
         if (r < 0)
                 return r;
 
+        if (e[0] == '.' && e[1] == '.') {
+                e += 2;
+                r = parse_component_decimal(&e, usec, &stop);
+                if (r < 0)
+                        return r;
+
+                repeat = usec ? USEC_PER_SEC : 1;
+        }
+
         if (*e == '/') {
                 e++;
                 r = parse_component_decimal(&e, usec, &repeat);
@@ -562,30 +587,6 @@ static int prepend_component(const char **p, bool usec, CalendarComponent **c) {
 
                 if (repeat == 0)
                         return -ERANGE;
-        } else if (e[0] == '.' && e[1] == '.') {
-                e += 2;
-                r = parse_component_decimal(&e, usec, &range_end);
-                if (r < 0)
-                        return r;
-
-                if (value >= range_end)
-                        return -EINVAL;
-
-                range_inc = usec ? USEC_PER_SEC : 1;
-
-                /* Don't allow impossibly large ranges... */
-                if (range_end - value >= MAX_RANGE_LEN * range_inc)
-                        return -EINVAL;
-
-                /* ...or ranges with only a single element */
-                if (range_end - value < range_inc)
-                        return -EINVAL;
-
-                for (i = value; i <= range_end; i += range_inc) {
-                        r = const_chain(i, c);
-                        if (r < 0)
-                                return r;
-                }
         }
 
         if (*e != 0 && *e != ' ' && *e != ',' && *e != '-' && *e != '~' && *e != ':')
@@ -595,7 +596,8 @@ static int prepend_component(const char **p, bool usec, CalendarComponent **c) {
         if (!cc)
                 return -ENOMEM;
 
-        cc->value = value;
+        cc->start = start;
+        cc->stop = stop;
         cc->repeat = repeat;
         cc->next = *c;
 
@@ -1014,11 +1016,24 @@ fail:
         return r;
 }
 
+static int find_end_of_month(struct tm *tm, bool utc, int day)
+{
+        struct tm t = *tm;
+
+        t.tm_mon++;
+        t.tm_mday = 1 - day;
+
+        if (mktime_or_timegm(&t, utc) == (time_t) -1 ||
+            t.tm_mon != tm->tm_mon)
+                return -1;
+
+        return t.tm_mday;
+}
+
 static int find_matching_component(const CalendarSpec *spec, const CalendarComponent *c,
                                    struct tm *tm, int *val) {
-        const CalendarComponent *n, *p = c;
-        struct tm t;
-        int v, d = -1;
+        const CalendarComponent *p = c;
+        int start, stop, d = -1;
         bool d_set = false;
         int r;
 
@@ -1028,40 +1043,36 @@ static int find_matching_component(const CalendarSpec *spec, const CalendarCompo
                 return 0;
 
         while (c) {
-                n = c->next;
+                start = c->start;
+                stop = c->stop;
 
                 if (spec->end_of_month && p == spec->day) {
-                        t = *tm;
-                        t.tm_mon++;
-                        t.tm_mday = 1 - c->value;
-
-                        if (mktime_or_timegm(&t, spec->utc) == (time_t) -1 ||
-                            t.tm_mon != tm->tm_mon)
-                                v = -1;
-                        else
-                                v = t.tm_mday;
-                } else
-                        v = c->value;
+                        start = find_end_of_month(tm, spec->utc, start);
+                        stop = find_end_of_month(tm, spec->utc, stop);
 
-                if (v >= *val) {
+                        if (stop > 0)
+                                SWAP_TWO(start, stop);
+                }
+
+                if (start >= *val) {
 
-                        if (!d_set || v < d) {
-                                d = v;
+                        if (!d_set || start < d) {
+                                d = start;
                                 d_set = true;
                         }
 
                 } else if (c->repeat > 0) {
                         int k;
 
-                        k = v + c->repeat * ((*val - v + c->repeat -1) / c->repeat);
+                        k = start + c->repeat * ((*val - start + c->repeat - 1) / c->repeat);
 
-                        if (!d_set || k < d) {
+                        if ((!d_set || k < d) && (stop < 0 || k <= stop)) {
                                 d = k;
                                 d_set = true;
                         }
                 }
 
-                c = n;
+                c = c->next;
         }
 
         if (!d_set)
diff --git a/src/basic/calendarspec.h b/src/basic/calendarspec.h
index 78af27403c..3d8798de0b 100644
--- a/src/basic/calendarspec.h
+++ b/src/basic/calendarspec.h
@@ -28,7 +28,8 @@
 #include "util.h"
 
 typedef struct CalendarComponent {
-        int value;
+        int start;
+        int stop;
         int repeat;
 
         struct CalendarComponent *next;
diff --git a/src/test/test-calendarspec.c b/src/test/test-calendarspec.c
index b8320b081b..5fd749a6a8 100644
--- a/src/test/test-calendarspec.c
+++ b/src/test/test-calendarspec.c
@@ -149,8 +149,8 @@ int main(int argc, char* argv[]) {
         test_one("*-*-7 0:0:0", "*-*-07 00:00:00");
         test_one("10-15", "*-10-15 00:00:00");
         test_one("monday *-12-* 17:00", "Mon *-12-* 17:00:00");
-        test_one("Mon,Fri *-*-3,1,2 *:30:45", "Mon,Fri *-*-01..03 *:30:45");
-        test_one("12,14,13,12:20,10,30", "*-*-* 12..14:10,20,30:00");
+        test_one("Mon,Fri *-*-3,1,2 *:30:45", "Mon,Fri *-*-01,02,03 *:30:45");
+        test_one("12,14,13,12:20,10,30", "*-*-* 12,13,14:10,20,30:00");
         test_one("mon,fri *-1/2-1,3 *:30:45", "Mon,Fri *-01/2-01,03 *:30:45");
         test_one("03-05 08:05:40", "*-03-05 08:05:40");
         test_one("08:05:40", "*-*-* 08:05:40");
@@ -172,13 +172,12 @@ int main(int argc, char* argv[]) {
         test_one("2015-10-25 01:00:00 uTc", "2015-10-25 01:00:00 UTC");
         test_one("2016-03-27 03:17:00.4200005", "2016-03-27 03:17:00.420001");
         test_one("2016-03-27 03:17:00/0.42", "2016-03-27 03:17:00/0.420000");
-        test_one("2016-03-27 03:17:00/0.42", "2016-03-27 03:17:00/0.420000");
         test_one("9..11,13:00,30", "*-*-* 09..11,13:00,30:00");
         test_one("1..3-1..3 1..3:1..3", "*-01..03-01..03 01..03:01..03:00");
-        test_one("00:00:1.125..2.125", "*-*-* 00:00:01.125000,02.125000");
+        test_one("00:00:1.125..2.125", "*-*-* 00:00:01.125000..02.125000");
         test_one("00:00:1.0..3.8", "*-*-* 00:00:01..03");
         test_one("00:00:01..03", "*-*-* 00:00:01..03");
-        test_one("00:00:01/2,02..03", "*-*-* 00:00:01/2,02,03");
+        test_one("00:00:01/2,02..03", "*-*-* 00:00:01/2,02..03");
         test_one("*-*~1 Utc", "*-*~01 00:00:00 UTC");
         test_one("*-*~05,3 ", "*-*~03,05 00:00:00");
         test_one("*-*~* 00:00:00", "*-*-* 00:00:00");
@@ -189,6 +188,10 @@ int main(int argc, char* argv[]) {
         test_one("*:*", "*-*-* *:*:00");
         test_one("12:*", "*-*-* 12:*:00");
         test_one("*:30", "*-*-* *:30:00");
+        test_one("93..00-*-*", "1993..2000-*-* 00:00:00");
+        test_one("00..07-*-*", "2000..2007-*-* 00:00:00");
+        test_one("*:20..39/5", "*-*-* *:20..35/5:00");
+        test_one("00:00:20..40/1", "*-*-* 00:00:20..40");
 
         test_next("2016-03-27 03:17:00", "", 12345, 1459048620000000);
         test_next("2016-03-27 03:17:00", "CET", 12345, 1459041420000000);
@@ -207,6 +210,9 @@ int main(int argc, char* argv[]) {
         test_next("2016-02~01 UTC", "", 12345, 1456704000000000);
         test_next("Mon 2017-05~01..07 UTC", "", 12345, 1496016000000000);
         test_next("Mon 2017-05~07/1 UTC", "", 12345, 1496016000000000);
+        test_next("2017-08-06 9,11,13,15,17:00 UTC", "", 1502029800000000, 1502031600000000);
+        test_next("2017-08-06 9..17/2:00 UTC", "", 1502029800000000, 1502031600000000);
+        test_next("2016-12-* 3..21/6:00 UTC", "", 1482613200000001, 1482634800000000);
 
         assert_se(calendar_spec_from_string("test", &c) < 0);
         assert_se(calendar_spec_from_string(" utc", &c) < 0);
@@ -225,6 +231,13 @@ int main(int argc, char* argv[]) {
         assert_se(calendar_spec_from_string("-00:+00/-5", &c) < 0);
         assert_se(calendar_spec_from_string("00:+00/-5", &c) < 0);
         assert_se(calendar_spec_from_string("2016- 11- 24 12: 30: 00", &c) < 0);
+        assert_se(calendar_spec_from_string("*~29", &c) < 0);
+        assert_se(calendar_spec_from_string("*~16..31", &c) < 0);
+        assert_se(calendar_spec_from_string("12..1/2-*", &c) < 0);
+        assert_se(calendar_spec_from_string("*:05..05", &c) < 0);
+        assert_se(calendar_spec_from_string("*:05..10/6", &c) < 0);
+        assert_se(calendar_spec_from_string("20/4:00", &c) < 0);
+        assert_se(calendar_spec_from_string("00:00/60", &c) < 0);
 
         test_timestamp();
         test_hourly_bug_4031();