Ast interner

UnitTestBot · Saloed · Feb 17, 2023 · Jan 25, 2023 · Jan 27, 2023 · Jan 17, 2023
commit 84806be4cd93cc227118c8bd6e0f2d4fa36c1a3b
diff --git a/ksmt-core/src/main/kotlin/org/ksmt/cache/ConcurrentWeakCache.kt b/ksmt-core/src/main/kotlin/org/ksmt/cache/ConcurrentWeakCache.kt
@@ -0,0 +1,66 @@
+package org.ksmt.cache
+
+import java.lang.ref.Reference
+import java.lang.ref.ReferenceQueue
+import java.lang.ref.WeakReference
+
+class ConcurrentWeakCache<K : KInternedObject, V : Any> : ConcurrentWeakHashMapCache<K, V>() {
+    override fun lookupKey(key: K): Any = LookupCacheKey(key)
+
+    override fun newNode(key: K, referenceQueue: ReferenceQueue<K>, value: V): KeyRefNode<K, V> {
+        val keyRef = WeakCacheKey(key, referenceQueue)
+        return CacheNode(keyRef, value)
+    }
+
+    private class CacheNode<T : KInternedObject, V : Any>(
+        keyRef: Reference<T>,
+        private var value: V
+    ) : KeyRefNode<T, V>(keyRef) {
+
+        override fun getValue(): V = value
+
+        override fun setValue(value: V) {
+            this.value = value
+        }
+    }
+
+    private interface CacheKey<K : KInternedObject> {
+        fun get(): K?
+    }
+
+    private class WeakCacheKey<K : KInternedObject>(
+        key: K?, queue: ReferenceQueue<K>?
+    ) : WeakReference<K>(key, queue), CacheKey<K> {
+        private val hashCode: Int = System.identityHashCode(key)
+
+        override fun equals(other: Any?): Boolean = when {
+            other === this -> true
+            other is CacheKey<*> -> get() === other.get()
+            else -> false
+        }
+
+        override fun hashCode(): Int = hashCode
+
+        override fun toString(): String =
+            "{key=${get()} hash=$hashCode}"
+    }
+
+    private class LookupCacheKey<K : KInternedObject>(
+        private val key: K
+    ) : CacheKey<K> {
+        private val hashCode: Int = System.identityHashCode(key)
+
+        override fun get(): K = key
+
+        override fun equals(other: Any?): Boolean = when {
+            other === this -> true
+            other is CacheKey<*> -> get() === other.get()
+            else -> false
+        }
+
+        override fun hashCode(): Int = hashCode
+
+        override fun toString(): String =
+            "{key=${get()} hash=$hashCode}"
+    }
+}
diff --git a/...n/org/ksmt/cache/ConcurrentWeakHashMap.kt → .../ksmt/cache/ConcurrentWeakHashMapCache.kt b/...n/org/ksmt/cache/ConcurrentWeakHashMap.kt → .../ksmt/cache/ConcurrentWeakHashMapCache.kt
@@ -1,78 +1,84 @@
 package org.ksmt.cache
 
+import java.lang.ref.Reference
 import java.lang.ref.ReferenceQueue
+import java.lang.ref.WeakReference
 import java.util.concurrent.ConcurrentHashMap
 import java.util.concurrent.atomic.AtomicInteger
 import java.util.concurrent.locks.ReentrantLock
 
