policy/rank.bend

cswap-bend-cli@0.1.0.0 · 298 lines · 41 definitions

1import Base
2import cswap-bend-cli@0.1.0.0/policy/types.bend as T
3import cswap-bend-cli@0.1.0.0/policy/usage.bend as U
4
5# Candidate ranking: recovery and reset times, eligibility, and the pickers
6# for each ranking family (headroom, weekly reset, recovery).
7
8# ------------------------------------------------ times, with None = inf
9
10# Measured candidates: any, all at or over the threshold, best headroom.
11type Meas is Data:
12  Meas{any: Bool, all: Bool, best: Nat}
13
14# What a tick selects with: the live slot, the bar, the least headroom a
15# target needs, the usage rows, the clock and the wanted models.
16type Sel is Data:
17  Sel{active: Nat, bar: Maybe<&2, Nat>, need: Nat, us: List<&2, T.Usage>, now: Nat, ms: List<&2, String>}
18
19def rec.within(+r: Maybe<&2, Nat>, +now: Nat) -> Bool:
20  match r:
21    case None{}:
22      False{}
23    case Some{t}:
24      Nat.is_le(Nat.sub(t, now), 14400n)
25
26# c >= a - 300 s (the recovery hysteresis), with inf for None.
27def rec.ge_minus(+c: Maybe<&2, Nat>, +a: Maybe<&2, Nat>) -> Bool:
28  match c a:
29    case None{} _:
30      True{}
31    case Some{t} None{}:
32      False{}
33    case Some{t} Some{x}:
34      Nat.is_ge(Nat.add(t, 300n), x)
35
36def rec.lt_minus(+c: Maybe<&2, Nat>, +a: Maybe<&2, Nat>) -> Bool:
37  Bool.not(rec.ge_minus(c, a))
38
39def rec.req(+x: Maybe<&2, Nat>, +y: Maybe<&2, Nat>) -> Bool:
40  match x y:
41    case None{} None{}:
42      True{}
43    case None{} Some{b}:
44      False{}
45    case Some{a} None{}:
46      False{}
47    case Some{a} Some{b}:
48      Nat.is_eq(a, b)
49
50# x <= y.
51def rec.rle(+x: Maybe<&2, Nat>, +y: Maybe<&2, Nat>) -> Bool:
52  match x y:
53    case None{} None{}:
54      True{}
55    case None{} Some{b}:
56      False{}
57    case Some{a} None{}:
58      True{}
59    case Some{a} Some{b}:
60      Nat.is_le(a, b)
61
62def rec.min(+x: Maybe<&2, Nat>, +y: Maybe<&2, Nat>) -> Maybe<&2, Nat>:
63  match x y:
64    case None{} _:
65      y
66    case Some{a} None{}:
67      x
68    case Some{a} Some{b}:
69      Some{Nat.min(a, b)}
70
71def rec.after.at(+ok: Bool, +t: Nat) -> Maybe<&2, Nat>:
72  match ok:
73    case True{}:
74      Some{t}
75    case False{}:
76      None{}
77
78# A reset that is still ahead of us; past or unknown is inf.
79def rec.after(+r: Maybe<&2, Nat>, +now: Nat) -> Maybe<&2, Nat>:
80  match r:
81    case None{}:
82      None{}
83    case Some{t}:
84      rec.after.at(Nat.is_gt(t, now), t)
85
86# ----------------------------------------------- binding window recovery
87
88def win.pct(+w: T.Win) -> Nat:
89  match w:
90    case T.Win{p, r}:
91      p
92
93def win.bind.pick(+hit: Bool, +b: T.Win, +w: T.Win) -> Maybe<&2, T.Win>:
94  match hit:
95    case True{}:
96      Some{w}
97    case False{}:
98      Some{b}
99
100# The binding window: highest utilization, the first wins ties.
101def win.bind.step(+acc: Maybe<&2, T.Win>, +w: T.Win) -> Maybe<&2, T.Win>:
102  match acc:
103    case None{}:
104      Some{w}
105    case Some{b}:
106      win.bind.pick(Nat.is_gt(win.pct(w), win.pct(b)), b, w)
107
108def win.bind(+ws: List<&2, T.Win>, +acc: Maybe<&2, T.Win>) -> Maybe<&2, T.Win>:
109  match ws:
110    case Nil{}:
111      acc
112    case Con{w, t}:
113      win.bind(t, win.bind.step(acc, w))
114
115def bind.rec.of(+m: Maybe<&2, T.Win>, +now: Nat) -> Maybe<&2, Nat>:
116  match m:
117    case None{}:
118      None{}
119    case Some{w}:
120      match w:
121        case T.Win{p, r}:
122          rec.after(r, now)
123
124# When the binding window comes back; inf when unknown or already past.
125def bind.rec(+ws: List<&2, T.Win>, +now: Nat) -> Maybe<&2, Nat>:
126  bind.rec.of(win.bind(ws, None{}), now)
127
128def rec.row.at(+ok: Bool, +u: T.Usage, +now: Nat, +ms: List<&2, String>) -> Maybe<&2, Nat>:
129  match ok:
130    case True{}:
131      bind.rec(U.windows(u, ms), now)
132    case False{}:
133      None{}
134
135def rec.row(+m: Maybe<&2, T.Usage>, +now: Nat, +ms: List<&2, String>) -> Maybe<&2, Nat>:
136  match m:
137    case None{}:
138      None{}
139    case Some{u}:
140      rec.row.at(U.trusted(u, now, ms), u, now, ms)
141
142def usage.seven_reset(+u: T.Usage) -> Maybe<&2, Nat>:
143  match u:
144    case T.Usage{slot, five, fr, seven, sr, ss, fa, bo, er, nfl, np, pi, ad, hu, cu, se}:
145      sr
146
147def seven.row.at(+ok: Bool, +u: T.Usage, +now: Nat) -> Maybe<&2, Nat>:
148  match ok:
149    case True{}:
150      rec.after(usage.seven_reset(u), now)
151    case False{}:
152      None{}
153
154# The weekly reset consume-first ranks by; past is unknown.
155def seven.row(+m: Maybe<&2, T.Usage>, +now: Nat, +ms: List<&2, String>) -> Maybe<&2, Nat>:
156  match m:
157    case None{}:
158      None{}
159    case Some{u}:
160      seven.row.at(U.trusted(u, now, ms), u, now)
161
162# ------------------------------------------------------- the census
163
164def is_oauth(+k: T.AcctKind) -> Bool:
165  match k:
166    case T.ApiKey{}:
167      False{}
168    case o:
169      True{}
170
171def is_api(+k: T.AcctKind) -> Bool:
172  match k:
173    case T.ApiKey{}:
174      True{}
175    case o:
176      False{}
177
178# A switchable OAuth candidate: not disabled, not the live slot.
179def isc(+a: T.Account, +active: Nat) -> Bool:
180  match a:
181    case T.Account{slot, email, kind, disabled}:
182      is_oauth(kind) && Bool.not(disabled) && Bool.not(Nat.is_eq(slot, active))
183
184# A last-resort API-key candidate.
185def isapi(+a: T.Account, +active: Nat) -> Bool:
186  match a:
187    case T.Account{slot, email, kind, disabled}:
188      is_api(kind) && Bool.not(disabled) && Bool.not(Nat.is_eq(slot, active))
189
190def above.thr(+h: Nat, +thr: Nat) -> Bool:
191  Nat.is_ge(Nat.sub(T.full(), h), thr)
192
193def meas.step(+m: Meas, +h: Maybe<&2, Nat>, +thr: Nat) -> Meas:
194  match m:
195    case Meas{any, all, best}:
196      match h:
197        case None{}:
198          m
199        case Some{x}:
200          Meas{True{}, all && above.thr(x, thr), Nat.max(best, x)}
201
202def meas.acct(+ok: Bool, +h: Maybe<&2, Nat>, +thr: Nat, +m: Meas) -> Meas:
203  match ok:
204    case True{}:
205      meas.step(m, h, thr)
206    case False{}:
207      m
208
209def meas(+as: List<&2, T.Account>, +active: Nat, +us: List<&2, T.Usage>, +now: Nat, +ms: List<&2, String>, +thr: Nat, +m: Meas) -> Meas:
210  match as:
211    case Nil{}:
212      m
213    case Con{a, t}:
214      meas(t, active, us, now, ms, thr, meas.acct(isc(a, active), U.head.row(U.usage.of(U.account.slot(a), us), now, ms), thr, m))
215
216# Is the active account and every measured candidate at or over the threshold?
217def all_above(+m: Meas, +ah: Maybe<&2, Nat>, +thr: Nat) -> Bool:
218  match m:
219    case Meas{any, all, best}:
220      match ah:
221        case None{}:
222          False{}
223        case Some{a}:
224          above.thr(a, thr) && any && all
225
226# --------------------------------------------------------- eligibility
227
228def barred(+bar: Maybe<&2, Nat>, +slot: Nat) -> Bool:
229  match bar:
230    case None{}:
231      False{}
232    case Some{b}:
233      Nat.is_eq(b, slot)
234
235# A candidate that may be chosen: OAuth, enabled, not live, not barred.
236def target.base(+a: T.Account, +active: Nat, +bar: Maybe<&2, Nat>) -> Bool:
237  match a:
238    case T.Account{slot, email, kind, disabled}:
239      is_oauth(kind) && Bool.not(disabled) && Bool.not(Nat.is_eq(slot, active)) && Bool.not(barred(bar, slot))
240
241def elig.pos.at(+x: Nat) -> Maybe<&2, Nat>:
242  match x:
243    case 0n:
244      None{}
245    case 1n+p:
246      Some{x}
247
248def elig.pos(+h: Maybe<&2, Nat>) -> Maybe<&2, Nat>:
249  match h:
250    case None{}:
251      None{}
252    case Some{x}:
253      elig.pos.at(x)
254
255# A usable reading for a candidate: a row with a trusted headroom above zero.
256# Backoff is not a condition: it throttles polling, not trust.
257def elig.row(+m: Maybe<&2, T.Usage>, +now: Nat, +ms: List<&2, String>) -> Maybe<&2, Nat>:
258  match m:
259    case None{}:
260      None{}
261    case Some{u}:
262      elig.pos(U.headroom(u, now, ms))
263
264def sel.ok(+b: Bool, +m: Maybe<&2, T.Usage>, +now: Nat, +ms: List<&2, String>) -> Maybe<&2, Nat>:
265  match b:
266    case True{}:
267      elig.row(m, now, ms)
268    case False{}:
269      None{}
270
271# The headroom of a candidate that may be chosen, or None.
272def elig(+a: T.Account, +s: Sel) -> Maybe<&2, Nat>:
273  match s:
274    case Sel{active, bar, need, us, now, ms}:
275      sel.ok(target.base(a, active, bar), U.usage.of(U.account.slot(a), us), now, ms)
276
277def sel.need(+s: Sel) -> Nat:
278  match s:
279    case Sel{active, bar, need, us, now, ms}:
280      need
281
282def cand.gate.at(+ok: Bool, +h: Nat) -> Maybe<&2, Nat>:
283  match ok:
284    case True{}:
285      Some{h}
286    case False{}:
287      None{}
288
289def cand.gate(+m: Maybe<&2, Nat>, +need: Nat) -> Maybe<&2, Nat>:
290  match m:
291    case None{}:
292      None{}
293    case Some{h}:
294      cand.gate.at(Nat.is_ge(h, need), h)
295
296# A candidate that also clears the headroom gate (landing and hysteresis).
297def cand(+a: T.Account, +s: Sel) -> Maybe<&2, Nat>:
298  cand.gate(elig(a, s), sel.need(s))