robfiig/cron ソースコード解析

Cron式

参考Wiki
https://en.wikipedia.org/wiki/Cron

robfiig/cron プロジェクト情報

ダウンロードアドレス

https://github.com/robfig/cron.git

ファイルディレクトリの説明

constantdelay.go # One of the simplest second-level timing systems. Not related to cron
constantdelay_test.go #test
cron.go #Cron system. Manage a series of cron timed jobs (Schedule Job)
cron_test.go #Test
doc.go #Documentation
LICENSE #Authorization 
parser.go #parser, parse cron format string city a specific timer (Schedule)
parser_test.go #test
README.md #README
spec.go #Single timer (Schedule) structure. How to calculate your next trigger time
spec_test.go #test

robfiig/cron 現在の実装要件

doc.go

CRON Expression Format
A cron expression represents a set of times, using 6 space-separated fields.
Field name | Mandatory? | Allowed values | Allowed special characters
---------- | ---------- | -------------- | --------------------------
Seconds | Yes | 0-59 | * / , -
Minutes | Yes | 0-59 | * / , -
Hours | Yes | 0-23 | * / , -
Day of month | Yes | 1-31 | * / , - ?
Month | Yes | 1-12 or JAN-DEC | * / , -
Day of week | Yes | 0-6 or SUN-SAT | * / , - ?
Predefined schedules

You may use one of several pre-defined schedules in place of a cron expression.

Entry | Description | Equivalent To
----- | ----------- | -------------
@yearly (or @annually) | Run once a year, midnight, Jan. 1st | 0 0 0 0 1 1 *
@monthly | Run once a month, midnight, first of month | 0 0 0 1 * *
@weekly | Run once a week, midnight on Sunday | 0 0 0 0 * * 0
@daily (or @midnight) | Run once a day, midnight | 0 0 0 0 * * *
@hourly | Run once an hour, beginning of hour | 0 0 * * * *

の実装がないことがわかります。 L , W , # これらは特殊文字です。この理由は、正確なコードが実装されたときに後述します。

cron式のパース

cronのBNF式とそのエリシテーションのためのパース方法

まず、EBNFを使ってcron式を定義してみます（あまり厳密ではありませんが・・・）。

<non_zero> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<num> ::= <non_zero> | "0"
<number> ::= <non_zero> {<num>} 
<normal_item> ::= "*" | <number> | <number> "-"<number> | <number> "/" <number >
<days_item> ::= <normal_item> | ""? " | <number>"L" | <number>"W" | <number>"#"
<item> ::= <normal_item> | <days_item>;
<items> ::= {<item>","} <item> ;
<cron> ::= <items>" "<items>" "<items>" "<items>" "<items>" "<items>" quot; "<items>

この時点で、もし私がcron式をパースするとしたら、以下のステップを踏むでしょう。

1. cron 空白を使用して、分離された items .
2. items を使用することで , を逆アセンブルします。 item .
3. item 網羅的なテストを使用する（以下のいずれか1つだけが合法である）。
   
   1. という文字は1つしかないのでしょうか？ * または ? .
   2. を使用することは可能ですか？ / または - 2つの数値に分解する。
   3. は、数字にプラス L または W エンディングです。
   4. 純粋な数字
4. ルールを一つずつ記述し、ルールの解析を完了させる

スタンドアロンルールの表現方法

cron式は一連の時間を表現するために使用され、時間はそれ自身の間隔、分、秒0〜59、時間0〜23、日/月0〜31、日/週0〜6、月0〜11を逃れることはできません。これらは基本的に点の集合、つまり整数の区間である。したがって、任意の整数区間について、cronのルールのいくつかを次のように記述することができます。

• * | ? 任意，区間内のすべての点に対応する。(さらに、day/weekとday/monthは互いに干渉しあうことに注意)。
• 特定の点に対応する純粋な数値。
• / 2つの数a , bの除算で、a + n * b (n >= 0 ) に一致する区間上のすべての点。
• - 分割された2つの数。この2つの数で決まる区間内のすべての点に対応する。
• L | W 特定の時間に特化する必要があり、区間内のポイントに一般化できない。

この時点で robfig/cron なぜ L | W その理由は明確です。この2つの規則を取り除くと、残りの規則は点の網羅的なリストを使って一般的な方法で表現することができる。最大の区間が60点しかないことを考えると uint64 整数の各ビットで点を表現するのが適切である。ここでは robfig/cron の表現です。

