1// SPDX-License-Identifier: AGPL-3.0-or-later
2
3package domain
4
5import (
6 "slices"
7 "strconv"
8 "unicode"
9 "unicode/utf16"
10)
11
12// CIConcurrencyState is where a run or a job is in its concurrency group.
13type CIConcurrencyState string
14
15// Concurrency states.
16const (
17 // CIConcurrencyIdle: the group is evaluated but the entry has not asked for
18 // its turn yet.
19 CIConcurrencyIdle CIConcurrencyState = ""
20 // CIConcurrencyPending: the group record names this entry as a waiting
21 // one, behind the running entry.
22 CIConcurrencyPending CIConcurrencyState = "pending"
23 // CIConcurrencyHolding: this entry is the running one of its group.
24 CIConcurrencyHolding CIConcurrencyState = "holding"
25 // CIConcurrencyReplaced: only in a mark. A newer entry replaced this one:
26 // it is owed a cancellation and never acquires the group.
27 CIConcurrencyReplaced CIConcurrencyState = "replaced"
28 // CIConcurrencyRejected: only in a mark. A queue: max entry that arrived
29 // while CIMaxConcurrencyQueue entries were waiting: like a replaced entry it
30 // is owed a cancellation and never acquires the group, but its annotation is
31 // ConcurrencyQueueFullMessage.
32 CIConcurrencyRejected CIConcurrencyState = "rejected"
33)
34
35// Owed reports whether a mark in this state is owed a cancellation: the entry
36// was replaced or rejected, and never acquires its group.
37func (s CIConcurrencyState) Owed() bool {
38 return s == CIConcurrencyReplaced || s == CIConcurrencyRejected
39}
40
41// CIMaxConcurrencyGroup is the longest concurrency group name GitHub accepts
42// (actions/runner WorkflowTemplateConverter.cs:679-687, "must be less than 400
43// characters").
44const CIMaxConcurrencyGroup = 400
45
46// CIMaxConcurrencyQueue is how many entries may wait in a group with queue: max
47// (docs.github.com, data/reusables/actions/actions-group-concurrency.md: "Up to
48// 100 jobs or workflow runs can be pending in the concurrency group. When the
49// queue is full, any additional jobs or workflow runs are canceled."; the limits
50// page: "up to 100 jobs or workflow runs can be queued per concurrency group").
51const CIMaxConcurrencyQueue = 100
52
53// CIConcurrency is the evaluated "concurrency:" of a run (workflow level) or of
54// a job.
55type CIConcurrency struct {
56 // Group is the evaluated group as written; "" for none. Groups are compared
57 // without regard to case (ConcurrencyKey).
58 Group string
59 // Cancel is the evaluated cancel-in-progress.
60 Cancel bool
61 // Max is set for queue: max (the default, queue: single, leaves it false).
62 Max bool
63 // State is written to the record of the entry only after the group record
64 // named it (acquire committed): an entry that waits in a group that does
65 // not name it any more was replaced, and is cancelled.
66 State CIConcurrencyState
67 // Evaluated is set once the expressions were evaluated, whatever the result
68 // (a run starts unevaluated, and a re-run evaluates again).
69 Evaluated bool
70 // FromRun is set on a job that shows the group of its run: the entry is the
71 // run's, the job holds nothing of its own.
72 FromRun bool
73 // Preempted is set when a newer entry of the group cancelled this one.
74 Preempted bool
75}
76
77// ConcurrencyKey is the identity of a group within a repository. GitHub compares
78// groups with .NET's OrdinalIgnoreCase, which compares strings upper-cased
79// character by character with the simple case mapping (OrdinalCasing in
80// dotnet/runtime, System.Private.CoreLib/src/System/Globalization/
81// OrdinalCasing.cs; the source was not available here, so this follows its
82// documented rule). A character that is not ASCII and whose upper case is ASCII
83// keeps itself: ı (U+0131) and ſ (U+017F) are neither I nor S. So σ, ς and Σ are
84// one letter, ı and İ are distinct from I, and i equals I. The key is upper
85// case and is never lowered back.
86func ConcurrencyKey(group string) string {
87 out := make([]rune, 0, len(group))
88 for _, r := range group {
89 if u := unicode.ToUpper(r); r <= unicode.MaxASCII || u > unicode.MaxASCII {
90 r = u
91 }
92 out = append(out, r)
93 }
94 return string(out)
95}
96
97// ConcurrencyGroupLength is the length of a group as C#'s String.Length counts
98// it: in UTF-16 code units.
99func ConcurrencyGroupLength(group string) int { return len(utf16.Encode([]rune(group))) }
100
101// ConcurrencyCancelMessage is GitHub's annotation for an entry cancelled by a
102// newer one (docs.github.com, "Control the concurrency of workflows and jobs").
103func ConcurrencyCancelMessage(group string) string {
104 return "Canceling since a higher priority waiting request for '" + group + "' exists"
105}
106
107// ConcurrencyQueueFullMessage is the annotation of a queue: max entry cancelled
108// because CIMaxConcurrencyQueue entries already wait in its group. GitHub's text
109// is not documented: this one is ermite's.
110func ConcurrencyQueueFullMessage(group string) string {
111 return "Canceling since the concurrency group '" + group + "' already has " + strconv.Itoa(CIMaxConcurrencyQueue) + " waiting requests"
112}
113
114// CIConcurrencyEntry is a run (JobID empty) or a job waiting for or holding a
115// concurrency group.
116type CIConcurrencyEntry struct {
117 RunID int64
118 Attempt int32
119 JobID string
120 // Cancel is the cancel-in-progress of the entry: while it waits, the
121 // running entry of the group is cancelled.
122 Cancel bool
123 // Canceling is set on a running entry that a waiting entry with
124 // cancel-in-progress asked to stop; it stays named until it has ended, and
125 // the reconciliation asks it again.
126 Canceling bool
127 // Max is the queue mode of the entry: queue: max when set, else single.
128 Max bool
129}
130
131// Key identifies the entry in the marks of its group.
132func (e CIConcurrencyEntry) Key() string {
133 return strconv.FormatInt(e.RunID, 10) + "/" + strconv.FormatInt(int64(e.Attempt), 10) + "/" + e.JobID
134}
135
136// Same reports whether two entries are the same run or job.
137func (e CIConcurrencyEntry) Same(o CIConcurrencyEntry) bool {
138 return e.RunID == o.RunID && e.Attempt == o.Attempt && e.JobID == o.JobID
139}
140
141// CIConcurrencyRecord is the state of a group: at most one running entry, and
142// the waiting entries in the order they started waiting (first in, first out).
143//
144// GitHub documents each queue mode alone; a group that mixes them follows
145// ermite's rules (Enqueue): a queue: single entry that starts waiting cancels
146// and replaces every waiting entry, whatever their mode, and is then the only
147// one; a queue: max entry joins the end of the line, or is rejected when
148// CIMaxConcurrencyQueue entries already wait. When the running entry leaves,
149// the head of the line takes its place (Promote); a waiting entry that leaves
150// keeps the order of the others.
151type CIConcurrencyRecord struct {
152 Running *CIConcurrencyEntry
153 Pending []CIConcurrencyEntry
154}
155
156// IsEmpty reports whether nothing runs or waits in the group.
157func (r CIConcurrencyRecord) IsEmpty() bool { return r.Running == nil && len(r.Pending) == 0 }
158
159// Names reports whether the record names the entry as the running or a pending
160// one.
161func (r CIConcurrencyRecord) Names(e CIConcurrencyEntry) bool {
162 return (r.Running != nil && r.Running.Same(e)) || r.PendingIndex(e) >= 0
163}
164
165// PendingIndex is the place of the entry in the waiting line, -1 if it does not
166// wait.
167func (r CIConcurrencyRecord) PendingIndex(e CIConcurrencyEntry) int {
168 for i, p := range r.Pending {
169 if p.Same(e) {
170 return i
171 }
172 }
173 return -1
174}
175
176// RemovePending takes the entry out of the waiting line, keeping the order of
177// the others, and reports whether it was there.
178func (r *CIConcurrencyRecord) RemovePending(e CIConcurrencyEntry) bool {
179 i := r.PendingIndex(e)
180 if i < 0 {
181 return false
182 }
183 r.Pending = append(r.Pending[:i:i], r.Pending[i+1:]...)
184 if len(r.Pending) == 0 {
185 r.Pending = nil
186 }
187 return true
188}
189
190// Enqueue puts a new entry, which neither runs nor waits, in the waiting line.
191// A queue: single entry replaces every waiting entry (returned, in line order)
192// and is then the only one; a queue: max entry is appended, unless limit
193// entries already wait: then the record is left as it is and rejected is set.
194func (r *CIConcurrencyRecord) Enqueue(e CIConcurrencyEntry, limit int) (replaced []CIConcurrencyEntry, rejected bool) {
195 if !e.Max {
196 replaced = r.Pending
197 r.Pending = []CIConcurrencyEntry{e}
198 return replaced, false
199 }
200 if len(r.Pending) >= limit {
201 return nil, true
202 }
203 r.Pending = append(r.Pending, e)
204 return nil, false
205}
206
207// Promote gives the free running place to the head of the waiting line, and
208// returns it (nil when the place is taken or nobody waits).
209func (r *CIConcurrencyRecord) Promote() *CIConcurrencyEntry {
210 if r.Running != nil || len(r.Pending) == 0 {
211 return nil
212 }
213 head := r.Pending[0]
214 r.Pending = r.Pending[1:]
215 if len(r.Pending) == 0 {
216 r.Pending = nil
217 }
218 r.Running = &head
219 return r.Running
220}
221
222// Clone is a copy of the record that shares nothing with it.
223func (r CIConcurrencyRecord) Clone() CIConcurrencyRecord {
224 out := CIConcurrencyRecord{Pending: slices.Clone(r.Pending)}
225 if r.Running != nil {
226 e := *r.Running
227 out.Running = &e
228 }
229 return out
230}
231
232// CIConcurrencyMark says where an entry stands in its group. The marks of a group
233// are written in the same batch as its record: an entry is marked pending or
234// holding if and only if the record names it as a pending or the running
235// entry, an entry that a newer one replaced is marked replaced in the batch
236// that unnames it, and a queue: max entry that found the line full is marked
237// rejected in the batch that refused it. So a replaced entry is found from the marks alone, whatever
238// failed after that batch.
239type CIConcurrencyMark struct {
240 Entry CIConcurrencyEntry
241 // Group is the group as the newest request wrote it (the cancel annotation
242 // names it).
243 Group string
244 State CIConcurrencyState
245}
246
247// CIConcurrencyGroupState is a group as one transaction sees it: its record and
248// the marks of the entries that belong to it, by CIConcurrencyEntry.Key.
249type CIConcurrencyGroupState struct {
250 Record CIConcurrencyRecord
251 Marks map[string]CIConcurrencyMark
252}
253
254// IsEmpty reports whether the group has no entry and no mark left.
255func (s CIConcurrencyGroupState) IsEmpty() bool { return s.Record.IsEmpty() && len(s.Marks) == 0 }