Parse cron expressions and find the next time

The schedules of the agent repeat by a five-field cron expression, so
OneChat parses one with a small parser and no new dependency. A field is
a comma list of *, N, and N-M, where * and N-M can have a step. When
both day fields are restricted, a day matches when either one matches,
as in classic cron. The parser refuses names, macros, the characters ? L
W #, a seconds field, N/S, values out of range, and an expression that
matches no day in 8 years, each with an error that names the problem.

It also refuses an expression whose runs can be less than 5 minutes
apart, also across the end of an hour and across midnight. Each run is a
full turn, so a run every minute would use the weekly quota in hours.
The error gives the limit, so that the agent can ask the user.

The next time is the first matching wall time in the local zone. 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.

Issue: 60e4e4f

diff --git a/schedule_cron.go b/schedule_cron.go
new file mode 100644 (file)
index 0000000..78ec90b
--- /dev/null
+++ b/schedule_cron.go
@@ -0,0 +1,300 @@
+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
+}

diff --git a/schedule_cron_test.go b/schedule_cron_test.go
new file mode 100644 (file)
index 0000000..cd59a4c
--- /dev/null
+++ b/schedule_cron_test.go
@@ -0,0 +1,336 @@
+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)
+               })
+       }
+}