1import logging
2from typing import Any, Callable, Dict, Optional, Set, Tuple
3
4
5class Cacheable(dict):
6 """
7 A dictionary that is specifically cacheable, by way of its added
8 cache_key property.
9 """
10
11 _cache_key: Optional[str]
12
13 @property
14 def cache_key(self) -> str:
15 if not self._cache_key:
16 raise RuntimeError("cache key is not set")
17
18 return self._cache_key
19
20 @cache_key.setter
21 def cache_key(self, cache_key: str) -> None:
22 self._cache_key = cache_key
23
24
25DeletionHandler = Callable[[Cacheable], None]
26CacheEntry = Tuple[Cacheable, Optional[DeletionHandler]]
27CacheLink = Set[str]
28
29
30class Cache:
31 """
32 A cache of Cacheables, supporting add/delete/fetch and also linking
33 an owning Cacheable to an owned Cacheable. Deletion is cascaded: if you
34 delete something, everything it owns is recursively deleted too. THIS ONLY
35 HAPPENS IN ONE DIRECTION at present, so deleting a Cacheable in the middle
36 of the ownership tree can leave dangling pointers.
37 """
38
39 def __init__(self, logger: logging.Logger) -> None:
40 self.cache: Dict[str, CacheEntry] = {}
41 self.links: Dict[str, CacheLink] = {}
42 self.logger = logger
43
44 self.reset_stats()
45
46 self.logger.debug("Cache initialized")
47
48 def reset_stats(self) -> None:
49 self.hits = 0
50 self.misses = 0
51 self.invalidate_calls = 0
52 self.invalidated_objects = 0
53
54 @staticmethod
55 def fn_name(fn: Optional[Callable]) -> str:
56 return fn.__name__ if (fn and fn.__name__) else "-none-"
57
58 def add(self, rsrc: Cacheable, on_delete: Optional[DeletionHandler] = None) -> None:
59 """
60 Adds an entry to the cache, if it's not already present. If
61 on_delete is not None, it will called when rsrc is removed from
62 the cache.
63 """
64
65 key = rsrc.cache_key
66
67 if not key:
68 self.logger.info(f"CACHE: ignore, no cache_key: {rsrc}")
69 elif key in self.cache:
70 # self.logger.info(f"CACHE: ignore, already present: {rsrc}")
71 pass
72 else:
73 self.logger.debug(f"CACHE: adding {key}: {rsrc}, on_delete {self.fn_name(on_delete)}")
74
75 self.cache[key] = (rsrc, on_delete)
76
77 def link(self, owner: Cacheable, owned: Cacheable) -> None:
78 """
79 Adds a link to the cache. Links are directional from the owner to
80 the owned. The basic idea is that if the owner changes, all the owned
81 things get invalidated. Both the owner and the owned must be in the
82 cache.
83 """
84
85 owner_key = owner.cache_key
86 owned_key = owned.cache_key
87
88 if not owner_key:
89 self.logger.info(f"CACHE: cannot link, owner has no key: {owner}")
90 return
91
92 if not owned_key:
93 self.logger.info(f"CACHE: cannot link, owned has no key: {owned}")
94 return
95
96 if owner_key not in self.cache:
97 self.logger.info(f"CACHE: cannot link, owner not cached: {owner}")
98 return
99
100 if owned_key not in self.cache:
101 self.logger.info(f"CACHE: cannot link, owned not cached: {owned}")
102 return
103
104 self.logger.debug(f"CACHE: linking {owner_key} -> {owned_key}")
105
106 links = self.links.setdefault(owner_key, set())
107 links.update([owned_key])
108
109 def invalidate(self, key: str) -> None:
110 """
111 Recursively invalidate the entry named by 'key' and everything to which it
112 is linked.
113 """
114
115 # We use worklist to keep track of things to consider: for starters,
116 # it just has our key in it, and as we find owned things, we add them
117 # to the worklist to consider.
118 #
119 # Note that word "consider". If you want to invalidate something from
120 # the cache that isn't in the cache, that's not an error -- it'll be
121 # silently ignored. That helps with dangling links (e.g. if two Mappings
122 # both link to the same Group, and you invalidate the first Mapping, the
123 # second will have a dangling link to the now-invalidated Group, and that
124 # needs to not break anything).
125
126 self.invalidate_calls += 1
127
128 worklist = [key]
129
130 # Under the hood, "invalidating" something from this cache is really
131 # deleting it, so we'll use "to_delete" for the set of things we're going
132 # to, y'knom, delete. We find all the resources we're going to work with
133 # before deleting any of them, because I get paranoid about modifying a
134 # data structure while I'm trying to traverse it.
135 to_delete: Dict[str, CacheEntry] = {}
136
137 # Keep going until we have nothing else to do.
138 while worklist:
139 # Pop off the first thing...
140 key = worklist.pop(0)
141
142 # ...and check if it's in the cache.
143 if key in self.cache:
144 # It is, good. We can append it to our set of things to delete...
145 rsrc, on_delete = self.cache[key]
146
147 self.logger.debug(f"CACHE: DEL {key}: will delete {rsrc}")
148
149 if key not in to_delete:
150 # We haven't seen this key, so remember to delete it...
151 to_delete[key] = (rsrc, on_delete)
152
153 # ...and then toss all of its linked objects on our list to
154 # consider.
155 if key in self.links:
156 for owned in sorted(self.links[key]):
157 self.logger.debug(f"CACHE: DEL {key}: will check owned {owned}")
158 worklist.append(owned)
159
160 # (If we have seen the key already, just ignore it and go to the next
161 # key in the worklist. This is important to not get stuck if we somehow
162 # get a circular link list.)
163
164 # OK, we have a set of things to delete. Get to it.
165 for key, rdh in to_delete.items():
166 self.logger.debug(f"CACHE: DEL {key}: smiting!")
167
168 self.invalidated_objects += 1
169 del self.cache[key]
170
171 if key in self.links:
172 del self.links[key]
173
174 rsrc, on_delete = rdh
175
176 if on_delete:
177 self.logger.debug(f"CACHE: DEL {key}: calling {self.fn_name(on_delete)}")
178 on_delete(rsrc)
179
180 def __getitem__(self, key: str) -> Optional[Cacheable]:
181 """
182 Fetches only the _resource_ for a given key from the cache. If the
183 key is not present in the cache, returns None.
184
185 If you need the deletion callback, you'll have to work with
186 self.cache manually.
187 """
188
189 item: Optional[CacheEntry] = self.cache.get(key, None)
190
191 if item is not None:
192 self.logger.debug(f"CACHE: got {key}")
193 self.hits += 1
194 return item[0]
195 else:
196 self.logger.debug(f"CACHE: no {key}")
197 self.misses += 1
198 return None
199
200 def dump(self, what, *args) -> None:
201 """
202 Dump the cache to the logger.
203 """
204
205 if self.logger.isEnabledFor(logging.DEBUG):
206 self.logger.debug("CACHE DUMP AFTER " + what, *args)
207
208 for k in sorted(self.cache.keys()):
209 rsrc, on_delete = self.cache[k]
210
211 self.logger.debug(f"CACHE DUMP: {k}, on_delete {self.fn_name(on_delete)}:")
212
213 if k in self.links:
214 for owned in sorted(self.links[k]):
215 self.logger.debug(f"CACHE DUMP: -> {owned}")
216
217 def dump_stats(self) -> None:
218 total = self.hits + self.misses
219
220 if total > 0:
221 ratio = "%.1f%%" % ((float(self.hits) / float(total)) * 100.0)
222 else:
223 ratio = "--"
224
225 self.logger.info("CACHE: Total requests: %d" % total)
226 self.logger.info("CACHE: Hit ratio: %s" % ratio)
227 self.logger.info("CACHE: Invalidations: %d calls" % self.invalidate_calls)
228 self.logger.info("CACHE: %d objects" % self.invalidated_objects)
229
230
231class NullCache(Cache):
232 """
233 A Cache that doesn't actually cache anything -- basically, a no-op
234 implementation of the Cache interface.
235
236 Giving consumers of the Cache class a way to make their cache
237 instance non-Optional, without actually requiring the use of the
238 cache, makes the consumer code simpler.
239 """
240
241 def __init__(self, logger: logging.Logger) -> None:
242 self.logger = logger
243 self.logger.debug("NullCache: INIT")
244 self.reset_stats()
245
246 def add(self, rsrc: Cacheable, on_delete: Optional[DeletionHandler] = None) -> None:
247 pass
248
249 def link(self, owner: Cacheable, owned: Cacheable) -> None:
250 pass
251
252 def invalidate(self, key: str) -> None:
253 self.invalidate_calls += 1
254
255 def __getitem__(self, key: str) -> Any:
256 self.misses += 1
257 return None
258
259 def dump(self, what, *args) -> None:
260 pass
261 # self.logger.info("NullCache: empty")
View as plain text