defend against mutation while iterating

isaacs · isaacs · commit c1ad5da5685b · 2022-03-13T19:57:12.000-07:00
Fix: #212
diff --git a/index.js b/index.js
@@ -244,10 +244,12 @@ class LRUCache {
   *indexes ({ allowStale = this.allowStale } = {}) {
     if (this.size) {
       for (let i = this.tail, j; true; ) {
+        j = i === this.head
         if (allowStale || !this.isStale(i)) {
           yield i
         }
-        if (i === this.head) {
+        // either head now, or WAS head and head was deleted
+        if (i === this.head || j && !this.isValidIndex(i)) {
           break
         } else {
           i = this.prev[i]
@@ -259,10 +261,12 @@ class LRUCache {
   *rindexes ({ allowStale = this.allowStale } = {}) {
     if (this.size) {
       for (let i = this.head, j; true; ) {
+        j = i === this.tail
         if (allowStale || !this.isStale(i)) {
           yield i
         }
-        if (i === this.tail) {
+        // either the tail now, or WAS the tail, and deleted
+        if (i === this.tail || j && !this.isValidIndex(i)) {
           break
         } else {
           i = this.next[i]
@@ -271,6 +275,10 @@ class LRUCache {
     }
   }
 
+  isValidIndex (index) {
+    return this.keyMap.get(this.keyList[index]) === index
+  }
+
   *entries () {
     for (const i of this.indexes()) {
       yield [this.keyList[i], this.valList[i]]
@@ -335,16 +343,12 @@ class LRUCache {
 
   purgeStale () {
     let deleted = false
-    const toDelete = []
     for (const i of this.rindexes({ allowStale: true })) {
       if (this.isStale(i)) {
-        toDelete.push(this.keyList[i])
+        this.delete(this.keyList[i])
         deleted = true
       }
     }
-    for (const k of toDelete) {
-      this.delete(k)
-    }
     return deleted
   }
 
diff --git a/test/delete-while-iterating.js b/test/delete-while-iterating.js
@@ -0,0 +1,68 @@
+const t = require('tap')
+const LRU = require('../')
+
+t.beforeEach(t => {
+  const c = new LRU({ max: 5 })
+  c.set(0, 0)
+  c.set(1, 1)
+  c.set(2, 2)
+  c.set(3, 3)
+  c.set(4, 4)
+  t.context = c
+})
+
+t.test('delete evens', t => {
+  const c = t.context
+  t.same([...c.keys()], [4, 3, 2, 1, 0])
+
+  for (const k of c.keys()) {
+    if (k % 2 === 0) {
+      c.delete(k)
+    }
+  }
+
+  t.same([...c.keys()], [3, 1])
+  t.end()
+})
+
+t.test('delete odds', t => {
+  const c = t.context
+  t.same([...c.keys()], [4, 3, 2, 1, 0])
+
+  for (const k of c.keys()) {
+    if (k % 2 === 1) {
+      c.delete(k)
+    }
+  }
+
+  t.same([...c.keys()], [4, 2, 0])
+  t.end()
+})
+
+t.test('rdelete evens', t => {
+  const c = t.context
+  t.same([...c.keys()], [4, 3, 2, 1, 0])
+
+  for (const k of c.rkeys()) {
+    if (k % 2 === 0) {
+      c.delete(k)
+    }
+  }
+
+  t.same([...c.keys()], [3, 1])
+  t.end()
+})
+
+t.test('rdelete odds', t => {
+  const c = t.context
+  t.same([...c.keys()], [4, 3, 2, 1, 0])
+
+  for (const k of c.rkeys()) {
+    if (k % 2 === 1) {
+      c.delete(k)
+    }
+  }
+
+  t.same([...c.keys()], [4, 2, 0])
+  t.end()
+})