/* 
   ------------------------------------------------------------
   The 64th marker is arbitrary and is used for day/week and day/month interferences.
   63 - 0 for each point of the interval [63 , 0].
   ------------------------------------------------------------ 

   Assuming that the interval is 0 - 63, the following example is given. 

   For example, 0/3 is represented as follows. 
   * / ?       
   +--+--------------------------------------------------------+
   | 0 | 1 0 0 1 0 0 1 ~~ ~~ 1 0 0 1 0 0 1 |
   +--+--------------------------------------------------------+   
        63 ~ ~ ~~ 0 

   For example, 2-5 is represented as follows. 
   * / ?       
   +--+--------------------------------------------------------+
   | 0 | 0 0 0 0 0 ~ ~ ~~ ~ 0 0 0 0 1 1 1 1 1 0 0 |
   +--+--------------------------------------------------------+   
        63 ~ ~ ~~ 0 

  For example, * is represented as follows. 
   * / ?       
   +--+--------------------------------------------------------+
   | 1 | 1 1 1 1 1 1 ~ ~ ~ 1 1 1 1 1 1 1 1 1 1 1 1 |
   +--+--------------------------------------------------------+   
        63 ~ ~ ~~ 0 
*/

タイマーの基本機能

時刻がルールに合っているか

ルールがあれば、ある時点がルールに合致するかどうかは、対応するビットが1であるかどうかで判断できる。

ルールにマッチする次の時間を事前に決定する

ある時刻が与えられたとき、そのルールに合致する次の時刻を見つけるのも簡単です。

• 各フィールドの次に対象となる値を、大きいものから順に探す。
• 各時間フィールドを順番に、条件を満たすかどうかを判断するために1つずつ追加します。

このトラバーサルは間隔が狭いので非常に効率的ですが、ずっと下を見ないように注意してください。最も悲観的なケースは、うるう年の2月29日でしょう。5年以上先の探索は不正な表現ということになります。

robfiig/cron ソースコード解析

以上の説明を具体的なコードに置き換えてみましょう。

基本的なデータ構造

#cronのルールを表す構造体

spec.go

// Each time field is a uint64
type SpecSchedule struct {
    Second, Minute, Hour, Dom, Month, Dow uint64
}
// For 64-bit arbitrary identifiers
const (
    // Set the top bit if a star was included in the expression.
    starBit = 1 << 63
)

各タイムフィールドのインターバル、名前

spec.go

type bounds struct {
    min, max uint
    names map[string]uint
}



// The bounds for each field.
var (
    seconds = bounds{0, 59, nil}
    minutes = bounds{0, 59, nil}
    hours = bounds{0, 23, nil}
    dom = bounds{1, 31, nil}
    months = bounds{1, 12, map[string]uint{
        "jan": 1,
        "feb": 2,
        "mar": 3,
        "apr": 4,
        "may": 5,
        "jun": 6,
        "jul": 7,
        "aug": 8,
        "sep": 9,
        "oct": 10,
        "nov": 11,
        "dec": 12,
    }}
    dow = bounds{0, 6, map[string]uint{
        "sun": 0,
        "mon": 1,
        "tue": 2,
        "wed": 3,
        "thu": 4,
        "fri": 5,
        "sat": 6,
    }}
)

という文字列をパースします。

SpecSchedule

parser.go

package cron

import (
    "fmt"
    "log"
    "math"
    "strconv"
    "strings"
    "time"
)

