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 (component_compare(&b[k-1], &next) == 0) {
 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_unlocked(',', f);
 261                                 else
 262                                         need_comma = true;
 263
 264                                 fputs_unlocked(days[x], f);
 265                                 l = x;
 266                         }
 267
 268                 } else if (l >= 0) {
 269
 270                         if (x > l + 1) {
 271                                 fputs_unlocked(x > l + 2 ? ".." : ",", f);
 272                                 fputs_unlocked(days[x-1], f);
 273                         }
 274
 275                         l = -1;
 276                 }
 277         }
 278
 279         if (l >= 0 && x > l + 1) {
 280                 fputs_unlocked(x > l + 2 ? ".." : ",", f);
 281                 fputs_unlocked(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_unlocked('*', f);
 292                 return;
 293         }
 294
 295         if (usec && c->start == 0 && c->repeat == USEC_PER_SEC && !c->next) {
 296                 fputc_unlocked('*', 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_unlocked(',', 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_unlocked(' ', f);
 338         }
 339
 340         format_chain(f, 4, c->year, false);
 341         fputc_unlocked('-', f);
 342         format_chain(f, 2, c->month, false);
 343         fputc_unlocked(c->end_of_month ? '~' : '-', f);
 344         format_chain(f, 2, c->day, false);
 345         fputc_unlocked(' ', f);
 346         format_chain(f, 2, c->hour, false);
 347         fputc_unlocked(':', f);
 348         format_chain(f, 2, c->minute, false);
 349         fputc_unlocked(':', f);
 350         format_chain(f, 2, c->microsecond, true);
 351
 352         if (c->utc)
 353                 fputs_unlocked(" 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_unlocked(' ', f);
 362                         fputs_unlocked(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_one_number(const char *p, const char **e, unsigned long *ret) {
 491         char *ee = NULL;
 492         unsigned long value;
 493
 494         errno = 0;
 495         value = strtoul(p, &ee, 10);
 496         if (errno > 0)
 497                 return -errno;
 498         if (ee == p)
 499                 return -EINVAL;
 500
 501         *ret = value;
 502         *e = ee;
 503         return 0;
 504 }
 505
 506 static int parse_component_decimal(const char **p, bool usec, int *res) {
 507         unsigned long value;
 508         const char *e = NULL;
 509         int r;
 510
 511         if (!isdigit(**p))
 512                 return -EINVAL;
 513
 514         r = parse_one_number(*p, &e, &value);
 515         if (r < 0)
 516                 return r;
 517
 518         if (usec) {
 519                 if (value * USEC_PER_SEC / USEC_PER_SEC != value)
 520                         return -ERANGE;
 521
 522                 value *= USEC_PER_SEC;
 523
 524                 /* One "." is a decimal point, but ".." is a range separator */
 525                 if (e[0] == '.' && e[1] != '.') {
 526                         unsigned add;
 527
 528                         e++;
 529                         r = parse_fractional_part_u(&e, 6, &add);
 530                         if (r < 0)
 531                                 return r;
 532
 533                         if (add + value < value)
 534                                 return -ERANGE;
 535                         value += add;
 536                 }
 537         }
 538
 539         if (value > INT_MAX)
 540                 return -ERANGE;
 541
 542         *p = e;
 543         *res = value;
 544
 545         return 0;
 546 }
 547
 548 static int const_chain(int value, CalendarComponent **c) {
 549         CalendarComponent *cc = NULL;
 550
 551         assert(c);
 552
 553         cc = new0(CalendarComponent, 1);
 554         if (!cc)
 555                 return -ENOMEM;
 556
 557         cc->start = value;
 558         cc->stop = -1;
 559         cc->repeat = 0;
 560         cc->next = *c;
 561
 562         *c = cc;
 563
 564         return 0;
 565 }
 566
 567 static int calendarspec_from_time_t(CalendarSpec *c, time_t time) {
 568         struct tm tm;
 569         CalendarComponent *year = NULL, *month = NULL, *day = NULL, *hour = NULL, *minute = NULL, *us = NULL;
 570         int r;
 571
 572         assert_se(gmtime_r(&time, &tm));
 573
 574         r = const_chain(tm.tm_year + 1900, &year);
 575         if (r < 0)
 576                 return r;
 577
 578         r = const_chain(tm.tm_mon + 1, &month);
 579         if (r < 0)
 580                 return r;
 581
 582         r = const_chain(tm.tm_mday, &day);
 583         if (r < 0)
 584                 return r;
 585
 586         r = const_chain(tm.tm_hour, &hour);
 587         if (r < 0)
 588                 return r;
 589
 590         r = const_chain(tm.tm_min, &minute);
 591         if (r < 0)
 592                 return r;
 593
 594         r = const_chain(tm.tm_sec * USEC_PER_SEC, &us);
 595         if (r < 0)
 596                 return r;
 597
 598         c->utc = true;
 599         c->year = year;
 600         c->month = month;
 601         c->day = day;
 602         c->hour = hour;
 603         c->minute = minute;
 604         c->microsecond = us;
 605         return 0;
 606 }
 607
 608 static int prepend_component(const char **p, bool usec, CalendarComponent **c) {
 609         int r, start, stop = -1, repeat = 0;
 610         CalendarComponent *cc;
 611         const char *e;
 612
 613         assert(p);
 614         assert(c);
 615
 616         e = *p;
 617
 618         r = parse_component_decimal(&e, usec, &start);
 619         if (r < 0)
 620                 return r;
 621
 622         if (e[0] == '.' && e[1] == '.') {
 623                 e += 2;
 624                 r = parse_component_decimal(&e, usec, &stop);
 625                 if (r < 0)
 626                         return r;
 627
 628                 repeat = usec ? USEC_PER_SEC : 1;
 629         }
 630
 631         if (*e == '/') {
 632                 e++;
 633                 r = parse_component_decimal(&e, usec, &repeat);
 634                 if (r < 0)
 635                         return r;
 636
 637                 if (repeat == 0)
 638                         return -ERANGE;
 639         }
 640
 641         if (*e != 0 && *e != ' ' && *e != ',' && *e != '-' && *e != '~' && *e != ':')
 642                 return -EINVAL;
 643
 644         cc = new0(CalendarComponent, 1);
 645         if (!cc)
 646                 return -ENOMEM;
 647
 648         cc->start = start;
 649         cc->stop = stop;
 650         cc->repeat = repeat;
 651         cc->next = *c;
 652
 653         *p = e;
 654         *c = cc;
 655
 656         if (*e ==',') {
 657                 *p += 1;
 658                 return prepend_component(p, usec, c);
 659         }
 660
 661         return 0;
 662 }
 663
 664 static int parse_chain(const char **p, bool usec, CalendarComponent **c) {
 665         const char *t;
 666         CalendarComponent *cc = NULL;
 667         int r;
 668
 669         assert(p);
 670         assert(c);
 671
 672         t = *p;
 673
 674         if (t[0] == '*') {
 675                 if (usec) {
 676                         r = const_chain(0, c);
 677                         if (r < 0)
 678                                 return r;
 679                         (*c)->repeat = USEC_PER_SEC;
 680                 } else
 681                         *c = NULL;
 682
 683                 *p = t + 1;
 684                 return 0;
 685         }
 686
 687         r = prepend_component(&t, usec, &cc);
 688         if (r < 0) {
 689                 free_chain(cc);
 690                 return r;
 691         }
 692
 693         *p = t;
 694         *c = cc;
 695         return 0;
 696 }
 697
 698 static int parse_date(const char **p, CalendarSpec *c) {
 699         const char *t;
 700         int r;
 701         CalendarComponent *first, *second, *third;
 702
 703         assert(p);
 704         assert(*p);
 705         assert(c);
 706
 707         t = *p;
 708
 709         if (*t == 0)
 710                 return 0;
 711
 712         /* @TIMESTAMP — UNIX time in seconds since the epoch */
 713         if (*t == '@') {
 714                 unsigned long value;
 715                 time_t time;
 716
 717                 r = parse_one_number(t + 1, &t, &value);
 718                 if (r < 0)
 719                         return r;
 720
 721                 time = value;
 722                 if ((unsigned long) time != value)
 723                         return -ERANGE;
 724
 725                 r = calendarspec_from_time_t(c, time);
 726                 if (r < 0)
 727                         return r;
 728
 729                 *p = t;
 730                 return 1; /* finito, don't parse H:M:S after that */
 731         }
 732
 733         r = parse_chain(&t, false, &first);
 734         if (r < 0)
 735                 return r;
 736
 737         /* Already the end? A ':' as separator? In that case this was a time, not a date */
 738         if (*t == 0 || *t == ':') {
 739                 free_chain(first);
 740                 return 0;
 741         }
 742
 743         if (*t == '~')
 744                 c->end_of_month = true;
 745         else if (*t != '-') {
 746                 free_chain(first);
 747                 return -EINVAL;
 748         }
 749
 750         t++;
 751         r = parse_chain(&t, false, &second);
 752         if (r < 0) {
 753                 free_chain(first);
 754                 return r;
 755         }
 756
 757         /* Got two parts, hence it's month and day */
 758         if (*t == ' ' || *t == 0) {
 759                 *p = t + strspn(t, " ");
 760                 c->month = first;
 761                 c->day = second;
 762                 return 0;
 763         } else if (c->end_of_month) {
 764                 free_chain(first);
 765                 free_chain(second);
 766                 return -EINVAL;
 767         }
 768
 769         if (*t == '~')
 770                 c->end_of_month = true;
 771         else if (*t != '-') {
 772                 free_chain(first);
 773                 free_chain(second);
 774                 return -EINVAL;
 775         }
 776
 777         t++;
 778         r = parse_chain(&t, false, &third);
 779         if (r < 0) {
 780                 free_chain(first);
 781                 free_chain(second);
 782                 return r;
 783         }
 784
 785         /* Got three parts, hence it is year, month and day */
 786         if (*t == ' ' || *t == 0) {
 787                 *p = t + strspn(t, " ");
 788                 c->year = first;
 789                 c->month = second;
 790                 c->day = third;
 791                 return 0;
 792         }
 793
 794         free_chain(first);
 795         free_chain(second);
 796         free_chain(third);
 797         return -EINVAL;
 798 }
 799
 800 static int parse_calendar_time(const char **p, CalendarSpec *c) {
 801         CalendarComponent *h = NULL, *m = NULL, *s = NULL;
 802         const char *t;
 803         int r;
 804
 805         assert(p);
 806         assert(*p);
 807         assert(c);
 808
 809         t = *p;
 810
 811         /* If no time is specified at all, then this means 00:00:00 */
 812         if (*t == 0)
 813                 goto null_hour;
 814
 815         r = parse_chain(&t, false, &h);
 816         if (r < 0)
 817                 goto fail;
 818
 819         if (*t != ':') {
 820                 r = -EINVAL;
 821                 goto fail;
 822         }
 823
 824         t++;
 825         r = parse_chain(&t, false, &m);
 826         if (r < 0)
 827                 goto fail;
 828
 829         /* Already at the end? Then it's hours and minutes, and seconds are 0 */
 830         if (*t == 0)
 831                 goto null_second;
 832
 833         if (*t != ':') {
 834                 r = -EINVAL;
 835                 goto fail;
 836         }
 837
 838         t++;
 839         r = parse_chain(&t, true, &s);
 840         if (r < 0)
 841                 goto fail;
 842
 843         /* At the end? Then it's hours, minutes and seconds */
 844         if (*t == 0)
 845                 goto finish;
 846
 847         r = -EINVAL;
 848         goto fail;
 849
 850 null_hour:
 851         r = const_chain(0, &h);
 852         if (r < 0)
 853                 goto fail;
 854
 855         r = const_chain(0, &m);
 856         if (r < 0)
 857                 goto fail;
 858
 859 null_second:
 860         r = const_chain(0, &s);
 861         if (r < 0)
 862                 goto fail;
 863
 864 finish:
 865         *p = t;
 866         c->hour = h;
 867         c->minute = m;
 868         c->microsecond = s;
 869
 870         return 0;
 871
 872 fail:
 873         free_chain(h);
 874         free_chain(m);
 875         free_chain(s);
 876         return r;
 877 }
 878
 879 int calendar_spec_from_string(const char *p, CalendarSpec **spec) {
 880         const char *utc;
 881         CalendarSpec *c;
 882         int r;
 883
 884         assert(p);
 885         assert(spec);
 886
 887         c = new0(CalendarSpec, 1);
 888         if (!c)
 889                 return -ENOMEM;
 890         c->dst = -1;
 891
 892         utc = endswith_no_case(p, " UTC");
 893         if (utc) {
 894                 c->utc = true;
 895                 p = strndupa(p, utc - p);
 896         } else {
 897                 const char *e = NULL;
 898                 int j;
 899
 900                 tzset();
 901
 902                 /* Check if the local timezone was specified? */
 903                 for (j = 0; j <= 1; j++) {
 904                         if (isempty(tzname[j]))
 905                                 continue;
 906
 907                         e = endswith_no_case(p, tzname[j]);
 908                         if (!e)
 909                                 continue;
 910                         if (e == p)
 911                                 continue;
 912                         if (e[-1] != ' ')
 913                                 continue;
 914
 915                         break;
 916                 }
 917
 918                 /* Found one of the two timezones specified? */
 919                 if (IN_SET(j, 0, 1)) {
 920                         p = strndupa(p, e - p - 1);
 921                         c->dst = j;
 922                 }
 923         }
 924
 925         if (isempty(p)) {
 926                 r = -EINVAL;
 927                 goto fail;
 928         }
 929
 930         if (strcaseeq(p, "minutely")) {
 931                 r = const_chain(0, &c->microsecond);
 932                 if (r < 0)
 933                         goto fail;
 934
 935         } else if (strcaseeq(p, "hourly")) {
 936                 r = const_chain(0, &c->minute);
 937                 if (r < 0)
 938                         goto fail;
 939                 r = const_chain(0, &c->microsecond);
 940                 if (r < 0)
 941                         goto fail;
 942
 943         } else if (strcaseeq(p, "daily")) {
 944                 r = const_chain(0, &c->hour);
 945                 if (r < 0)
 946                         goto fail;
 947                 r = const_chain(0, &c->minute);
 948                 if (r < 0)
 949                         goto fail;
 950                 r = const_chain(0, &c->microsecond);
 951                 if (r < 0)
 952                         goto fail;
 953
 954         } else if (strcaseeq(p, "monthly")) {
 955                 r = const_chain(1, &c->day);
 956                 if (r < 0)
 957                         goto fail;
 958                 r = const_chain(0, &c->hour);
 959                 if (r < 0)
 960                         goto fail;
 961                 r = const_chain(0, &c->minute);
 962                 if (r < 0)
 963                         goto fail;
 964                 r = const_chain(0, &c->microsecond);
 965                 if (r < 0)
 966                         goto fail;
 967
 968         } else if (strcaseeq(p, "annually") ||
 969                    strcaseeq(p, "yearly") ||
 970                    strcaseeq(p, "anually") /* backwards compatibility */ ) {
 971
 972                 r = const_chain(1, &c->month);
 973                 if (r < 0)
 974                         goto fail;
 975                 r = const_chain(1, &c->day);
 976                 if (r < 0)
 977                         goto fail;
 978                 r = const_chain(0, &c->hour);
 979                 if (r < 0)
 980                         goto fail;
 981                 r = const_chain(0, &c->minute);
 982                 if (r < 0)
 983                         goto fail;
 984                 r = const_chain(0, &c->microsecond);
 985                 if (r < 0)
 986                         goto fail;
 987
 988         } else if (strcaseeq(p, "weekly")) {
 989
 990                 c->weekdays_bits = 1;
 991
 992                 r = const_chain(0, &c->hour);
 993                 if (r < 0)
 994                         goto fail;
 995                 r = const_chain(0, &c->minute);
 996                 if (r < 0)
 997                         goto fail;
 998                 r = const_chain(0, &c->microsecond);
 999                 if (r < 0)
1000                         goto fail;
1001
1002         } else if (strcaseeq(p, "quarterly")) {
1003
1004                 r = const_chain(1, &c->month);
1005                 if (r < 0)
1006                         goto fail;
1007                 r = const_chain(4, &c->month);
1008                 if (r < 0)
1009                         goto fail;
1010                 r = const_chain(7, &c->month);
1011                 if (r < 0)
1012                         goto fail;
1013                 r = const_chain(10, &c->month);
1014                 if (r < 0)
1015                         goto fail;
1016                 r = const_chain(1, &c->day);
1017                 if (r < 0)
1018                         goto fail;
1019                 r = const_chain(0, &c->hour);
1020                 if (r < 0)
1021                         goto fail;
1022                 r = const_chain(0, &c->minute);
1023                 if (r < 0)
1024                         goto fail;
1025                 r = const_chain(0, &c->microsecond);
1026                 if (r < 0)
1027                         goto fail;
1028
1029         } else if (strcaseeq(p, "biannually") ||
1030                    strcaseeq(p, "bi-annually") ||
1031                    strcaseeq(p, "semiannually") ||
1032                    strcaseeq(p, "semi-annually")) {
1033
1034                 r = const_chain(1, &c->month);
1035                 if (r < 0)
1036                         goto fail;
1037                 r = const_chain(7, &c->month);
1038                 if (r < 0)
1039                         goto fail;
1040                 r = const_chain(1, &c->day);
1041                 if (r < 0)
1042                         goto fail;
1043                 r = const_chain(0, &c->hour);
1044                 if (r < 0)
1045                         goto fail;
1046                 r = const_chain(0, &c->minute);
1047                 if (r < 0)
1048                         goto fail;
1049                 r = const_chain(0, &c->microsecond);
1050                 if (r < 0)
1051                         goto fail;
1052
1053         } else {
1054                 r = parse_weekdays(&p, c);
1055                 if (r < 0)
1056                         goto fail;
1057
1058                 r = parse_date(&p, c);
1059                 if (r < 0)
1060                         goto fail;
1061
1062                 if (r == 0) {
1063                         r = parse_calendar_time(&p, c);
1064                         if (r < 0)
1065                                 goto fail;
1066                 }
1067
1068                 if (*p != 0) {
1069                         r = -EINVAL;
1070                         goto fail;
1071                 }
1072         }
1073
1074         r = calendar_spec_normalize(c);
1075         if (r < 0)
1076                 goto fail;
1077
1078         if (!calendar_spec_valid(c)) {
1079                 r = -EINVAL;
1080                 goto fail;
1081         }
1082
1083         *spec = c;
1084         return 0;
1085
1086 fail:
1087         calendar_spec_free(c);
1088         return r;
1089 }
1090
1091 static int find_end_of_month(struct tm *tm, bool utc, int day) {
1092         struct tm t = *tm;
1093
1094         t.tm_mon++;
1095         t.tm_mday = 1 - day;
1096
1097         if (mktime_or_timegm(&t, utc) < 0 ||
1098             t.tm_mon != tm->tm_mon)
1099                 return -1;
1100
1101         return t.tm_mday;
1102 }
1103
1104 static int find_matching_component(const CalendarSpec *spec, const CalendarComponent *c,
1105                                    struct tm *tm, int *val) {
1106         const CalendarComponent *p = c;
1107         int start, stop, d = -1;
1108         bool d_set = false;
1109         int r;
1110
1111         assert(val);
1112
1113         if (!c)
1114                 return 0;
1115
1116         while (c) {
1117                 start = c->start;
1118                 stop = c->stop;
1119
1120                 if (spec->end_of_month && p == spec->day) {
1121                         start = find_end_of_month(tm, spec->utc, start);
1122                         stop = find_end_of_month(tm, spec->utc, stop);
1123
1124                         if (stop > 0)
1125                                 SWAP_TWO(start, stop);
1126                 }
1127
1128                 if (start >= *val) {
1129
1130                         if (!d_set || start < d) {
1131                                 d = start;
1132                                 d_set = true;
1133                         }
1134
1135                 } else if (c->repeat > 0) {
1136                         int k;
1137
1138                         k = start + c->repeat * ((*val - start + c->repeat - 1) / c->repeat);
1139
1140                         if ((!d_set || k < d) && (stop < 0 || k <= stop)) {
1141                                 d = k;
1142                                 d_set = true;
1143                         }
1144                 }
1145
1146                 c = c->next;
1147         }
1148
1149         if (!d_set)
1150                 return -ENOENT;
1151
1152         r = *val != d;
1153         *val = d;
1154         return r;
1155 }
1156
1157 static bool tm_out_of_bounds(const struct tm *tm, bool utc) {
1158         struct tm t;
1159         assert(tm);
1160
1161         t = *tm;
1162
1163         if (mktime_or_timegm(&t, utc) < 0)
1164                 return true;
1165
1166         /*
1167          * Set an upper bound on the year so impossible dates like "*-02-31"
1168          * don't cause find_next() to loop forever. tm_year contains years
1169          * since 1900, so adjust it accordingly.
1170          */
1171         if (tm->tm_year + 1900 > MAX_YEAR)
1172                 return true;
1173
1174         /* Did any normalization take place? If so, it was out of bounds before */
1175         return
1176                 t.tm_year != tm->tm_year ||
1177                 t.tm_mon != tm->tm_mon ||
1178                 t.tm_mday != tm->tm_mday ||
1179                 t.tm_hour != tm->tm_hour ||
1180                 t.tm_min != tm->tm_min ||
1181                 t.tm_sec != tm->tm_sec;
1182 }
1183
1184 static bool matches_weekday(int weekdays_bits, const struct tm *tm, bool utc) {
1185         struct tm t;
1186         int k;
1187
1188         if (weekdays_bits < 0 || weekdays_bits >= BITS_WEEKDAYS)
1189                 return true;
1190
1191         t = *tm;
1192         if (mktime_or_timegm(&t, utc) < 0)
1193                 return false;
1194
1195         k = t.tm_wday == 0 ? 6 : t.tm_wday - 1;
1196         return (weekdays_bits & (1 << k));
1197 }
1198
1199 static int find_next(const CalendarSpec *spec, struct tm *tm, usec_t *usec) {
1200         struct tm c;
1201         int tm_usec;
1202         int r;
1203
1204         assert(spec);
1205         assert(tm);
1206
1207         c = *tm;
1208         tm_usec = *usec;
1209
1210         for (;;) {
1211                 /* Normalize the current date */
1212                 (void) mktime_or_timegm(&c, spec->utc);
1213                 c.tm_isdst = spec->dst;
1214
1215                 c.tm_year += 1900;
1216                 r = find_matching_component(spec, spec->year, &c, &c.tm_year);
1217                 c.tm_year -= 1900;
1218
1219                 if (r > 0) {
1220                         c.tm_mon = 0;
1221                         c.tm_mday = 1;
1222                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1223                 }
1224                 if (r < 0)
1225                         return r;
1226                 if (tm_out_of_bounds(&c, spec->utc))
1227                         return -ENOENT;
1228
1229                 c.tm_mon += 1;
1230                 r = find_matching_component(spec, spec->month, &c, &c.tm_mon);
1231                 c.tm_mon -= 1;
1232
1233                 if (r > 0) {
1234                         c.tm_mday = 1;
1235                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1236                 }
1237                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1238                         c.tm_year++;
1239                         c.tm_mon = 0;
1240                         c.tm_mday = 1;
1241                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1242                         continue;
1243                 }
1244
1245                 r = find_matching_component(spec, spec->day, &c, &c.tm_mday);
1246                 if (r > 0)
1247                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1248                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1249                         c.tm_mon++;
1250                         c.tm_mday = 1;
1251                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1252                         continue;
1253                 }
1254
1255                 if (!matches_weekday(spec->weekdays_bits, &c, spec->utc)) {
1256                         c.tm_mday++;
1257                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1258                         continue;
1259                 }
1260
1261                 r = find_matching_component(spec, spec->hour, &c, &c.tm_hour);
1262                 if (r > 0)
1263                         c.tm_min = c.tm_sec = tm_usec = 0;
1264                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1265                         c.tm_mday++;
1266                         c.tm_hour = c.tm_min = c.tm_sec = tm_usec = 0;
1267                         continue;
1268                 }
1269
1270                 r = find_matching_component(spec, spec->minute, &c, &c.tm_min);
1271                 if (r > 0)
1272                         c.tm_sec = tm_usec = 0;
1273                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1274                         c.tm_hour++;
1275                         c.tm_min = c.tm_sec = tm_usec = 0;
1276                         continue;
1277                 }
1278
1279                 c.tm_sec = c.tm_sec * USEC_PER_SEC + tm_usec;
1280                 r = find_matching_component(spec, spec->microsecond, &c, &c.tm_sec);
1281                 tm_usec = c.tm_sec % USEC_PER_SEC;
1282                 c.tm_sec /= USEC_PER_SEC;
1283
1284                 if (r < 0 || tm_out_of_bounds(&c, spec->utc)) {
1285                         c.tm_min++;
1286                         c.tm_sec = tm_usec = 0;
1287                         continue;
1288                 }
1289
1290                 *tm = c;
1291                 *usec = tm_usec;
1292                 return 0;
1293         }
1294 }
1295
1296 int calendar_spec_next_usec(const CalendarSpec *spec, usec_t usec, usec_t *next) {
1297         struct tm tm;
1298         time_t t;
1299         int r;
1300         usec_t tm_usec;
1301
1302         assert(spec);
1303         assert(next);
1304
1305         if (usec > USEC_TIMESTAMP_FORMATTABLE_MAX)
1306                 return -EINVAL;
1307
1308         usec++;
1309         t = (time_t) (usec / USEC_PER_SEC);
1310         assert_se(localtime_or_gmtime_r(&t, &tm, spec->utc));
1311         tm_usec = usec % USEC_PER_SEC;
1312
1313         r = find_next(spec, &tm, &tm_usec);
1314         if (r < 0)
1315                 return r;
1316
1317         t = mktime_or_timegm(&tm, spec->utc);
1318         if (t < 0)
1319                 return -EINVAL;
1320
1321         *next = (usec_t) t * USEC_PER_SEC + tm_usec;
1322         return 0;
1323 }