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