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