src/basic/calendarspec.c

   1 /***
   2   This file is part of systemd.
   3
   4   Copyright 2012 Lennart Poettering
   5
   6   systemd is free software; you can redistribute it and/or modify it
   7   under the terms of the GNU Lesser General Public License as published by
   8   the Free Software Foundation; either version 2.1 of the License, or
   9   (at your option) any later version.
  10
  11   systemd is distributed in the hope that it will be useful, but
  12   WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14   Lesser General Public License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public License
  17   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  18 ***/
  19
  20 #include <alloca.h>
  21 #include <ctype.h>
  22 #include <errno.h>
  23 #include <stddef.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <time.h>
  28
  29 #include "alloc-util.h"
  30 #include "calendarspec.h"
  31 #include "fileio.h"
  32 #include "macro.h"
  33 #include "parse-util.h"
  34 #include "string-util.h"
  35
  36 /* Longest valid date/time range is 1970..2199 */
  37 #define MAX_RANGE_LEN   230
  38 #define MIN_YEAR       1970
  39 #define MAX_YEAR       2199
  40 #define BITS_WEEKDAYS   127
  41
  42 static void free_chain(CalendarComponent *c) {
  43         CalendarComponent *n;
  44
  45         while (c) {
  46                 n = c->next;
  47                 free(c);
  48                 c = n;
  49         }
  50 }
  51
  52 void calendar_spec_free(CalendarSpec *c) {
  53
  54         if (!c)
  55                 return;
  56
  57         free_chain(c->year);
  58         free_chain(c->month);
  59         free_chain(c->day);
  60         free_chain(c->hour);
  61         free_chain(c->minute);
  62         free_chain(c->microsecond);
  63
  64         free(c);
  65 }
  66
  67 static int component_compare(const void *_a, const void *_b) {
  68         CalendarComponent * const *a = _a, * const *b = _b;
  69
  70         if ((*a)->value < (*b)->value)
  71                 return -1;
  72         if ((*a)->value > (*b)->value)
  73                 return 1;
  74
  75         if ((*a)->repeat < (*b)->repeat)
  76                 return -1;
  77         if ((*a)->repeat > (*b)->repeat)
  78                 return 1;
  79
  80         return 0;
  81 }
  82
  83 static void sort_chain(CalendarComponent **c) {
  84         unsigned n = 0, k;
  85         CalendarComponent **b, *i, **j, *next;
  86
  87         assert(c);
  88
  89         for (i = *c; i; i = i->next)
  90                 n++;
  91
  92         if (n <= 1)
  93                 return;
  94
  95         j = b = alloca(sizeof(CalendarComponent*) * n);
  96         for (i = *c; i; i = i->next)
  97                 *(j++) = i;
  98
  99         qsort(b, n, sizeof(CalendarComponent*), component_compare);
 100
 101         b[n-1]->next = NULL;
 102         next = b[n-1];
 103
 104         /* Drop non-unique entries */
 105         for (k = n-1; k > 0; k--) {
 106                 if (b[k-1]->value == next->value &&
 107                     b[k-1]->repeat == next->repeat) {
 108                         free(b[k-1]);
 109                         continue;
 110                 }
 111
 112                 b[k-1]->next = next;
 113                 next = b[k-1];
 114         }
 115
 116         *c = next;
 117 }
 118
 119 static void fix_year(CalendarComponent *c) {
 120         /* Turns 12 → 2012, 89 → 1989 */
 121
 122         while (c) {
 123                 CalendarComponent *n = c->next;
 124
 125                 if (c->value >= 0 && c->value < 70)
 126                         c->value += 2000;
 127
 128                 if (c->value >= 70 && c->value < 100)
 129                         c->value += 1900;
 130
 131                 c = n;
 132         }
 133 }
 134
 135 int calendar_spec_normalize(CalendarSpec *c) {
 136         assert(c);
 137
 138         if (c->weekdays_bits <= 0 || c->weekdays_bits >= BITS_WEEKDAYS)
 139                 c->weekdays_bits = -1;
 140
 141         if (c->end_of_month && !c->day)
 142                 c->end_of_month = false;
 143
 144         fix_year(c->year);
 145
 146         sort_chain(&c->year);
 147         sort_chain(&c->month);
 148         sort_chain(&c->day);
 149         sort_chain(&c->hour);
 150         sort_chain(&c->minute);
 151         sort_chain(&c->microsecond);
 152
 153         return 0;
 154 }
 155
 156 _pure_ static bool chain_valid(CalendarComponent *c, int from, int to, bool eom) {
 157         if (!c)
 158                 return true;
 159
 160         if (c->value < from || c->value > to)
 161                 return false;
 162
 163         /*
 164          * c->repeat must be short enough so at least one repetition may
 165          * occur before the end of the interval.  For dates scheduled
 166          * relative to the end of the month (eom), c->value corresponds
 167          * to the Nth last day of the month.
 168          */
 169         if (eom && c->value - c->repeat < from)
 170                 return false;
 171
 172         if (!eom && c->value + c->repeat > to)
 173                 return false;
 174
 175         if (c->next)
 176                 return chain_valid(c->next, from, to, eom);
 177
 178         return true;
 179 }
 180
 181 _pure_ bool calendar_spec_valid(CalendarSpec *c) {
 182         assert(c);
 183
 184         if (c->weekdays_bits > BITS_WEEKDAYS)
 185                 return false;
 186
 187         if (!chain_valid(c->year, MIN_YEAR, MAX_YEAR, false))
 188                 return false;
 189
 190         if (!chain_valid(c->month, 1, 12, false))
 191                 return false;
 192
 193         if (!chain_valid(c->day, 1, 31, c->end_of_month))
 194                 return false;
 195
 196         if (!chain_valid(c->hour, 0, 23, false))
 197                 return false;
 198
 199         if (!chain_valid(c->minute, 0, 59, false))
 200                 return false;
 201
 202         if (!chain_valid(c->microsecond, 0, 60*USEC_PER_SEC-1, false))
 203                 return false;
 204
 205         return true;
 206 }
 207
 208 static void format_weekdays(FILE *f, const CalendarSpec *c) {
 209         static const char *const days[] = {
 210                 "Mon",
 211                 "Tue",
 212                 "Wed",
 213                 "Thu",
 214                 "Fri",
 215                 "Sat",
 216                 "Sun"
 217         };
 218
 219         int l, x;
 220         bool need_comma = false;
 221
 222         assert(f);
 223         assert(c);
 224         assert(c->weekdays_bits > 0 && c->weekdays_bits <= BITS_WEEKDAYS);
 225
 226         for (x = 0, l = -1; x < (int) ELEMENTSOF(days); x++) {
 227
 228                 if (c->weekdays_bits & (1 << x)) {
 229
 230                         if (l < 0) {
 231                                 if (need_comma)
 232                                         fputc(',', f);
 233                                 else
 234                                         need_comma = true;
 235
 236                                 fputs(days[x], f);
 237                                 l = x;
 238                         }
 239
 240                 } else if (l >= 0) {
 241
 242                         if (x > l + 1) {
 243                                 fputs(x > l + 2 ? ".." : ",", f);
 244                                 fputs(days[x-1], f);
 245                         }
 246
 247                         l = -1;
 248                 }
 249         }
 250
 251         if (l >= 0 && x > l + 1) {
 252                 fputs(x > l + 2 ? ".." : ",", f);
 253                 fputs(days[x-1], f);
 254         }
 255 }
 256
 257 static void format_chain(FILE *f, int space, const CalendarComponent *c, bool usec) {
 258         assert(f);
 259
 260         if (!c) {
 261                 fputc('*', f);
 262                 return;
 263         }
 264
 265         assert(c->value >= 0);
 266         if (!usec)
 267                 fprintf(f, "%0*i", space, c->value);
 268         else if (c->value % USEC_PER_SEC == 0)
 269                 fprintf(f, "%0*i", space, (int) (c->value / USEC_PER_SEC));
 270         else
 271                 fprintf(f, "%0*i.%06i", space, (int) (c->value / USEC_PER_SEC), (int) (c->value % USEC_PER_SEC));
 272
 273         if (c->repeat > 0) {
 274                 if (!usec)
 275                         fprintf(f, "/%i", c->repeat);
 276                 else if (c->repeat % USEC_PER_SEC == 0)
 277                         fprintf(f, "/%i", (int) (c->repeat / USEC_PER_SEC));
 278                 else
 279                         fprintf(f, "/%i.%06i", (int) (c->repeat / USEC_PER_SEC), (int) (c->repeat % USEC_PER_SEC));
 280         }
 281
 282         if (c->next) {
 283                 fputc(',', f);
 284                 format_chain(f, space, c->next, usec);
 285         }
 286 }
 287
 288 int calendar_spec_to_string(const CalendarSpec *c, char **p) {
 289         CalendarComponent *cc;
 290         char *buf = NULL;
 291         size_t sz = 0;
 292         FILE *f;
 293         int r;
 294
 295         assert(c);
 296         assert(p);
 297
 298         f = open_memstream(&buf, &sz);
 299         if (!f)
 300                 return -ENOMEM;
 301
 302         if (c->weekdays_bits > 0 && c->weekdays_bits <= BITS_WEEKDAYS) {
 303                 format_weekdays(f, c);
 304                 fputc(' ', f);
 305         }
 306
 307         format_chain(f, 4, c->year, false);
 308         fputc('-', f);
 309         format_chain(f, 2, c->month, false);
 310         fputc(c->end_of_month ? '~' : '-', f);
 311         format_chain(f, 2, c->day, false);
 312         fputc(' ', f);
 313         format_chain(f, 2, c->hour, false);
 314         fputc(':', f);
 315         format_chain(f, 2, c->minute, false);
 316         fputc(':', f);
 317
 318         cc = c->microsecond;
 319         if (cc && !cc->value && cc->repeat == USEC_PER_SEC && !cc->next)
 320                 fputc('*', f);
 321         else
 322                 format_chain(f, 2, c->microsecond, true);
 323
 324         if (c->utc)
 325                 fputs(" UTC", f);
 326         else if (IN_SET(c->dst, 0, 1)) {
 327
 328                 /* If daylight saving is explicitly on or off, let's show the used timezone. */
 329
 330                 tzset();
 331
 332                 if (!isempty(tzname[c->dst])) {
 333                         fputc(' ', f);
 334                         fputs(tzname[c->dst], f);
 335                 }
 336         }
 337
 338         r = fflush_and_check(f);
 339         if (r < 0) {
 340                 free(buf);
 341                 fclose(f);
 342                 return r;
 343         }
 344
 345         fclose(f);
 346
 347         *p = buf;
 348         return 0;
 349 }
 350
 351 static int parse_weekdays(const char **p, CalendarSpec *c) {
 352         static const struct {
 353                 const char *name;
 354                 const int nr;
 355         } day_nr[] = {
 356                 { "Monday",    0 },
 357                 { "Mon",       0 },
 358                 { "Tuesday",   1 },
 359                 { "Tue",       1 },
 360                 { "Wednesday", 2 },
 361                 { "Wed",       2 },
 362                 { "Thursday",  3 },
 363                 { "Thu",       3 },
 364                 { "Friday",    4 },
 365                 { "Fri",       4 },
 366                 { "Saturday",  5 },
 367                 { "Sat",       5 },
 368                 { "Sunday",    6 },
 369                 { "Sun",       6 }
 370         };
 371
 372         int l = -1;
 373         bool first = true;
 374
 375         assert(p);
 376         assert(*p);
 377         assert(c);
 378
 379         for (;;) {
 380                 unsigned i;
 381
 382                 for (i = 0; i < ELEMENTSOF(day_nr); i++) {
 383                         size_t skip;
 384
 385                         if (!startswith_no_case(*p, day_nr[i].name))
 386                                 continue;
 387
 388                         skip = strlen(day_nr[i].name);
 389
 390                         if ((*p)[skip] != '-' &&
 391                             (*p)[skip] != '.' &&
 392                             (*p)[skip] != ',' &&
 393                             (*p)[skip] != ' ' &&
 394                             (*p)[skip] != 0)
 395                                 return -EINVAL;
 396
 397                         c->weekdays_bits |= 1 << day_nr[i].nr;
 398
 399                         if (l >= 0) {
 400                                 int j;
 401
 402                                 if (l > day_nr[i].nr)
 403                                         return -EINVAL;
 404
 405                                 for (j = l + 1; j < day_nr[i].nr; j++)
 406                                         c->weekdays_bits |= 1 << j;
 407                         }
 408
 409                         *p += skip;
 410                         break;
 411                 }
 412
 413                 /* Couldn't find this prefix, so let's assume the
 414                    weekday was not specified and let's continue with
 415                    the date */
 416                 if (i >= ELEMENTSOF(day_nr))
 417                         return first ? 0 : -EINVAL;
 418
 419                 /* We reached the end of the string */
 420                 if (**p == 0)
 421                         return 0;
 422
 423                 /* We reached the end of the weekday spec part */
 424                 if (**p == ' ') {
 425                         *p += strspn(*p, " ");
 426                         return 0;
 427                 }
 428
 429                 if (**p == '.') {
 430                         if (l >= 0)
 431                                 return -EINVAL;
 432
 433                         if ((*p)[1] != '.')
 434                                 return -EINVAL;
 435
 436                         l = day_nr[i].nr;
 437                         *p += 2;
 438
 439                 /* Support ranges with "-" for backwards compatibility */
 440                 } else if (**p == '-') {
 441                         if (l >= 0)
 442                                 return -EINVAL;
 443
 444                         l = day_nr[i].nr;
 445                         *p += 1;
 446
 447                 } else if (**p == ',') {
 448                         l = -1;
 449                         *p += 1;
 450                 }
 451
 452                 /* Allow  a trailing comma but not an open range */
 453                 if (**p == 0 || **p == ' ') {
 454                         *p += strspn(*p, " ");
 455                         return l < 0 ? 0 : -EINVAL;
 456                 }
 457
 458                 first = false;
 459         }
 460 }
 461
 462 static int parse_component_decimal(const char **p, bool usec, unsigned long *res) {
 463         unsigned long value;
 464         const char *e = NULL;
 465         char *ee = NULL;
 466         int r;
 467
 468         if (!isdigit(**p))
 469                 return -EINVAL;
 470
 471         errno = 0;
 472         value = strtoul(*p, &ee, 10);
 473         if (errno > 0)
 474                 return -errno;
 475         if (ee == *p)
 476                 return -EINVAL;
 477         if ((unsigned long) (int) value != value)
 478                 return -ERANGE;
 479         e = ee;
 480
 481         if (usec) {
 482                 if (value * USEC_PER_SEC / USEC_PER_SEC != value)
 483                         return -ERANGE;
 484
 485                 value *= USEC_PER_SEC;
 486                 if (*e == '.') {
 487                         unsigned add;
 488
 489                         /* This is the start of a range, not a fractional part */
 490                         if (e[1] == '.')
 491                                 goto finish;
 492
 493                         e++;
 494                         r = parse_fractional_part_u(&e, 6, &add);
 495                         if (r < 0)
 496                                 return r;
 497
 498                         if (add + value < value)
 499                                 return -ERANGE;
 500                         value += add;
 501                 }
 502         }
 503
 504 finish:
 505         *p = e;
 506         *res = value;
 507
 508         return 0;
 509 }
 510
 511 static int const_chain(int value, CalendarComponent **c) {
 512         CalendarComponent *cc = NULL;
 513
 514         assert(c);
 515
 516         cc = new0(CalendarComponent, 1);
 517         if (!cc)
 518                 return -ENOMEM;
 519
 520         cc->value = value;
 521         cc->repeat = 0;
 522         cc->next = *c;
 523
 524         *c = cc;
 525
 526         return 0;
 527 }
 528
 529 static int prepend_component(const char **p, bool usec, CalendarComponent **c) {
 530         unsigned long i, value, range_end, range_inc, repeat = 0;
 531         CalendarComponent *cc;
 532         int r;
 533         const char *e;
 534
 535         assert(p);
 536         assert(c);
 537
 538         e = *p;
 539
 540         r = parse_component_decimal(&e, usec, &value);
 541         if (r < 0)
 542                 return r;
 543
 544         if (*e == '/') {
 545                 e++;
 546                 r = parse_component_decimal(&e, usec, &repeat);
 547                 if (r < 0)
 548                         return r;
 549
 550                 if (repeat == 0)
 551                         return -ERANGE;
 552         } else if (e[0] == '.' && e[1] == '.') {
 553                 e += 2;
 554                 r = parse_component_decimal(&e, usec, &range_end);
 555                 if (r < 0)
 556                         return r;
 557
 558                 if (value >= range_end)
 559                         return -EINVAL;
 560
 561                 range_inc = usec ? USEC_PER_SEC : 1;
 562
 563                 /* Don't allow impossibly large ranges... */
 564                 if (range_end - value >= MAX_RANGE_LEN * range_inc)
 565                         return -EINVAL;
 566
 567                 /* ...or ranges with only a single element */
 568                 if (range_end - value < range_inc)
 569                         return -EINVAL;
 570
 571                 for (i = value; i <= range_end; i += range_inc) {
 572                         r = const_chain(i, c);
 573                         if (r < 0)
 574                                 return r;
 575                 }
 576         }
 577
 578         if (*e != 0 && *e != ' ' && *e != ',' && *e != '-' && *e != '~' && *e != ':')
 579                 return -EINVAL;
 580
 581         cc = new0(CalendarComponent, 1);
 582         if (!cc)
 583                 return -ENOMEM;
 584
 585         cc->value = value;
 586         cc->repeat = repeat;
 587         cc->next = *c;
 588
 589         *p = e;
 590         *c = cc;
 591
 592         if (*e ==',') {
 593                 *p += 1;
 594                 return prepend_component(p, usec, c);
 595         }
 596
 597         return 0;
 598 }
 599
 600 static int parse_chain(const char **p, bool usec, CalendarComponent **c) {
 601         const char *t;
 602         CalendarComponent *cc = NULL;
 603         int r;
 604
 605         assert(p);
 606         assert(c);
 607
 608         t = *p;
 609
 610         if (t[0] == '*') {
 611                 if (usec) {
 612                         r = const_chain(0, c);
 613                         if (r < 0)
 614                                 return r;
 615                         (*c)->repeat = USEC_PER_SEC;
 616                 } else
 617                         *c = NULL;
 618
 619                 *p = t + 1;
 620                 return 0;
 621         }
 622
 623         r = prepend_component(&t, usec, &cc);
 624         if (r < 0) {
 625                 free_chain(cc);
 626                 return r;
 627         }
 628
 629         *p = t;
 630         *c = cc;
 631         return 0;
 632 }
 633
 634 static int parse_date(const char **p, CalendarSpec *c) {
 635         const char *t;
 636         int r;
 637         CalendarComponent *first, *second, *third;
 638
 639         assert(p);
 640         assert(*p);
 641         assert(c);
 642
 643         t = *p;
 644
 645         if (*t == 0)
 646                 return 0;
 647
 648         r = parse_chain(&t, false, &first);
 649         if (r < 0)
 650                 return r;
 651
 652         /* Already the end? A ':' as separator? In that case this was a time, not a date */
 653         if (*t == 0 || *t == ':') {
 654                 free_chain(first);
 655                 return 0;
 656         }
 657
 658         if (*t == '~')
 659                 c->end_of_month = true;
 660         else if (*t != '-') {
 661                 free_chain(first);
 662                 return -EINVAL;
 663         }
 664
 665         t++;
 666         r = parse_chain(&t, false, &second);
 667         if (r < 0) {
 668                 free_chain(first);
 669                 return r;
 670         }
 671
 672         /* Got two parts, hence it's month and day */
 673         if (*t == ' ' || *t == 0) {
 674                 *p = t + strspn(t, " ");
 675                 c->month = first;
 676                 c->day = second;
 677                 return 0;
 678         } else if (c->end_of_month)
 679                 return -EINVAL;
 680
 681         if (*t == '~')
 682                 c->end_of_month = true;
 683         else if (*t != '-') {
 684                 free_chain(first);
 685                 free_chain(second);
 686                 return -EINVAL;
 687         }
 688
 689         t++;
 690         r = parse_chain(&t, false, &third);
 691         if (r < 0) {
 692                 free_chain(first);
 693                 free_chain(second);
 694                 return r;
 695         }
 696
 697         /* Got three parts, hence it is year, month and day */
 698         if (*t == ' ' || *t == 0) {
 699                 *p = t + strspn(t, " ");
 700                 c->year = first;
 701                 c->month = second;
 702                 c->day = third;
 703                 return 0;
 704         }
 705
 706         free_chain(first);
 707         free_chain(second);
 708         free_chain(third);
 709         return -EINVAL;
 710 }
 711
 712 static int parse_calendar_time(const char **p, CalendarSpec *c) {
 713         CalendarComponent *h = NULL, *m = NULL, *s = NULL;
 714         const char *t;
 715         int r;
 716
 717         assert(p);
 718         assert(*p);
 719         assert(c);
 720
 721         t = *p;
 722
 723         /* If no time is specified at all, then this means 00:00:00 */
 724         if (*t == 0)
 725                 goto null_hour;
 726
 727         r = parse_chain(&t, false, &h);
 728         if (r < 0)
 729                 goto fail;
 730
 731         if (*t != ':') {
 732                 r = -EINVAL;
 733                 goto fail;
 734         }
 735
 736         t++;
 737         r = parse_chain(&t, false, &m);
 738         if (r < 0)
 739                 goto fail;
 740
 741         /* Already at the end? Then it's hours and minutes, and seconds are 0 */
 742         if (*t == 0) {
 743                 if (m != NULL)
 744                         goto null_second;
 745
 746                 goto finish;
 747         }
 748
 749         if (*t != ':') {
 750                 r = -EINVAL;
 751                 goto fail;
 752         }
 753
 754         t++;
 755         r = parse_chain(&t, true, &s);
 756         if (r < 0)
 757                 goto fail;
 758
 759         /* At the end? Then it's hours, minutes and seconds */
 760         if (*t == 0)
 761                 goto finish;
 762
 763         r = -EINVAL;
 764         goto fail;
 765
 766 null_hour:
 767         r = const_chain(0, &h);
 768         if (r < 0)
 769                 goto fail;
 770
 771         r = const_chain(0, &m);
 772         if (r < 0)
 773                 goto fail;
 774
 775 null_second:
 776         r = const_chain(0, &s);
 777         if (r < 0)
 778                 goto fail;
 779
 780 finish:
 781         *p = t;
 782         c->hour = h;
 783         c->minute = m;
 784         c->microsecond = s;
 785
 786         return 0;
 787
 788 fail:
 789         free_chain(h);
 790         free_chain(m);
 791         free_chain(s);
 792         return r;
 793 }
 794
 795 int calendar_spec_from_string(const char *p, CalendarSpec **spec) {
 796         const char *utc;
 797         CalendarSpec *c;
 798         int r;
 799
 800         assert(p);
 801         assert(spec);
 802
 803         c = new0(CalendarSpec, 1);
 804         if (!c)
 805                 return -ENOMEM;
 806         c->dst = -1;
 807
 808         utc = endswith_no_case(p, " UTC");
 809         if (utc) {
 810                 c->utc = true;
 811                 p = strndupa(p, utc - p);
 812         } else {
 813                 const char *e = NULL;
 814                 int j;
 815
 816                 tzset();
 817
 818                 /* Check if the local timezone was specified? */
 819                 for (j = 0; j <= 1; j++) {
 820                         if (isempty(tzname[j]))
 821                                 continue;
 822
 823                         e = endswith_no_case(p, tzname[j]);
 824                         if(!e)
 825                                 continue;
 826                         if (e == p)
 827                                 continue;
 828                         if (e[-1] != ' ')
 829                                 continue;
 830
 831                         break;
 832                 }
 833
 834                 /* Found one of the two timezones specified? */
 835                 if (IN_SET(j, 0, 1)) {
 836                         p = strndupa(p, e - p - 1);
 837                         c->dst = j;
 838                 }
 839         }
 840
 841         if (isempty(p)) {
 842                 r = -EINVAL;
 843                 goto fail;
 844         }
 845
 846         if (strcaseeq(p, "minutely")) {
 847                 r = const_chain(0, &c->microsecond);
 848                 if (r < 0)
 849                         goto fail;
 850
 851         } else if (strcaseeq(p, "hourly")) {
 852                 r = const_chain(0, &c->minute);
 853                 if (r < 0)
 854                         goto fail;
 855                 r = const_chain(0, &c->microsecond);
 856                 if (r < 0)
 857                         goto fail;
 858
 859         } else if (strcaseeq(p, "daily")) {
 860                 r = const_chain(0, &c->hour);
 861                 if (r < 0)
 862                         goto fail;
 863                 r = const_chain(0, &c->minute);
 864                 if (r < 0)
 865                         goto fail;
 866                 r = const_chain(0, &c->microsecond);
 867                 if (r < 0)
 868                         goto fail;
 869
 870         } else if (strcaseeq(p, "monthly")) {
 871                 r = const_chain(1, &c->day);
 872                 if (r < 0)
 873                         goto fail;
 874                 r = const_chain(0, &c->hour);
 875                 if (r < 0)
 876                         goto fail;
 877                 r = const_chain(0, &c->minute);
 878                 if (r < 0)
 879                         goto fail;
 880                 r = const_chain(0, &c->microsecond);
 881                 if (r < 0)
 882                         goto fail;
 883
 884         } else if (strcaseeq(p, "annually") ||
 885                    strcaseeq(p, "yearly") ||
 886                    strcaseeq(p, "anually") /* backwards compatibility */ ) {
 887
 888                 r = const_chain(1, &c->month);
 889                 if (r < 0)
 890                         goto fail;
 891                 r = const_chain(1, &c->day);
 892                 if (r < 0)
 893                         goto fail;
 894                 r = const_chain(0, &c->hour);
 895                 if (r < 0)
 896                         goto fail;
 897                 r = const_chain(0, &c->minute);
 898                 if (r < 0)
 899                         goto fail;
 900                 r = const_chain(0, &c->microsecond);
 901                 if (r < 0)
 902                         goto fail;
 903
 904         } else if (strcaseeq(p, "weekly")) {
 905
 906                 c->weekdays_bits = 1;
 907
 908                 r = const_chain(0, &c->hour);
 909                 if (r < 0)
 910                         goto fail;
 911                 r = const_chain(0, &c->minute);
 912                 if (r < 0)
 913                         goto fail;
 914                 r = const_chain(0, &c->microsecond);
 915                 if (r < 0)
 916                         goto fail;
 917
 918         } else if (strcaseeq(p, "quarterly")) {
 919
 920                 r = const_chain(1, &c->month);
 921                 if (r < 0)
 922                         goto fail;
 923                 r = const_chain(4, &c->month);
 924                 if (r < 0)
 925                         goto fail;
 926                 r = const_chain(7, &c->month);
 927                 if (r < 0)
 928                         goto fail;
 929                 r = const_chain(10, &c->month);
 930                 if (r < 0)
 931                         goto fail;
 932                 r = const_chain(1, &c->day);
 933                 if (r < 0)
 934                         goto fail;
 935                 r = const_chain(0, &c->hour);
 936                 if (r < 0)
 937                         goto fail;
 938                 r = const_chain(0, &c->minute);
 939                 if (r < 0)
 940                         goto fail;
 941                 r = const_chain(0, &c->microsecond);
 942                 if (r < 0)
 943                         goto fail;
 944
 945         } else if (strcaseeq(p, "biannually") ||
 946                    strcaseeq(p, "bi-annually") ||
 947                    strcaseeq(p, "semiannually") ||
 948                    strcaseeq(p, "semi-annually")) {
 949
 950                 r = const_chain(1, &c->month);
 951                 if (r < 0)
 952                         goto fail;
 953                 r = const_chain(7, &c->month);
 954                 if (r < 0)
 955                         goto fail;
 956                 r = const_chain(1, &c->day);
 957                 if (r < 0)
 958                         goto fail;
 959                 r = const_chain(0, &c->hour);
 960                 if (r < 0)
 961                         goto fail;
 962                 r = const_chain(0, &c->minute);
 963                 if (r < 0)
 964                         goto fail;
 965                 r = const_chain(0, &c->microsecond);
 966                 if (r < 0)
 967                         goto fail;
 968
 969         } else {
 970                 r = parse_weekdays(&p, c);
 971                 if (r < 0)
 972                         goto fail;
 973
 974                 r = parse_date(&p, c);
 975                 if (r < 0)
 976                         goto fail;
 977
 978                 r = parse_calendar_time(&p, c);
 979                 if (r < 0)
 980                         goto fail;
 981
 982                 if (*p != 0) {
 983                         r = -EINVAL;
 984                         goto fail;
 985                 }
 986         }
 987
 988         r = calendar_spec_normalize(c);
 989         if (r < 0)
 990                 goto fail;
 991
 992         if (!calendar_spec_valid(c)) {
 993                 r = -EINVAL;
 994                 goto fail;
 995         }
 996
 997         *spec = c;
 998         return 0;
 999
1000 fail:
1001         calendar_spec_free(c);
1002         return r;
1003 }
1004
1005 static int find_matching_component(const CalendarSpec *spec, const CalendarComponent *c,
1006                                    struct tm *tm, int *val) {
1007         const CalendarComponent *n, *p = c;
1008         struct tm t;
1009         int v, d = -1;
1010         bool d_set = false;
1011         int r;
1012
1013         assert(val);
1014
1015         if (!c)
1016                 return 0;
1017
1018         while (c) {
1019                 n = c->next;
1020
1021                 if (spec->end_of_month && p == spec->day) {
1022                         t = *tm;
1023                         t.tm_mon++;
1024                         t.tm_mday = 1 - c->value;
1025
1026                         if (mktime_or_timegm(&t, spec->utc) == (time_t) -1 ||
1027                             t.tm_mon != tm->tm_mon)
1028                                 v = -1;
1029                         else
1030                                 v = t.tm_mday;
1031                 } else
1032                         v = c->value;
1033
1034                 if (v >= *val) {
1035
1036                         if (!d_set || v < d) {
1037                                 d = v;
1038                                 d_set = true;
1039                         }
1040
1041                 } else if (c->repeat > 0) {
1042                         int k;
1043
1044                         k = v + c->repeat * ((*val - v + c->repeat -1) / c->repeat);
1045
1046                         if (!d_set || k < d) {
1047                                 d = k;
1048                                 d_set = true;
1049                         }
1050                 }
1051
1052                 c = n;
1053         }
1054
1055         if (!d_set)
1056                 return -ENOENT;
1057
1058         r = *val != d;
1059         *val = d;
1060         return r;
1061 }
1062
1063 static bool tm_out_of_bounds(const struct tm *tm, bool utc) {
1064         struct tm t;
1065         assert(tm);
1066
1067         t = *tm;
1068
1069         if (mktime_or_timegm(&t, utc) == (time_t) -1)
1070                 return true;
1071
1072         /*
1073          * Set an upper bound on the year so impossible dates like "*-02-31"
1074          * don't cause find_next() to loop forever. tm_year contains years
1075          * since 1900, so adjust it accordingly.
1076          */
1077         if (tm->tm_year + 1900 > MAX_YEAR)
1078                 return true;
1079
1080         /* Did any normalization take place? If so, it was out of bounds before */
1081         return
1082                 t.tm_year != tm->tm_year ||
1083                 t.tm_mon != tm->tm_mon ||
1084                 t.tm_mday != tm->tm_mday ||
1085                 t.tm_hour != tm->tm_hour ||
1086                 t.tm_min != tm->tm_min ||
1087                 t.tm_sec != tm->tm_sec;
1088 }
1089
1090 static bool matches_weekday(int weekdays_bits, const struct tm *tm, bool utc) {
1091         struct tm t;
1092         int k;
1093
1094         if (weekdays_bits < 0 || weekdays_bits >= BITS_WEEKDAYS)
1095                 return true;
1096
1097         t = *tm;
1098         if (mktime_or_timegm(&t, utc) == (time_t) -1)
1099                 return false;
1100
1101         k = t.tm_wday == 0 ? 6 : t.tm_wday - 1;
1102         return (weekdays_bits & (1 << k));
1103 }
1104
1105 static int find_next(const CalendarSpec *spec, struct tm *tm, usec_t *usec) {
1106         struct tm c;
1107         int tm_usec;
1108         int r;
1109
1110         assert(spec);
1111         assert(tm);
1112
1113         c = *tm;
1114         tm_usec = *usec;
1115
1116         for (;;) {
1117                 /* Normalize the current date */
1118                 (void) mktime_or_timegm(&c, spec->utc);
1119                 c.tm_isdst = spec->dst;
1120
1121                 c.tm_year += 1900;
1122                 r = find_matching_component(spec, spec->year, &c, &c.tm_year);
1123                 c.tm_year -= 1900;
1124
1125                 if (r > 0) {
1126                         c.tm_mon = 0;
1127                         c.tm_mday = 1;
1128                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1129                 }
1130                 if (r < 0)
1131                         return r;
1132                 if (tm_out_of_bounds(&c, spec->utc))
1133                         return -ENOENT;
1134
1135                 c.tm_mon += 1;
1136                 r = find_matching_component(spec, spec->month, &c, &c.tm_mon);
1137                 c.tm_mon -= 1;
1138
1139                 if (r > 0) {
1140                         c.tm_mday = 1;
1141                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1142                 }
1143                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1144                         c.tm_year++;
1145                         c.tm_mon = 0;
1146                         c.tm_mday = 1;
1147                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1148                         continue;
1149                 }
1150
1151                 r = find_matching_component(spec, spec->day, &c, &c.tm_mday);
1152                 if (r > 0)
1153                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1154                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1155                         c.tm_mon++;
1156                         c.tm_mday = 1;
1157                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1158                         continue;
1159                 }
1160
1161                 if (!matches_weekday(spec->weekdays_bits, &c, spec->utc)) {
1162                         c.tm_mday++;
1163                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1164                         continue;
1165                 }
1166
1167                 r = find_matching_component(spec, spec->hour, &c, &c.tm_hour);
1168                 if (r > 0)
1169                         c.tm_min = c.tm_sec = tm_usec = 0;
1170                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1171                         c.tm_mday++;
1172                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1173                         continue;
1174                 }
1175
1176                 r = find_matching_component(spec, spec->minute, &c, &c.tm_min);
1177                 if (r > 0)
1178                         c.tm_sec = tm_usec = 0;
1179                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1180                         c.tm_hour++;
1181                         c.tm_min = c.tm_sec = tm_usec = 0;
1182                         continue;
1183                 }
1184
1185                 c.tm_sec = c.tm_sec * USEC_PER_SEC + tm_usec;
1186                 r = find_matching_component(spec, spec->microsecond, &c, &c.tm_sec);
1187                 tm_usec = c.tm_sec % USEC_PER_SEC;
1188                 c.tm_sec /= USEC_PER_SEC;
1189
1190                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1191                         c.tm_min++;
1192                         c.tm_sec = tm_usec = 0;
1193                         continue;
1194                 }
1195
1196                 *tm = c;
1197                 *usec = tm_usec;
1198                 return 0;
1199         }
1200 }
1201
1202 int calendar_spec_next_usec(const CalendarSpec *spec, usec_t usec, usec_t *next) {
1203         struct tm tm;
1204         time_t t;
1205         int r;
1206         usec_t tm_usec;
1207
1208         assert(spec);
1209         assert(next);
1210
1211         usec++;
1212         t = (time_t) (usec / USEC_PER_SEC);
1213         assert_se(localtime_or_gmtime_r(&t, &tm, spec->utc));
1214         tm_usec = usec % USEC_PER_SEC;
1215
1216         r = find_next(spec, &tm, &tm_usec);
1217         if (r < 0)
1218                 return r;
1219
1220         t = mktime_or_timegm(&tm, spec->utc);
1221         if (t == (time_t) -1)
1222                 return -EINVAL;
1223
1224         *next = (usec_t) t * USEC_PER_SEC + tm_usec;
1225         return 0;
1226 }