Cron expression evaluator
I needed to support “cron expressions” for a project. The aim was to allow the user to quickly enter familiar cron expressions to configure scheduling for some tasks.
I followed the POSIX crontab specification in order to maximize familiarity for the user. I will reproduce the relevant section below.
In the POSIX locale, the user or application shall ensure that a crontab entry is a text file consisting of lines of six fields each. The fields shall be separated by <blank> characters. The first five fields shall be integer patterns that specify the following:
- Minute [0,59]
- Hour [0,23]
- Day of the month [1,31]
- Month of the year [1,12]
- Day of the week ([0,6] with 0=Sunday)
Each of these patterns can be either an <asterisk> (meaning all valid values), an element, or a list of elements separated by <comma> characters.
An element shall be either a number or two numbers separated by a <hyphen-minus> (meaning an inclusive range).
The specification of days can be made by two fields (day of the month and day of the week).
If month, day of month, and day of week are all <asterisk> characters, every day shall be matched.
If either the month or day of month is specified as an element or list, but the day of week is an <asterisk>, the month and day of month fields shall specify the days that match.
If both month and day of month are specified as an <asterisk>, but day of week is an element or list, then only the specified days of the week match.
Finally, if either the month or day of month is specified as an element or list, and the day of week is also specified as an element or list, then any day matching either the month and day of month, or the day of week, shall be matched.
You can find the full spec page here.
I tackled this problem by first making a “slow” evaluation function that follows these rules as written. This ensures that we have a solid base that is likely to be correct.
This slow evaluation function was made to work for a single field (such as minutes, hours, etc.). It just reads each field of the expression, and turns it into a 64-bit bitmap of the numbers that match that expression.
Using 64-bit integers fits really well for this problem, because all the units that we care about (minute, hour, day, month, day of week) are less than 64. Afterwards, the 5 64-bit integers are stored and used for quickly evaluating a given
DateTime for a cron expression. This means the “compiled” version of a cron expression only takes 40 bytes of memory, not too bad.
Even in C#, iterating over every minute of a year and matching against the cron expression like this only takes 3 ms. This is more than fast enough for my purposes.