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