--- /dev/null
+package main
+
+import (
+ "errors"
+ "fmt"
+ "strconv"
+ "strings"
+ "time"
+)
+
+const (
+ // scheduleCronGap is the shortest time between two runs of a cron
+ // expression. Each run is a full turn, so shorter gaps use the quota
+ // too fast.
+ scheduleCronGap = 5
+
+ // scheduleCronYears is how many years the search for the next time
+ // covers.
+ scheduleCronYears = 8
+)
+
+// scheduleCronFields are the fields of a cron expression, in order, with their
+// lowest and highest values.
+var scheduleCronFields = []struct {
+ name string
+ low int
+ high int
+}{
+ {
+ name: "minute",
+ low: 0,
+ high: 59,
+ },
+ {
+ name: "hour",
+ low: 0,
+ high: 23,
+ },
+ {
+ name: "day of month",
+ low: 1,
+ high: 31,
+ },
+ {
+ name: "month",
+ low: 1,
+ high: 12,
+ },
+ {
+ name: "day of week",
+ low: 0,
+ high: 7,
+ },
+}
+
+// scheduleParseCron parses a cron expression of five fields: minute, hour, day
+// of month, month, and day of week, where 0 and 7 are Sunday. A field is a
+// comma list of items, and an item is *, N, or N-M, where * and N-M can have a
+// step /S. Names, macros, the characters ? L W #, and N/S are errors.
+//
+// It refuses an expression whose runs can be less than scheduleCronGap minutes
+// apart. The check takes the wall times of one day from the hour and the minute
+// fields, and the gap across midnight as if the next day matches too. It also
+// refuses an expression that matches no day in scheduleCronYears years, such as
+// one on February 30.
+func scheduleParseCron(expression string) (ScheduleCron, error) {
+ fields := strings.Fields(expression)
+ if len(fields) != len(scheduleCronFields) {
+ return ScheduleCron{}, fmt.Errorf("the cron expression %q has %d fields, not 5: minute, hour, day of month, month, day of week", expression, len(fields))
+ }
+
+ var sets [5]uint64
+ for index, field := range fields {
+ set, err := scheduleCronField(field, scheduleCronFields[index].low, scheduleCronFields[index].high)
+ if err != nil {
+ return ScheduleCron{}, fmt.Errorf("the %s field of %q: %w", scheduleCronFields[index].name, expression, err)
+ }
+
+ sets[index] = set
+ }
+
+ c := ScheduleCron{
+ minutes: sets[0],
+ hours: sets[1],
+ days: sets[2],
+ months: sets[3],
+ weekdays: sets[4],
+ anyDay: strings.HasPrefix(fields[2], "*"),
+ anyWeekday: strings.HasPrefix(fields[4], "*"),
+ description: strings.Join(fields, " "),
+ }
+
+ if c.weekdays&(1<<7) != 0 {
+ c.weekdays |= 1
+ }
+
+ if c.gap() < scheduleCronGap {
+ return ScheduleCron{}, fmt.Errorf("the runs of %q can be less than %d minutes apart: the runs of a schedule must be at least %d minutes apart", expression, scheduleCronGap, scheduleCronGap)
+ }
+
+ start := time.Date(2024, time.January, 1, 0, 0, 0, 0, time.UTC)
+ _, found := c.Next(start)
+ if !found {
+ return ScheduleCron{}, fmt.Errorf("the cron expression %q matches no day in %d years", expression, scheduleCronYears)
+ }
+
+ return c, nil
+}
+
+// ScheduleCron is a parsed cron expression. Each set holds a bit for each value
+// of its field. anyDay and anyWeekday tell that the day field or the weekday
+// field starts with *. When neither does, a day matches when either field
+// matches, as in classic cron. Otherwise both fields must match.
+type ScheduleCron struct {
+ minutes uint64
+ hours uint64
+ days uint64
+ months uint64
+ weekdays uint64
+ anyDay bool
+ anyWeekday bool
+ description string
+}
+
+// String returns the expression with one space between its fields.
+func (c ScheduleCron) String() string {
+ return c.description
+}
+
+// Next returns the first time after after whose wall time in the location of
+// after matches, or false when no time in scheduleCronYears years matches. A
+// wall time goes through scheduleWallTime, so a wall time that the clock skips
+// runs later by the length of the skip, and a wall time that the clock repeats
+// runs once, at its first occurrence.
+func (c ScheduleCron) Next(after time.Time) (time.Time, bool) {
+ location := after.Location()
+ year, month, day := after.Date()
+ first := time.Date(year, month, day, 0, 0, 0, 0, time.UTC)
+ last := first.AddDate(scheduleCronYears, 0, 0)
+ for date := first; date.Before(last); date = date.AddDate(0, 0, 1) {
+ if !c.day(date) {
+ continue
+ }
+
+ // A wall time that the clock skips moves later, so the times of
+ // one day are not always in order. The first time is the
+ // smallest one.
+ var next time.Time
+ for hour := range 24 {
+ if c.hours&(1<<hour) == 0 {
+ continue
+ }
+
+ for minute := range 60 {
+ if c.minutes&(1<<minute) == 0 {
+ continue
+ }
+
+ t := scheduleWallTime(date.Year(), date.Month(), date.Day(), hour, minute, location)
+ if t.After(after) && (next.IsZero() || t.Before(next)) {
+ next = t
+ }
+ }
+ }
+
+ if !next.IsZero() {
+ return next, true
+ }
+ }
+
+ return time.Time{}, false
+}
+
+// day tells if the calendar date matches the month and the day fields.
+func (c ScheduleCron) day(date time.Time) bool {
+ if c.months&(1<<int(date.Month())) == 0 {
+ return false
+ }
+
+ day := c.days&(1<<date.Day()) != 0
+ weekday := c.weekdays&(1<<int(date.Weekday())) != 0
+ if c.anyDay || c.anyWeekday {
+ return day && weekday
+ }
+
+ return day || weekday
+}
+
+// gap returns the shortest time in minutes between two wall times of the hour
+// and the minute fields, also across midnight.
+func (c ScheduleCron) gap() int {
+ var times []int
+ for hour := range 24 {
+ for minute := range 60 {
+ if c.hours&(1<<hour) != 0 && c.minutes&(1<<minute) != 0 {
+ times = append(times, 60*hour+minute)
+ }
+ }
+ }
+
+ gap := times[0] + 24*60 - times[len(times)-1]
+ for index := 1; index < len(times); index++ {
+ gap = min(gap, times[index]-times[index-1])
+ }
+
+ return gap
+}
+
+// scheduleWallTime returns the time of a wall time in location. A wall time
+// that the clock skips, at the start of daylight saving time, is later by the
+// length of the skip: 02:30 becomes 03:30 when the clock goes from 02:00 to
+// 03:00. A wall time that the clock repeats, at the end of daylight saving
+// time, is its first occurrence, as in cron.
+func scheduleWallTime(year int, month time.Month, day, hour, minute int, location *time.Location) time.Time {
+ t := time.Date(year, month, day, hour, minute, 0, 0, location)
+ _, before := t.Add(-3 * time.Hour).Zone()
+ _, offset := t.Zone()
+ if t.Hour() != hour || t.Minute() != minute || t.Day() != day {
+ wall := time.Date(year, month, day, hour, minute, 0, 0, time.UTC)
+
+ return wall.Add(-time.Duration(before) * time.Second).In(location)
+ }
+
+ if before > offset {
+ earlier := t.Add(-time.Duration(before-offset) * time.Second)
+ if earlier.Day() == day && earlier.Hour() == hour && earlier.Minute() == minute {
+ return earlier
+ }
+ }
+
+ return t
+}
+
+// scheduleCronField returns the set of the values of one field, from low to
+// high.
+func scheduleCronField(field string, low, high int) (uint64, error) {
+ var set uint64
+ for item := range strings.SplitSeq(field, ",") {
+ base, stepText, stepped := strings.Cut(item, "/")
+ step := 1
+ if stepped {
+ var err error
+ step, err = scheduleCronNumber(stepText, 1, high)
+ if err != nil {
+ return 0, fmt.Errorf("the step of %q: %w", item, err)
+ }
+ }
+
+ first, last := low, high
+ startText, endText, ranged := strings.Cut(base, "-")
+ switch {
+ case base == "*":
+ case ranged:
+ var err error
+ first, err = scheduleCronNumber(startText, low, high)
+ if err == nil {
+ last, err = scheduleCronNumber(endText, low, high)
+ }
+
+ if err == nil && first > last {
+ err = errors.New("the start is after the end")
+ }
+
+ if err != nil {
+ return 0, fmt.Errorf("the range %q: %w", base, err)
+ }
+ case stepped:
+ return 0, fmt.Errorf("%q has a step after a single value: write a range N-M/S or */S", item)
+ default:
+ var err error
+ first, err = scheduleCronNumber(base, low, high)
+ if err != nil {
+ return 0, err
+ }
+
+ last = first
+ }
+
+ for value := first; value <= last; value += step {
+ set |= 1 << value
+ }
+ }
+
+ return set, nil
+}
+
+// scheduleCronNumber returns the value of text, a decimal number from low to
+// high.
+func scheduleCronNumber(text string, low, high int) (int, error) {
+ if text == "" || strings.Trim(text, "0123456789") != "" {
+ return 0, fmt.Errorf("%q is not a number from %d to %d", text, low, high)
+ }
+
+ value, err := strconv.Atoi(text)
+ if err != nil || value < low || value > high {
+ return 0, fmt.Errorf("%q is not a number from %d to %d", text, low, high)
+ }
+
+ return value, nil
+}
--- /dev/null
+package main
+
+import (
+ "testing"
+ "time"
+ _ "time/tzdata"
+
+ "github.com/stretchr/testify/require"
+)
+
+func TestScheduleParseCronAccepts(t *testing.T) {
+ testCases := []struct {
+ name string
+ expression string
+ }{
+ {
+ name: "every 5 minutes is the shortest gap",
+ expression: "*/5 * * * *",
+ },
+ {
+ name: "weekdays at 8",
+ expression: "0 8 * * 1-5",
+ },
+ {
+ name: "lists and ranges in office hours",
+ expression: "0,30 9-17 * * 1-5",
+ },
+ {
+ name: "a range with a step",
+ expression: "0 0 1-31/10 * *",
+ },
+ {
+ name: "February 29 of the leap years",
+ expression: "0 12 29 2 *",
+ },
+ {
+ name: "5 minutes across the end of an hour",
+ expression: "0,55 * * * *",
+ },
+ }
+
+ for _, tc := range testCases {
+ t.Run(tc.name, func(t *testing.T) {
+ cron, err := scheduleParseCron(tc.expression)
+ require.NoError(t, err)
+ require.Equal(t, tc.expression, cron.String())
+ })
+ }
+}
+
+func TestScheduleParseCronRefuses(t *testing.T) {
+ testCases := []struct {
+ name string
+ expression string
+ message string
+ }{
+ {
+ name: "four fields",
+ expression: "* * * *",
+ message: "has 4 fields, not 5",
+ },
+ {
+ name: "a seconds field",
+ expression: "0 0 8 * * *",
+ message: "has 6 fields, not 5",
+ },
+ {
+ name: "a macro",
+ expression: "@daily",
+ message: "has 1 fields, not 5",
+ },
+ {
+ name: "a day name",
+ expression: "0 8 * * MON",
+ message: `the day of week field of "0 8 * * MON": "MON" is not a number from 0 to 7`,
+ },
+ {
+ name: "a month name",
+ expression: "0 8 * JAN *",
+ message: `"JAN" is not a number from 1 to 12`,
+ },
+ {
+ name: "a question mark",
+ expression: "0 8 ? * *",
+ message: `"?" is not a number from 1 to 31`,
+ },
+ {
+ name: "the last day",
+ expression: "0 8 L * *",
+ message: `"L" is not a number`,
+ },
+ {
+ name: "the nearest weekday",
+ expression: "0 8 15W * *",
+ message: `"15W" is not a number`,
+ },
+ {
+ name: "the nth weekday",
+ expression: "0 8 * * 1#2",
+ message: `"1#2" is not a number`,
+ },
+ {
+ name: "a step after a single value",
+ expression: "5/10 * * * *",
+ message: "has a step after a single value",
+ },
+ {
+ name: "a minute out of range",
+ expression: "60 * * * *",
+ message: `"60" is not a number from 0 to 59`,
+ },
+ {
+ name: "an hour out of range",
+ expression: "0 24 * * *",
+ message: `"24" is not a number from 0 to 23`,
+ },
+ {
+ name: "day 0",
+ expression: "0 8 0 * *",
+ message: `"0" is not a number from 1 to 31`,
+ },
+ {
+ name: "month 13",
+ expression: "0 8 * 13 *",
+ message: `"13" is not a number from 1 to 12`,
+ },
+ {
+ name: "weekday 8",
+ expression: "0 8 * * 8",
+ message: `"8" is not a number from 0 to 7`,
+ },
+ {
+ name: "a negative number",
+ expression: "0 8 * * -1",
+ message: `the range "-1"`,
+ },
+ {
+ name: "a range with its start after its end",
+ expression: "0 10-5 * * *",
+ message: "the start is after the end",
+ },
+ {
+ name: "a step of 0",
+ expression: "0 */0 * * *",
+ message: `the step of "*/0"`,
+ },
+ {
+ name: "an empty item",
+ expression: "0,,30 * * * *",
+ message: `"" is not a number`,
+ },
+ {
+ name: "a day that never comes",
+ expression: "0 0 30 2 *",
+ message: "matches no day in 8 years",
+ },
+ {
+ name: "every minute",
+ expression: "* * * * *",
+ message: "the runs of a schedule must be at least 5 minutes apart",
+ },
+ {
+ name: "every 2 minutes",
+ expression: "*/2 * * * *",
+ message: "the runs of a schedule must be at least 5 minutes apart",
+ },
+ {
+ name: "two runs in one minute of the hour",
+ expression: "58,59 * * * *",
+ message: "the runs of a schedule must be at least 5 minutes apart",
+ },
+ {
+ name: "two runs across the end of an hour",
+ expression: "0,59 * * * *",
+ message: "the runs of a schedule must be at least 5 minutes apart",
+ },
+ {
+ name: "two runs across midnight",
+ expression: "0,59 0,23 * * *",
+ message: "the runs of a schedule must be at least 5 minutes apart",
+ },
+ }
+
+ for _, tc := range testCases {
+ t.Run(tc.name, func(t *testing.T) {
+ _, err := scheduleParseCron(tc.expression)
+ require.ErrorContains(t, err, tc.message)
+ })
+ }
+}
+
+func TestScheduleCronNext(t *testing.T) {
+ newYork, err := time.LoadLocation("America/New_York")
+ require.NoError(t, err)
+
+ testCases := []struct {
+ name string
+ expression string
+ after time.Time
+ next time.Time
+ }{
+ {
+ name: "a weekday schedule skips the weekend",
+ expression: "0 8 * * 1-5",
+ after: time.Date(2026, time.November, 6, 9, 0, 0, 0, time.UTC),
+ next: time.Date(2026, time.November, 9, 8, 0, 0, 0, time.UTC),
+ },
+ {
+ name: "the next time is after the given time",
+ expression: "0 8 * * *",
+ after: time.Date(2026, time.November, 6, 8, 0, 0, 0, time.UTC),
+ next: time.Date(2026, time.November, 7, 8, 0, 0, 0, time.UTC),
+ },
+ {
+ name: "every 5 minutes",
+ expression: "*/5 * * * *",
+ after: time.Date(2026, time.November, 6, 10, 3, 0, 0, time.UTC),
+ next: time.Date(2026, time.November, 6, 10, 5, 0, 0, time.UTC),
+ },
+ {
+ name: "day 31 skips the months with 30 days",
+ expression: "0 0 31 * *",
+ after: time.Date(2026, time.November, 1, 0, 0, 0, 0, time.UTC),
+ next: time.Date(2026, time.December, 31, 0, 0, 0, 0, time.UTC),
+ },
+ {
+ name: "the first day after the end of a year",
+ expression: "0 9 1 * *",
+ after: time.Date(2026, time.December, 31, 10, 0, 0, 0, time.UTC),
+ next: time.Date(2027, time.January, 1, 9, 0, 0, 0, time.UTC),
+ },
+ {
+ name: "February 29 waits for a leap year",
+ expression: "0 12 29 2 *",
+ after: time.Date(2026, time.March, 1, 0, 0, 0, 0, time.UTC),
+ next: time.Date(2028, time.February, 29, 12, 0, 0, 0, time.UTC),
+ },
+ {
+ name: "weekday 7 is Sunday",
+ expression: "0 10 * * 7",
+ after: time.Date(2026, time.November, 6, 0, 0, 0, 0, time.UTC),
+ next: time.Date(2026, time.November, 8, 10, 0, 0, 0, time.UTC),
+ },
+ {
+ name: "a day and a weekday match either",
+ expression: "0 0 13 * 5",
+ after: time.Date(2026, time.November, 1, 0, 0, 0, 0, time.UTC),
+ next: time.Date(2026, time.November, 6, 0, 0, 0, 0, time.UTC),
+ },
+ {
+ name: "a day with a star and a weekday match both",
+ expression: "0 0 */2 * 5",
+ after: time.Date(2026, time.November, 1, 0, 0, 0, 0, time.UTC),
+ next: time.Date(2026, time.November, 13, 0, 0, 0, 0, time.UTC),
+ },
+ {
+ name: "a time in the skipped hour runs later by the skip",
+ expression: "30 2 * * *",
+ after: time.Date(2027, time.March, 14, 0, 0, 0, 0, newYork),
+ next: time.Date(2027, time.March, 14, 7, 30, 0, 0, time.UTC),
+ },
+ {
+ name: "the day after the skip runs at its time",
+ expression: "30 2 * * *",
+ after: time.Date(2027, time.March, 14, 7, 30, 0, 0, time.UTC).In(newYork),
+ next: time.Date(2027, time.March, 15, 6, 30, 0, 0, time.UTC),
+ },
+ {
+ name: "every 30 minutes goes from before the skip to after it",
+ expression: "*/30 * * * *",
+ after: time.Date(2027, time.March, 14, 6, 30, 0, 0, time.UTC).In(newYork),
+ next: time.Date(2027, time.March, 14, 7, 0, 0, 0, time.UTC),
+ },
+ {
+ name: "a time in the repeated hour runs at its first occurrence",
+ expression: "30 1 * * *",
+ after: time.Date(2026, time.November, 1, 0, 0, 0, 0, newYork),
+ next: time.Date(2026, time.November, 1, 5, 30, 0, 0, time.UTC),
+ },
+ {
+ name: "a time in the repeated hour runs once",
+ expression: "30 1 * * *",
+ after: time.Date(2026, time.November, 1, 5, 30, 0, 0, time.UTC).In(newYork),
+ next: time.Date(2026, time.November, 2, 6, 30, 0, 0, time.UTC),
+ },
+ {
+ name: "every 30 minutes does not repeat the repeated hour",
+ expression: "*/30 * * * *",
+ after: time.Date(2026, time.November, 1, 5, 30, 0, 0, time.UTC).In(newYork),
+ next: time.Date(2026, time.November, 1, 7, 0, 0, 0, time.UTC),
+ },
+ }
+
+ for _, tc := range testCases {
+ t.Run(tc.name, func(t *testing.T) {
+ cron, err := scheduleParseCron(tc.expression)
+ require.NoError(t, err)
+
+ next, found := cron.Next(tc.after)
+ require.True(t, found)
+ require.True(t, tc.next.Equal(next), "next is %s", next)
+ })
+ }
+}
+
+func TestScheduleWallTime(t *testing.T) {
+ newYork, err := time.LoadLocation("America/New_York")
+ require.NoError(t, err)
+
+ testCases := []struct {
+ name string
+ hour int
+ day int
+ time time.Time
+ }{
+ {
+ name: "a normal wall time",
+ hour: 9,
+ day: 1,
+ time: time.Date(2026, time.November, 1, 14, 0, 0, 0, time.UTC),
+ },
+ {
+ name: "a wall time in the repeated hour is its first occurrence",
+ hour: 1,
+ day: 1,
+ time: time.Date(2026, time.November, 1, 5, 0, 0, 0, time.UTC),
+ },
+ }
+
+ for _, tc := range testCases {
+ t.Run(tc.name, func(t *testing.T) {
+ got := scheduleWallTime(2026, time.November, tc.day, tc.hour, 0, newYork)
+ require.True(t, tc.time.Equal(got), "time is %s", got)
+ })
+ }
+}
projects / onechat / commitdiff