| 1 | package calendar |
| 2 | |
| 3 | import ( |
| 4 | "strings" |
| 5 | "time" |
| 6 | ) |
| 7 | |
| 8 | // MaxOccurrencesPerSeries caps what one master may contribute to one |
| 9 | // request. A forever-daily series asked for a decade would otherwise |
| 10 | // expand three and a half thousand occurrences into a month view |
| 11 | // nobody can read. |
| 12 | // |
| 13 | // A cap rather than a refusal: the window is what bounds a normal |
| 14 | // request, and this only catches the pathological one. |
| 15 | const MaxOccurrencesPerSeries = 1000 |
| 16 | |
| 17 | // Occurrence is one instance of a series, in the series' own zone. |
| 18 | type Occurrence struct { |
| 19 | // Local is the occurrence's ORIGINAL local start — the key an |
| 20 | // override is written against, and never its moved time. |
| 21 | Local string |
| 22 | |
| 23 | StartUTC int64 |
| 24 | EndUTC int64 |
| 25 | } |
| 26 | |
| 27 | // Expand yields a series' occurrences overlapping the half-open UTC |
| 28 | // window [from, to). |
| 29 | // |
| 30 | // It iterates in WALL CLOCK, not in UTC, and that is the whole reason |
| 31 | // this is hand-written. A 09:00 daily standup is at 09:00 on both sides |
| 32 | // of a DST boundary; stepping the UTC instant by 24 hours would move it |
| 33 | // to 08:00 or 10:00 for half the year. Each occurrence's date is |
| 34 | // computed in the local calendar and only then converted. |
| 35 | // |
| 36 | // The rules that calendars get wrong, and which this follows: |
| 37 | // |
| 38 | // - COUNT counts GENERATED occurrences, including ones EXDATE later |
| 39 | // removes. Filtering first and counting second gives a series more |
| 40 | // occurrences than it was asked for. |
| 41 | // - A monthly BYMONTHDAY=31 SKIPS months with no 31st. It does not |
| 42 | // clamp to the 30th or the 28th — "the 31st" in a month without one |
| 43 | // is no occurrence at all. |
| 44 | // - Likewise a yearly rule on 29 February happens in leap years only, |
| 45 | // and the fifth Friday of a month happens only in months that have |
| 46 | // one. |
| 47 | func Expand(startLocal, endLocal, tz string, allDay bool, r Rule, exdates string, from, to int64) []Occurrence { |
| 48 | out, _ := ExpandComplete(startLocal, endLocal, tz, allDay, r, exdates, from, to) |
| 49 | return out |
| 50 | } |
| 51 | |
| 52 | // ExpandComplete is Expand plus the one fact Expand drops: whether the |
| 53 | // walk REACHED the window. It stops after 100,000 steps, and a series |
| 54 | // old enough to run out of steps first returns an ordinary slice with |
| 55 | // nothing in it — which reads as "nothing on" to a view, and would |
| 56 | // read as "free" to a booking page. Anything that decides free time |
| 57 | // asks this form and fails closed on false (booking spec §4.1, B23). |
| 58 | func ExpandComplete(startLocal, endLocal, tz string, allDay bool, r Rule, exdates string, from, to int64) ([]Occurrence, bool) { |
| 59 | if from >= to || !validExpansionRule(r) { |
| 60 | return nil, false |
| 61 | } |
| 62 | loc, err := Zone(tz) |
| 63 | if err != nil { |
| 64 | return nil, false |
| 65 | } |
| 66 | start, _, err := ParseLocal(startLocal, loc) |
| 67 | if err != nil { |
| 68 | return nil, false |
| 69 | } |
| 70 | end, _, err := ParseLocal(endLocal, loc) |
| 71 | validInput := err == nil && inDateHorizon(start) && inDateHorizon(end) && !end.Before(start) |
| 72 | if err != nil { |
| 73 | // An event with an unreadable end still has a start; treat it |
| 74 | // as instantaneous rather than dropping it entirely. |
| 75 | end = start |
| 76 | } |
| 77 | // The span in whole days plus the end's time of day, so both ends |
| 78 | // move together in wall clock and a DST boundary shifts neither. |
| 79 | dayspan := daysBetween(start, end) |
| 80 | |
| 81 | skip := exdateSet(exdates) |
| 82 | layout := LayoutLocal |
| 83 | if allDay { |
| 84 | layout = LayoutDate |
| 85 | } |
| 86 | |
| 87 | var out []Occurrence |
| 88 | generated := 0 |
| 89 | complete := false |
| 90 | uncertainWindow := false |
| 91 | for cur, i := start, 0; i < 100000; i++ { |
| 92 | if r.Count > 0 && generated >= r.Count { |
| 93 | complete = true |
| 94 | break |
| 95 | } |
| 96 | if r.HasUntil && cur.After(untilLocal(r, loc)) { |
| 97 | complete = true |
| 98 | break |
| 99 | } |
| 100 | occStart := cur |
| 101 | occEnd, endOK := shiftDays(cur, dayspan, end) |
| 102 | if !endOK { |
| 103 | break |
| 104 | } |
| 105 | |
| 106 | su := occStart.Unix() |
| 107 | eu := occEnd.Unix() |
| 108 | // Generated counts before EXDATE removes, per the RFC. |
| 109 | generated++ |
| 110 | |
| 111 | key := occStart.Format(layout) |
| 112 | if !skip[key] { |
| 113 | invalidSpan := end.After(start) && eu <= su |
| 114 | if invalidSpan && eu < to && su >= from { |
| 115 | // Reversed gap endpoints cannot establish free time between |
| 116 | // them. Keep walking for later dates without rendering this chip. |
| 117 | uncertainWindow = true |
| 118 | } |
| 119 | // Half-open overlap on both sides: an event that ends |
| 120 | // exactly at the window's start is not in the window. |
| 121 | if !invalidSpan && eu > from && su < to { |
| 122 | out = append(out, Occurrence{Local: key, StartUTC: su, EndUTC: eu}) |
| 123 | if len(out) >= MaxOccurrencesPerSeries { |
| 124 | // The window was reached, but not all of it was |
| 125 | // returned. For a view that is a bounded page; for |
| 126 | // anything deciding FREE time it is an incomplete |
| 127 | // answer, and says so. |
| 128 | break |
| 129 | } |
| 130 | } |
| 131 | } |
| 132 | // Past the window with nothing left that could come back. |
| 133 | if su >= to { |
| 134 | complete = true |
| 135 | break |
| 136 | } |
| 137 | |
| 138 | if r.Count > 0 && generated >= r.Count { |
| 139 | complete = true |
| 140 | break |
| 141 | } |
| 142 | next, state := advance(cur, start, r, loc) |
| 143 | if state != stepCandidate { |
| 144 | complete = state == stepExhausted |
| 145 | break |
| 146 | } |
| 147 | cur = next |
| 148 | } |
| 149 | return out, complete && validInput && !uncertainWindow |
| 150 | } |
| 151 | |
| 152 | // shiftDays puts proto's time of day onto a date dayspan days after cur. |
| 153 | func shiftDays(cur time.Time, dayspan int, proto time.Time) (time.Time, bool) { |
| 154 | next, state := candidateOnDay(civilDay(cur)+int64(dayspan), proto, cur.Location()) |
| 155 | return next, state == stepCandidate |
| 156 | } |
| 157 | |
| 158 | func untilLocal(r Rule, loc *time.Location) time.Time { |
| 159 | if r.UntilIsUTC { |
| 160 | return r.Until.In(loc) |
| 161 | } |
| 162 | return time.Date(r.Until.Year(), r.Until.Month(), r.Until.Day(), 23, 59, 59, 0, loc) |
| 163 | } |
| 164 | |
| 165 | func exdateSet(exdates string) map[string]bool { |
| 166 | set := map[string]bool{} |
| 167 | for _, d := range strings.Split(exdates, ",") { |
| 168 | if d = strings.TrimSpace(d); d != "" { |
| 169 | set[d] = true |
| 170 | } |
| 171 | } |
| 172 | return set |
| 173 | } |
| 174 | |
amadan