Spaces:
Running
Running
File size: 11,552 Bytes
979bf48 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 | "use strict";
Object.defineProperty(exports, "__esModule", {
value: true
});
0 && (module.exports = {
Fallback: null,
createCacheMap: null,
deleteFromCacheMap: null,
deleteMapEntry: null,
getFromCacheMap: null,
isValueExpired: null,
setInCacheMap: null,
setSizeInCacheMap: null
});
function _export(target, all) {
for(var name in all)Object.defineProperty(target, name, {
enumerable: true,
get: all[name]
});
}
_export(exports, {
Fallback: function() {
return Fallback;
},
createCacheMap: function() {
return createCacheMap;
},
deleteFromCacheMap: function() {
return deleteFromCacheMap;
},
deleteMapEntry: function() {
return deleteMapEntry;
},
getFromCacheMap: function() {
return getFromCacheMap;
},
isValueExpired: function() {
return isValueExpired;
},
setInCacheMap: function() {
return setInCacheMap;
},
setSizeInCacheMap: function() {
return setSizeInCacheMap;
}
});
const _lru = require("./lru");
const Fallback = {};
// This is a special internal key that is used for "revalidation" entries. It's
// an implementation detail that shouldn't leak outside of this module.
const Revalidation = {};
function createCacheMap() {
const cacheMap = {
parent: null,
key: null,
value: null,
map: null,
// LRU-related fields
prev: null,
next: null,
size: 0
};
return cacheMap;
}
function getOrInitialize(cacheMap, keys, isRevalidation) {
// Go through each level of keys until we find the entry that matches, or
// create a new entry if one doesn't exist.
//
// This function will only return entries that match the keypath _exactly_.
// Unlike getWithFallback, it will not access fallback entries unless it's
// explicitly part of the keypath.
let entry = cacheMap;
let remainingKeys = keys;
let key = null;
while(true){
const previousKey = key;
if (remainingKeys !== null) {
key = remainingKeys.value;
remainingKeys = remainingKeys.parent;
} else if (isRevalidation && previousKey !== Revalidation) {
// During a revalidation, we append an internal "Revalidation" key to
// the end of the keypath. The "normal" entry is its parent.
// However, if the parent entry is currently empty, we don't need to store
// this as a revalidation entry. Just insert the revalidation into the
// normal slot.
if (entry.value === null) {
return entry;
}
// Otheriwse, create a child entry.
key = Revalidation;
} else {
break;
}
let map = entry.map;
if (map !== null) {
const existingEntry = map.get(key);
if (existingEntry !== undefined) {
// Found a match. Keep going.
entry = existingEntry;
continue;
}
} else {
map = new Map();
entry.map = map;
}
// No entry exists yet at this level. Create a new one.
const newEntry = {
parent: entry,
key,
value: null,
map: null,
// LRU-related fields
prev: null,
next: null,
size: 0
};
map.set(key, newEntry);
entry = newEntry;
}
return entry;
}
function getFromCacheMap(now, currentCacheVersion, rootEntry, keys, isRevalidation) {
const entry = getEntryWithFallbackImpl(now, currentCacheVersion, rootEntry, keys, isRevalidation, 0);
if (entry === null || entry.value === null) {
return null;
}
// This is an LRU access. Move the entry to the front of the list.
(0, _lru.lruPut)(entry);
return entry.value;
}
function isValueExpired(now, currentCacheVersion, value) {
return value.staleAt <= now || value.version < currentCacheVersion;
}
function lazilyEvictIfNeeded(now, currentCacheVersion, entry) {
// We have a matching entry, but before we can return it, we need to check if
// it's still fresh. Otherwise it should be treated the same as a cache miss.
if (entry.value === null) {
// This entry has no value, so there's nothing to evict.
return entry;
}
const value = entry.value;
if (isValueExpired(now, currentCacheVersion, value)) {
// The value expired. Lazily evict it from the cache, and return null. This
// is conceptually the same as a cache miss.
deleteMapEntry(entry);
return null;
}
// The matched entry has not expired. Return it.
return entry;
}
function getEntryWithFallbackImpl(now, currentCacheVersion, entry, keys, isRevalidation, previousKey) {
// This is similar to getExactEntry, but if an exact match is not found for
// a key, it will return the fallback entry instead. This is recursive at
// every level, e.g. an entry with keypath [a, Fallback, c, Fallback] is
// valid match for [a, b, c, d].
//
// It will return the most specific match available.
let key;
let remainingKeys;
if (keys !== null) {
key = keys.value;
remainingKeys = keys.parent;
} else if (isRevalidation && previousKey !== Revalidation) {
// During a revalidation, we append an internal "Revalidation" key to
// the end of the keypath.
key = Revalidation;
remainingKeys = null;
} else {
// There are no more keys. This is the terminal entry.
// TODO: When performing a lookup during a navigation, as opposed to a
// prefetch, we may want to skip entries that are Pending if there's also
// a Fulfilled fallback entry. Tricky to say, though, since if it's
// already pending, it's likely to stream in soon. Maybe we could do this
// just on slow connections and offline mode.
return lazilyEvictIfNeeded(now, currentCacheVersion, entry);
}
const map = entry.map;
if (map !== null) {
const existingEntry = map.get(key);
if (existingEntry !== undefined) {
// Found an exact match for this key. Keep searching.
const result = getEntryWithFallbackImpl(now, currentCacheVersion, existingEntry, remainingKeys, isRevalidation, key);
if (result !== null) {
return result;
}
}
// No match found for this key. Check if there's a fallback.
const fallbackEntry = map.get(Fallback);
if (fallbackEntry !== undefined) {
// Found a fallback for this key. Keep searching.
return getEntryWithFallbackImpl(now, currentCacheVersion, fallbackEntry, remainingKeys, isRevalidation, key);
}
}
return null;
}
function setInCacheMap(cacheMap, keys, value, isRevalidation) {
// Add a value to the map at the given keypath. If the value is already
// part of the map, it's removed from its previous keypath. (NOTE: This is
// unlike a regular JS map, but the behavior is intentional.)
const entry = getOrInitialize(cacheMap, keys, isRevalidation);
setMapEntryValue(entry, value);
// This is an LRU access. Move the entry to the front of the list.
(0, _lru.lruPut)(entry);
(0, _lru.updateLruSize)(entry, value.size);
}
function setMapEntryValue(entry, value) {
if (entry.value !== null) {
// There's already a value at the given keypath. Disconnect the old value
// from the map. We're not calling `deleteMapEntry` here because the
// entry itself is still in the map. We just want to overwrite its value.
dropRef(entry.value);
entry.value = null;
}
// This value may already be in the map at a different keypath.
// Grab a reference before we overwrite it.
const oldEntry = value.ref;
entry.value = value;
value.ref = entry;
(0, _lru.updateLruSize)(entry, value.size);
if (oldEntry !== null && oldEntry !== entry && oldEntry.value === value) {
// This value is already in the map at a different keypath in the map.
// Values only exist at a single keypath at a time. Remove it from the
// previous keypath.
//
// Note that only the internal map entry is garbage collected; we don't
// call `dropRef` here because it's still in the map, just
// at a new keypath (the one we just set, above).
deleteMapEntry(oldEntry);
}
}
function deleteFromCacheMap(value) {
const entry = value.ref;
if (entry === null) {
// This value is not a member of any map.
return;
}
dropRef(value);
deleteMapEntry(entry);
}
function dropRef(value) {
// Drop the value from the map by setting its `ref` backpointer to
// null. This is a separate operation from `deleteMapEntry` because when
// re-keying a value we need to be able to delete the old, internal map
// entry without garbage collecting the value itself.
value.ref = null;
}
function deleteMapEntry(entry) {
// Delete the entry from the cache.
entry.value = null;
(0, _lru.deleteFromLru)(entry);
// Check if we can garbage collect the entry.
const map = entry.map;
if (map === null) {
// Since this entry has no value, and also no child entries, we can
// garbage collect it. Remove it from its parent, and keep garbage
// collecting the parents until we reach a non-empty entry.
let parent = entry.parent;
let key = entry.key;
while(parent !== null){
const parentMap = parent.map;
if (parentMap !== null) {
parentMap.delete(key);
if (parentMap.size === 0) {
// We just removed the last entry in the parent map.
parent.map = null;
if (parent.value === null) {
// The parent node has no child entries, nor does it have a value
// on itself. It can be garbage collected. Keep going.
key = parent.key;
parent = parent.parent;
continue;
}
}
}
break;
}
} else {
// Check if there's a revalidating entry. If so, promote it to a
// "normal" entry, since the normal one was just deleted.
const revalidatingEntry = map.get(Revalidation);
if (revalidatingEntry !== undefined && revalidatingEntry.value !== null) {
setMapEntryValue(entry, revalidatingEntry.value);
}
}
}
function setSizeInCacheMap(value, size) {
const entry = value.ref;
if (entry === null) {
// This value is not a member of any map.
return;
}
// Except during initialization (when the size is set to 0), this is the only
// place the `size` field should be updated, to ensure it's in sync with the
// the LRU.
value.size = size;
(0, _lru.updateLruSize)(entry, size);
}
if ((typeof exports.default === 'function' || (typeof exports.default === 'object' && exports.default !== null)) && typeof exports.default.__esModule === 'undefined') {
Object.defineProperty(exports.default, '__esModule', { value: true });
Object.assign(exports.default, exports);
module.exports = exports.default;
}
//# sourceMappingURL=cache-map.js.map |