-abstract class Node<K : Any, V : Any> {
-    abstract fun getKeyReference(): Any
-    abstract fun getKey(): K?
-    abstract fun getValue(): V
-    abstract fun setValue(value: V)
-    abstract fun isAlive(): Boolean
-    abstract fun isDead(): Boolean
-    abstract fun retire()
-    abstract fun die()
-}
+abstract class ConcurrentWeakHashMapCache<K : Any, V : Any> {
+    private val data = ConcurrentHashMap<Any, KeyRefNode<K, V>>()
+    private val keyReferenceQueue = ReferenceQueue<K>()
+    private val cleanupLock = ReentrantLock()
+    private val cleanupStatus = AtomicInteger(IDLE)
+    private var removeHandler: CacheRemoveHandler<K, V>? = null
 
-interface RemoveHandler<K, V> {
-    fun onRemove(key: K?, value: V)
-}
+    abstract fun lookupKey(key: K): Any
 
-/** A cleanup is not taking place.  */
-private const val IDLE = 0
+    abstract fun newNode(key: K, referenceQueue: ReferenceQueue<K>, value: V): KeyRefNode<K, V>
 
-/** A cleanup is required due to write modification.  */
-private const val REQUIRED = 1
+    abstract class KeyRefNode<K : Any, V : Any>(keyRef: Reference<K>) {
+        @Volatile
+        private var keyReference: Reference<out K> = keyRef
 
-/** A cleanup is in progress and will transition to idle.  */
-private const val PROCESSING_TO_IDLE = 2
+        fun getKeyReference(): Any = keyReference
 
-/** A cleanup is in progress and will transition to required.  */
-private const val PROCESSING_TO_REQUIRED = 3
+        fun getKey(): K? = keyReference.get()
 
-abstract class ConcurrentWeakHashMapCache<K : Any, V : Any> {
-    private val data = ConcurrentHashMap<Any, Node<K, V>>()
-    private val keyReferenceQueue = ReferenceQueue<K>()
-    private val cleanupLock = ReentrantLock()
-    private val cleanupStatus = AtomicInteger(IDLE)
-    private var removeHandler: RemoveHandler<K, V>? = null
 
-    abstract fun lookupKey(key: K): Any
+        abstract fun getValue(): V
+        abstract fun setValue(value: V)
+
+        fun isAlive(): Boolean {
+            val keyRef = keyReference
+            return keyRef !== deadRef && keyRef !== retiredRef
+        }
+
+        fun isDead(): Boolean = keyReference === deadRef
 
-    abstract fun newNode(key: K, referenceQueue: ReferenceQueue<K>, value: V): Node<K, V>
+        fun retire() {
+            val keyRef = keyReference
+            keyReference = deadRef
+            keyRef.clear()
+        }
 
-    fun addRemoveHandler(handler: RemoveHandler<K, V>) {
+        fun die() {
+            val keyRef = keyReference
+            keyReference = retiredRef
+            keyRef.clear()
+        }
+
+        companion object {
+            @JvmStatic
+            private val deadRef: Reference<Nothing> = WeakReference(null)
+
+            @JvmStatic
+            private val retiredRef: Reference<Nothing> = WeakReference(null)
+        }
+    }
+
+    fun addRemoveHandler(handler: CacheRemoveHandler<K, V>) {
         removeHandler = handler
     }
 
     fun get(key: K): V? = getNode(key)?.getValue()
 
-    fun put(key: K, value: V, onlyIfAbsent: Boolean): V? {
-        val lookupKey = lookupKey(key)
-        return putUtil(key, value, onlyIfAbsent, lookupKey)
-    }
+    fun put(key: K, value: V, onlyIfAbsent: Boolean): V? = putUtil(key, value, onlyIfAbsent)
 
-    fun internKey(key: K, valueStub: V): K {
-        val lookupKey = lookupKey(key)
-        return internUtil(key, valueStub, lookupKey)
-    }
+    fun internKey(key: K, valueStub: V): K = internUtil(key, valueStub)
 
-    private fun getNode(key: K): Node<K, V>? {
+    private fun getNode(key: K): KeyRefNode<K, V>? {
         val lookupKey = lookupKey(key)
         val node = data.get(lookupKey)
         afterRead()
         return node
     }
 
-    private fun putUtil(
-        key: K,
-        value: V,
-        onlyIfAbsent: Boolean,
-        lookupKey: Any,
-    ): V? {
-        var node: Node<K, V>? = null
+    @Suppress("LoopWithTooManyJumpStatements")
+    private fun putUtil(key: K, value: V, onlyIfAbsent: Boolean): V? {
+        var node: KeyRefNode<K, V>? = null
+        val lookupKey = lookupKey(key)
 
         while (true) {
             var current = data.get(lookupKey)
@@ -126,12 +132,10 @@ abstract class ConcurrentWeakHashMapCache<K : Any, V : Any> {
         }
     }
 
-    private fun internUtil(
-        key: K,
-        value: V,
-        lookupKey: Any
-    ): K {
-        var node: Node<K, V>? = null
+    @Suppress("NestedBlockDepth")
+    private fun internUtil(key: K, value: V): K {
+        var node: KeyRefNode<K, V>? = null
+        val lookupKey = lookupKey(key)
 
         while (true) {
             var current = data.get(lookupKey)
@@ -168,7 +172,7 @@ abstract class ConcurrentWeakHashMapCache<K : Any, V : Any> {
         }
     }
 
-    private fun updateValueIfAlive(node: Node<K, V>, value: V): V? = synchronized(node) {
+    private fun updateValueIfAlive(node: KeyRefNode<K, V>, value: V): V? = synchronized(node) {
         if (!node.isAlive()) return null
         val oldValue = node.getValue()
         node.setValue(value)
@@ -255,7 +259,7 @@ abstract class ConcurrentWeakHashMapCache<K : Any, V : Any> {
         }
     }
 
-    private fun cleanupEntry(node: Node<K, V>) {
+    private fun cleanupEntry(node: KeyRefNode<K, V>) {
         val keyRef = node.getKeyReference()
         val key = node.getKey()
         var nodeResurrected = false
@@ -288,8 +292,22 @@ abstract class ConcurrentWeakHashMapCache<K : Any, V : Any> {
         }
     }
 
-    private fun makeDead(node: Node<K, V>) = synchronized(node) {
+    private fun makeDead(node: KeyRefNode<K, V>) = synchronized(node) {
         if (node.isDead()) return
         node.die()
     }
+
+    companion object {
+        /** A cleanup is not taking place.  */
+        private const val IDLE = 0
+
+        /** A cleanup is required due to write modification.  */
+        private const val REQUIRED = 1
+
+        /** A cleanup is in progress and will transition to idle.  */
+        private const val PROCESSING_TO_IDLE = 2
+
+        /** A cleanup is in progress and will transition to required.  */
+        private const val PROCESSING_TO_REQUIRED = 3
+    }
 }
diff --git a/ksmt-core/src/main/kotlin/org/ksmt/cache/ConcurrentWeakInterner.kt b/ksmt-core/src/main/kotlin/org/ksmt/cache/ConcurrentWeakInterner.kt
@@ -0,0 +1,69 @@
+package org.ksmt.cache
+
+import java.lang.ref.Reference
+import java.lang.ref.ReferenceQueue
+import java.lang.ref.WeakReference
+
+class ConcurrentWeakInterner<T : KInternedObject> : ConcurrentWeakHashMapCache<T, Any>() {
+
+    fun intern(obj: T): T = internKey(obj, valueStub)
+
+    override fun lookupKey(key: T): Any = LookupInternerKey(key)
+
+    override fun newNode(key: T, referenceQueue: ReferenceQueue<T>, value: Any): KeyRefNode<T, Any> {
+        val keyRef = WeakInternerKey(key, referenceQueue)
+        return InternerNode(keyRef)
+    }
+
+    private class InternerNode<T : KInternedObject>(keyRef: Reference<T>) : KeyRefNode<T, Any>(keyRef) {
+
+        override fun getValue(): Any = valueStub
+
+        override fun setValue(value: Any) {
+        }
+    }
+
+    private interface InternerKey<T : KInternedObject> {
+        fun get(): T?
+    }
+
+    private class WeakInternerKey<T : KInternedObject>(
+        key: T?, queue: ReferenceQueue<T>?
+    ) : WeakReference<T>(key, queue), InternerKey<T> {
+        private val hashCode: Int = key?.internHashCode() ?: 0
+
+        override fun equals(other: Any?): Boolean = when {
+            other === this -> true
+            other is InternerKey<*> -> KInternedObject.objectEquality(get(), other.get())
+            else -> false
+        }
+
+        override fun hashCode(): Int = hashCode
+
+        override fun toString(): String =
+            "{key=${get()} hash=$hashCode}"
+    }
+
+    private class LookupInternerKey<T : KInternedObject>(
+        private val key: T
+    ) : InternerKey<T> {
+        private val hashCode: Int = key.internHashCode()
+
+        override fun get(): T = key
+
+        override fun equals(other: Any?): Boolean = when {
+            other === this -> true
+            other is InternerKey<*> -> KInternedObject.objectEquality(get(), other.get())
+            else -> false
+        }
+
+        override fun hashCode(): Int = hashCode
+
+        override fun toString(): String =
+            "{key=${get()} hash=$hashCode}"
+    }
+
+    companion object {
+        private val valueStub = Any()
+    }
+}