// Parse the string into SpecSchedule . SpecSchedule conforms to the Schedule interface
func Parse(spec string) (_ Schedule, err error) {
    // Process the panic . Do not let the idiom crash. Instead, output it as an error
    defer func() {
        if recovered := recover(); recovered ! = nil {
            err = fmt.Errorf("%v", recovered)
        }
    }()
    // handle special special strings directly. 
    if spec[0] == '@' {
        return parseDescriptor(spec), nil
    }

    // cron uses whitespace to disassemble separate items. 
    fields := strings.Fields(spec)
    if len(fields) ! = 5 && len(fields) ! = 6 {
 
    // Parse each item by rule
    schedule := &SpecSchedule{
        Second: getField(fields[0], seconds),
        Minute: getField(fields[1], minutes),
        Hour: getField(fields[2], hours),
        Dom: getField(fields[3], dom),
        Month: getField(fields[4], months),
        Dow: getField(fields[5], dow),
    }

    return schedule, nil
}

// Parse items.
func getField(field string, r bounds) uint64 {
    var bits uint64
    // Items are broken out using ",".
    ranges := strings.FieldsFunc(field, func(r rune) bool { return r == ',' })
    for _, expr := range ranges {
        // use the exhaustive method to detect each one
        bits |= getRange(expr, r)
    }
    return bits
}


// use the exhaustive method to detect each one
func getRange(expr string, r bounds) uint64 {

    var (
        start, end, step uint
        rangeAndStep = strings.Split(expr, "/")
        lowAndHigh = strings.Split(rangeAndStep[0], "-")
        singleDigit = len(lowAndHigh) == 1
    )

    var extra_star uint64
    // Is there only one character that is * or ? 
    if lowAndHigh[0] == "*" || lowAndHigh[0] == "? " {
        start = r.min
        end = r.max
        extra_star = starBit
    } else {
        //can "-" be broken into two numbers 
        start = parseIntOrName(lowAndHigh[0], r.names)
        switch len(lowAndHigh) {
        case 1:
            end = start
        case 2:
            end = parseIntOrName(lowAndHigh[1], r.names)
        default:
            log.Panicf("Too many hyphens: %s", expr)
        }
    }
    //can "/" be decomposed into two numbers 
    switch len(rangeAndStep) {
    case 1:
        step = 1
    case 2:
        step = mustParseInt(rangeAndStep[1])

        // Special handling: "N/step" means "N-max/step".
        if singleDigit {
            end = r.max
        }
    default:
        log.Panicf("Too many slashes: %s", expr)
    }
    // Convert to points . 
    if start < r.min {
        log.Panicf("Beginning of range (%d) below minimum (%d): %s", start, r.min, expr)
    }
    if end > r.max {
        log.Panicf("End of range (%d) above maximum (%d): %s", end, r.max, expr)
    }
    if start > end {
        log.Panicf("Beginning of range (%d) beyond end of range (%d): %s", start, end, expr)
    }

    return getBits(start, end, step) | extra_star
}

// Helper function . Parse a predefined name or number
func parseIntOrName(expr string, names map[string]uint) uint {
    if names ! = nil {
        if namedInt, ok := names[strings.ToLower(expr)]; ok {
            return namedInt
        }
    }
    return mustParseInt(expr)
}

// helper functions . String - Number
func mustParseInt(expr string) uint {
    num, err := strconv.Atoi(expr)
    if err ! = nil {
        log.Panicf("Failed to parse int from %s: %s", expr, err)
    }
    if num < 0 {
        log.Panicf("Negative number (%d) not allowed: %s", num, expr)
    }

    return uint(num)
}

// helper function to set each point specifically
func getBits(min, max, step uint) uint64 {
    var bits uint64

    // If step is 1, use shifts.
    if step == 1 {
        return ^(math.MaxUint64 << (max + 1)) & (math.MaxUint64 << min)
    }

    // Else, use a simple loop.
    for i := min; i <= max; i += step {
        bits |= 1 << i
    }
    return bits
}

// Helper function . Set the points of the interval + arbitrary flags
func all(r bounds) uint64 {
    return getBits(r.min, r.max, 1) | starBit
}

// Parse the predefined names
func parseDescriptor(spec string) Schedule {
    switch spec {
    case "@yearly", "@annually":
        return &SpecSchedule{
            Second: 1 << seconds.min,
            Minute: 1 << min

次にそのルールに合致したときを事前に判断する

spec.go

func (s *SpecSchedule) Next(t time.Time) time.Time {
    // Rounding at the second level
    t = t.Add(1*time.Second - time.Duration(t.Nanosecond())*time.Nanosecond)

    // Determine if a field is added or not, if so, then the field at the next level needs to be zeroed.
    added := false

    // The future is not explored more than 5 years into the future
    yearLimit := t.Year() + 5
    // the next level of the field accumulation to reset, need to re-accumulate plus a level of the field when the goto point
    // For example, if you want to find the 31st of each month, April matches the month field, but there is no 31st in April. After traversing every day of April, you can only request to re-accumulate the month.
WRAP:
    if t.Year() > yearLimit {
        return time.Time{}
    }
    // month
    for 1<<uint(t.Month())& s.Month == 0 {
        // If we have to add a month, reset the other parts to 0.
        if !added {
            added = true
            // Otherwise, set the date at the beginning (since the current time is irrelevant).
            t = time.Date(t.Year(), t.Month(), 1, 0, 0, 0, 0, 0, 0, t.Location())
        }
        t = t.AddDate(0, 1, 0)

        // Wrapped around.
        if t.Month() == time.January {
            goto WRAP
        }
    }

    // Days, handling days/month and days/week at a time
    for !dayMatches(s, t) {
        if !added {
            added = true
            t = time.Date(t.Year(), t.Month(), t.Day(), 0, 0, 0, 0, 0, t.Location())
        }
        t = t.AddDate(0, 0, 1)

        if t.Day() == 1 {
            goto WRAP
        }
    }
    // time
    for 1<<uint(t.Hour())&s.Hour == 0 {
        if !added {
            added = true
            t = t.Truncate(time.Hour)
        }
        t = t.Add(1 * time.Hour)

        if t.Hour() == 0 {
            goto WRAP
        }
    }
    // divide
    for 1<<uint(t.Minute())&s.Minute == 0 {
        if !added {
            added = true
            t = t.Truncate(time.Minute)
        }
        t = t.Add(1 * time.Minute)

        if t.Minute() == 0 {
            goto WRAP
        }
    }
    // seconds
    for 1<<uint(t.Second())&s.Second == 0 {
        if !added {
            added = true
            t = t.Truncate(time.Second)
        }
        t = t.Add(1 * time.Second)

        if t.Second() == 0 {
            goto WRAP
        }
    }

    return t
}
// Process both days/month and days/week at once. If any of the two are present, then both must match the other to be considered a match
func dayMatches(s *SpecSchedule, t time.Time) bool {
    var (
        domMatch bool = 1<<uint(t.Day())&s.Dom > 0
        dowMatch bool = 1<<uint(t.Weekday())&s.Dow > 0
    )

    if s.Dom&starBit > 0 || s.Dow&starBit > 0 {
        return domMatch && dowMatch
    }
    return domMatch || dowMatch
}

時限タスク管理クラス cron.go

これはもうcronの話ではなく、安定した、メンテナンス可能な、使いやすい時間指定タスク管理クラスを実行する方法についての話です。

タイマーの抽象化

cron.go

type Schedule interface {
    //Given a time, give the next execution time
    Next(time.Time) time.Time
}

タスクの抽象化

cron.go

type Job interface {
    Run()
}

タイマタスク

cron.go

type Entry struct {
    // , timer
    Schedule Schedule
    // Next execution time
    Next time.
    // last execution time
    Prev time.
    // Task
    Job Job
Job }

マネージャー

cron.go

type Cron struct {
    entries []*Entry // Tasks
    stop chan struct {} // The way to call stop
    add chan *Entry // The way to add a new task
    snapshot chan []*Entry // A way to request a snapshot of a task
    running bool // Whether it is running or not
    ErrorLog *log.Logger // Error log
}

// Start and end all tasks
func (c *Cron) Start() {
    c.running = true
    go c.running()
}
func (c *Cron) Stop() {
    if !c.running {
        return
    }
    c.stop <- struct{}{}
    c.running = false
}

//running interface
func (c *Cron) run() {
    // Figure out the next activation times for each entry.
    Now := time.Now().Local()
    for _, entry := range c.entries {
        entry.Next = entry.Schedule.Next(now)
    }
    // infinite loop
    for {
        // Determine which tasks are next to be executed by sorting on the next execution time, preventing them from being at the front of the queue
        sort.Sort(byTime(c.entries)) 

        var effective time.Time
        if len(c.entries) == 0 || c.entries[0].Next.IsZero() {
            // If there are no entries yet, just sleep - it still handles new entries
            // and stop requests.
            effective = now.AddDate(10, 0, 0)
        } else {
            effective = c.entries[0].Next
        Next}

        select {
        case now = <-time.After(effective.Sub(now)):
            // Run the task that needs to be executed
            for _, e := range c.entries {
                if e.Next ! = effective {
                    break
                }
                go c.runWithRecovery(e.Job)
                e.Prev = e.Next
                e.Next = e.Schedule.Next(effective)
            }
            continue

        case newEntry := <-c.add: //add new task
            c.entries = append(c.entries, newEntry)
            newEntry.Next = newEntry.Schedule.Next(time.Now().Local())

        case <-c.snapshot: // Get snapshot while running
            c.snapshot <- c.entrySnapshot()

        case <-c.stop: // stop
            return
        }

        // 'now' should be updated after newEntry and snapshot cases.
        now = time.Now().Local()
    }
}
// Helper functions. Handle panic, single-task panic does not cause global crashes
func (c *Cron) runWithRecovery(j Job) {
    defer func() {
        if r := recover(); r ! = nil {
            const size = 64 << 10
            buf := make([]byte, size)
            buf = buf[:runtime.Stack(buf, false)]
            c.logf("cron: panic running job: %v\n%s", r, buf)
        }
    }()
    j.Run()
}

// Sorting helper class. Support len swap less 
type byTime []*Entry

func (s byTime) Len() int { return len(s) }
func (s byTime) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s byTime) Less(i, j int) bool {
    // Two zero times should return false.
    // Otherwise, zero is "greater" than any other time.
    // (To sort it at the end of the list.)
    if s[i].Next.IsZero() {
        return false
    }
    If s[j].Next.IsZero() {
        return true
    }
    return s[i].Next.Before(s[j].Next)
}

それ以外の些細なインターフェースは説明しないので、自分でcronタイマータスクのサポートライブラリを書けばいいと思います。