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