1	# Cache validity: expiry, negative results, invalidation, and generation-safe fetch completion. Source: https://github.com/paymog/bend-kit/tree/main/cache
2	import Base
3	import bend-kit-collections@0.1.2.0/omap.bend as OMap
4	
5	# How long a result stays fresh, in the units of the caller's clock.
6	type Policy is Data:
7	  Policy{ttl: Nat, negative_ttl: Nat}
8	
9	# What one fetch found upstream: a value at an upstream version, or nothing.
10	type Found<-V: Data> is Data:
11	  Found{version: Nat, value: V}
12	  Missing{}
13	
14	# A cached result. It serves a read at `now` only while now < expires.
15	type Entry<-V: Data> is Data:
16	  Hit{version: Nat, value: V, expires: Nat}
17	  Miss{expires: Nat}
18	
19	# The state of one key. Fetches take the generations floor, floor+1, ..., next-1.
20	# A completion lands only when floor <= its generation < next. It then raises
21	# floor past its generation, so no older fetch can land after it.
22	type Slot<-V: Data> is Data:
23	  Slot{next: Nat, floor: Nat, entry: Maybe<&2, Entry<V>>}
24	
25	# One fetch in flight: its key, its generation, and the clock when it started.
26	# It is affine, so it completes at most once.
27	type Ticket is Type:
28	  Ticket{key: String, gen: Nat, at: Nat}
29	
30	type Cache<-V: Data> is Data:
31	  Cache{policy: Policy, slots: OMap.OMap<String, Slot<V>>}
32	
33	# Slot
34	# ----
35	
36	def Slot.new(-V: Data) -> Slot<V>:
37	  Slot{0n, 0n, None{}}
38	
39	def Entry.expires(-V: Data, e: Entry<V>) -> Nat:
40	  match e:
41	    case Hit{v, x, t}:
42	      t
43	    case Miss{t}:
44	      t
45	
46	# The entry for a result fetched at `at`. Its age counts from the fetch start.
47	def Entry.of(-V: Data, r: Found<V>, p: Policy, at: Nat) -> Entry<V>:
48	  match r:
49	    case Found{v, x}:
50	      Policy{ttl, neg} = p
51	      Hit{v, x, Nat.add(at, ttl)}
52	    case Missing{}:
53	      Policy{ttl, neg} = p
54	      Miss{Nat.add(at, neg)}
55	
56	def Slot.serve(-V: Data, fresh: Bool, e: Entry<V>) -> Maybe<&2, Entry<V>>:
57	  match fresh:
58	    case True{}:
59	      Some{e}
60	    case False{}:
61	      None{}
62	
63	def Slot.lookup(-V: Data, m: Maybe<&2, Entry<V>>, +now: Nat) -> Maybe<&2, Entry<V>>:
64	  match m:
65	    case None{}:
66	      None{}
67	    case Some{+e}:
68	      Slot.serve(V, Nat.is_lt(now, Entry.expires(V, e)), e)
69	
70	# The fresh entry at `now`, or None when the caller must fetch.
71	def Slot.read(-V: Data, s: Slot<V>, +now: Nat) -> Maybe<&2, Entry<V>>:
72	  Slot{n, f, m} = s
73	  Slot.lookup(V, m, now)
74	
75	# Takes the next generation for a new fetch.
76	def Slot.start(-V: Data, s: Slot<V>) -> Nat & Slot<V>:
77	  Slot{+n, f, m} = s
78	  (n, Slot{1n+n, f, m})
79	
80	def Slot.complete.if(-V: Data, ok: Bool, n: Nat, f: Nat, m: Maybe<&2, Entry<V>>, g: Nat, e: Entry<V>) -> Slot<V>:
81	  match ok:
82	    case True{}:
83	      Slot{n, 1n+g, Some{e}}
84	    case False{}:
85	      Slot{n, f, m}
86	
87	# Stores the result of fetch g, unless g is stale or was never issued.
88	def Slot.complete(-V: Data, p: Policy, s: Slot<V>, +g: Nat, at: Nat, r: Found<V>) -> Slot<V>:
89	  Slot{+n, +f, m} = s
90	  Slot.complete.if(V, Nat.is_le(f, g) && Nat.is_lt(g, n), n, f, m, g, Entry.of(V, r, p, at))
91	
92	# Drops the entry and voids every fetch issued so far.
93	def Slot.invalidate(-V: Data, s: Slot<V>) -> Slot<V>:
94	  Slot{+n, f, m} = s
95	  Slot{n, n, None{}}
96	
97	# Drops the entry. The generations stay, so no fetch that was stale before is accepted after.
98	def Slot.evict(-V: Data, s: Slot<V>) -> Slot<V>:
99	  Slot{n, f, m} = s
100	  Slot{n, f, None{}}
101	
102	# Cache
103	# -----
104	
105	def key.cmp.fin(c: Cmp, rest: Cmp) -> Cmp:
106	  match c:
107	    case LT{}:
108	      LT{}
109	    case EQ{}:
110	      rest
111	    case GT{}:
112	      GT{}
113	
114	# Keys in code-point order. String.order rebuilds both strings on every call.
115	def key.cmp(a: String, b: String) -> Cmp:
116	  match a b:
117	    case SNil{} SNil{}:
118	      EQ{}
119	    case SNil{} SCon{h, t}:
120	      LT{}
121	    case SCon{h, t} SNil{}:
122	      GT{}
123	    case SCon{Chr{+x}, s} SCon{Chr{+y}, t}:
124	      key.cmp.fin(U32.cmp(x, y), key.cmp(s, t))
125	
126	def Cache.new(-V: Data, p: Policy) -> Cache<V>:
127	  Cache{p, OMap.OMap.new(String, Slot<V>)}
128	
129	def Cache.slot(~V: Data, slots: OMap.OMap<String, Slot<V>>, +key: String) -> Slot<V>:
130	  Maybe.default(&2, Slot<V>, OMap.OMap.get(~String, ~Slot<V>, ~key.cmp, slots, key), Slot.new(V))
131	
132	def Cache.put(~V: Data, p: Policy, slots: OMap.OMap<String, Slot<V>>, +key: String, +s: Slot<V>) -> Cache<V>:
133	  Cache{p, OMap.OMap.put(~String, ~Slot<V>, ~key.cmp, slots, key, s)}
134	
135	# The fresh entry for key at `now`, or None when the caller must fetch.
136	def Cache.read(~V: Data, c: Cache<V>, +key: String, +now: Nat) -> Maybe<&2, Entry<V>>:
137	  Cache{p, slots} = c
138	  Slot.read(V, Cache.slot(~V, slots, key), now)
139	
140	def Cache.start.fin(~V: Data, p: Policy, slots: OMap.OMap<String, Slot<V>>, +key: String, at: Nat, r: Nat & Slot<V>) -> Ticket & Cache<V>:
141	  (g, s) = r
142	  (Ticket{key, g, at}, Cache.put(~V, p, slots, key, s))
143	
144	# Starts a fetch of key at clock `at`. Fetch upstream, then pass the ticket to complete.
145	def Cache.start(~V: Data, c: Cache<V>, +key: String, at: Nat) -> Ticket & Cache<V>:
146	  Cache{p, +slots} = c
147	  Cache.start.fin(~V, p, slots, key, at, Slot.start(V, Cache.slot(~V, slots, key)))
148	
149	# Stores what the ticket's fetch found. A stale ticket changes nothing.
150	def Cache.complete(~V: Data, c: Cache<V>, t: Ticket, r: Found<V>) -> Cache<V>:
151	  Cache{+p, +slots} = c
152	  Ticket{+key, g, at} = t
153	  Cache.put(~V, p, slots, key, Slot.complete(V, p, Cache.slot(~V, slots, key), g, at, r))
154	
155	# Drops key's entry and voids its fetches in flight.
156	def Cache.invalidate(~V: Data, c: Cache<V>, +key: String) -> Cache<V>:
157	  Cache{p, +slots} = c
158	  Cache.put(~V, p, slots, key, Slot.invalidate(V, Cache.slot(~V, slots, key)))
159	
160	# Drops key's entry. Its generations stay, so stale fetches stay stale.
161	def Cache.evict(~V: Data, c: Cache<V>, +key: String) -> Cache<V>:
162	  Cache{p, +slots} = c
163	  Cache.put(~V, p, slots, key, Slot.evict(V, Cache.slot(~V, slots, key)))