1 /*
2  * Copyright 2024 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package androidx.compose.runtime.snapshots
18 
19 import androidx.compose.runtime.Stable
20 import androidx.compose.runtime.external.kotlinx.collections.immutable.PersistentSet
21 import androidx.compose.runtime.external.kotlinx.collections.immutable.persistentSetOf
22 import androidx.compose.runtime.platform.makeSynchronizedObject
23 import androidx.compose.runtime.platform.synchronized
24 import kotlin.js.JsName
25 import kotlin.jvm.JvmName
26 
27 /**
28  * An implementation of [MutableSet] that can be observed and snapshot. This is the result type
29  * created by [androidx.compose.runtime.mutableStateSetOf].
30  *
31  * @see androidx.compose.runtime.mutableStateSetOf
32  */
33 @Stable
34 class SnapshotStateSet<T> : StateObject, MutableSet<T>, RandomAccess {
35     override var firstStateRecord: StateRecord = stateRecordWith(persistentSetOf())
36         private set
37 
prependStateRecordnull38     override fun prependStateRecord(value: StateRecord) {
39         value.next = firstStateRecord
40         @Suppress("UNCHECKED_CAST")
41         firstStateRecord = value as StateSetStateRecord<T>
42     }
43 
44     /**
45      * Return a set containing all the elements of this set.
46      *
47      * The set returned is immutable and returned will not change even if the content of the set is
48      * changed in the same snapshot. It also will be the same instance until the content is changed.
49      * It is not, however, guaranteed to be the same instance for the same set as adding and
50      * removing the same item from the this set might produce a different instance with the same
51      * content.
52      *
53      * This operation is O(1) and does not involve a physically copying the set. It instead returns
54      * the underlying immutable set used internally to store the content of the set.
55      *
56      * It is recommended to use [toSet] when returning the value of this set from
57      * [androidx.compose.runtime.snapshotFlow].
58      */
toSetnull59     fun toSet(): Set<T> = readable.set
60 
61     internal val modification: Int
62         get() = withCurrent { modification }
63 
64     @Suppress("UNCHECKED_CAST")
65     internal val readable: StateSetStateRecord<T>
66         get() = (firstStateRecord as StateSetStateRecord<T>).readable(this)
67 
68     /** This is an internal implementation class of [SnapshotStateSet]. Do not use. */
69     internal class StateSetStateRecord<T>
70     internal constructor(snapshotId: SnapshotId, internal var set: PersistentSet<T>) :
71         StateRecord(snapshotId) {
72         internal var modification = 0
73 
assignnull74         override fun assign(value: StateRecord) {
75             synchronized(sync) {
76                 @Suppress("UNCHECKED_CAST")
77                 set = (value as StateSetStateRecord<T>).set
78                 modification = value.modification
79             }
80         }
81 
createnull82         override fun create(): StateRecord = StateSetStateRecord(currentSnapshot().snapshotId, set)
83 
84         override fun create(snapshotId: SnapshotId): StateRecord =
85             StateSetStateRecord(snapshotId, set)
86     }
87 
88     override val size: Int
89         get() = readable.set.size
90 
91     override fun contains(element: T) = readable.set.contains(element)
92 
93     override fun containsAll(elements: Collection<T>) = readable.set.containsAll(elements)
94 
95     override fun isEmpty() = readable.set.isEmpty()
96 
97     override fun iterator(): MutableIterator<T> = StateSetIterator(this, readable.set.iterator())
98 
99     @Suppress("UNCHECKED_CAST")
100     override fun toString(): String =
101         (firstStateRecord as StateSetStateRecord<T>).withCurrent {
102             "SnapshotStateSet(value=${it.set})@${hashCode()}"
103         }
104 
addnull105     override fun add(element: T) = conditionalUpdate { it.add(element) }
106 
<lambda>null107     override fun addAll(elements: Collection<T>) = conditionalUpdate { it.addAll(elements) }
108 
clearnull109     override fun clear() {
110         writable {
111             synchronized(sync) {
112                 set = persistentSetOf()
113                 modification++
114             }
115         }
116     }
117 
<lambda>null118     override fun remove(element: T) = conditionalUpdate { it.remove(element) }
119 
<lambda>null120     override fun removeAll(elements: Collection<T>) = conditionalUpdate { it.removeAll(elements) }
121 
<lambda>null122     override fun retainAll(elements: Collection<T>) = mutateBoolean {
123         it.retainAll(elements.toSet())
124     }
125 
126     /**
127      * An internal function used by the debugger to display the value of the current set without
128      * triggering read observers.
129      */
130     @Suppress("unused")
131     internal val debuggerDisplayValue: Set<T>
<lambda>null132         @JvmName("getDebuggerDisplayValue") get() = withCurrent { set }
133 
writablenull134     private inline fun <R> writable(block: StateSetStateRecord<T>.() -> R): R =
135         @Suppress("UNCHECKED_CAST")
136         (firstStateRecord as StateSetStateRecord<T>).writable(this, block)
137 
138     private inline fun <R> withCurrent(block: StateSetStateRecord<T>.() -> R): R =
139         @Suppress("UNCHECKED_CAST") (firstStateRecord as StateSetStateRecord<T>).withCurrent(block)
140 
141     private fun mutateBoolean(block: (MutableSet<T>) -> Boolean): Boolean = mutate(block)
142 
143     private inline fun <R> mutate(block: (MutableSet<T>) -> R): R {
144         var result: R
145         while (true) {
146             var oldSet: PersistentSet<T>? = null
147             var currentModification = 0
148             synchronized(sync) {
149                 val current = withCurrent { this }
150                 currentModification = current.modification
151                 oldSet = current.set
152             }
153             val builder = oldSet?.builder() ?: error("No set to mutate")
154             result = block(builder)
155             val newSet = builder.build()
156             if (newSet == oldSet || writable { attemptUpdate(currentModification, newSet) }) break
157         }
158         return result
159     }
160 
<lambda>null161     private inline fun conditionalUpdate(block: (PersistentSet<T>) -> PersistentSet<T>) = run {
162         val result: Boolean
163         while (true) {
164             var oldSet: PersistentSet<T>? = null
165             var currentModification = 0
166             synchronized(sync) {
167                 val current = withCurrent { this }
168                 currentModification = current.modification
169                 oldSet = current.set
170             }
171             val newSet = block(oldSet!!)
172             if (newSet == oldSet) {
173                 result = false
174                 break
175             }
176             if (writable { attemptUpdate(currentModification, newSet) }) {
177                 result = true
178                 break
179             }
180         }
181         result
182     }
183 
184     // NOTE: do not inline this method to avoid class verification failures, see b/369909868
StateSetStateRecordnull185     private fun StateSetStateRecord<T>.attemptUpdate(
186         currentModification: Int,
187         newSet: PersistentSet<T>
188     ): Boolean =
189         synchronized(sync) {
190             if (modification == currentModification) {
191                 set = newSet
192                 modification++
193                 true
194             } else false
195         }
196 
stateRecordWithnull197     private fun stateRecordWith(set: PersistentSet<T>): StateRecord {
198         return StateSetStateRecord(currentSnapshot().snapshotId, set).also {
199             if (Snapshot.isInSnapshot) {
200                 it.next = StateSetStateRecord(Snapshot.PreexistingSnapshotId.toSnapshotId(), set)
201             }
202         }
203     }
204 }
205 
206 /**
207  * This lock is used to ensure that the value of modification and the set in the state record, when
208  * used together, are atomically read and written.
209  *
210  * A global sync object is used to avoid having to allocate a sync object and initialize a monitor
211  * for each instance the set. This avoids additional allocations but introduces some contention
212  * between sets. As there is already contention on the global snapshot lock to write so the
213  * additional contention introduced by this lock is nominal.
214  *
215  * In code the requires this lock and calls `writable` (or other operation that acquires the
216  * snapshot global lock), this lock *MUST* be acquired last to avoid deadlocks. In other words, the
217  * lock must be taken in the `writable` lambda, if `writable` is used.
218  */
219 private val sync = makeSynchronizedObject()
220 
221 private class StateSetIterator<T>(val set: SnapshotStateSet<T>, val iterator: Iterator<T>) :
222     MutableIterator<T> {
223     var current: T? = null
224     @JsName("var_next") var next: T? = null
225     var modification = set.modification
226 
227     init {
228         advance()
229     }
230 
hasNextnull231     override fun hasNext(): Boolean {
232         return next != null
233     }
234 
nextnull235     override fun next(): T {
236         validateModification()
237         advance()
238         return current ?: throw IllegalStateException()
239     }
240 
<lambda>null241     override fun remove() = modify {
242         val value = current
243 
244         if (value != null) {
245             set.remove(value)
246             current = null
247         } else {
248             throw IllegalStateException()
249         }
250     }
251 
advancenull252     private fun advance() {
253         current = next
254         next = if (iterator.hasNext()) iterator.next() else null
255     }
256 
modifynull257     private inline fun <T> modify(block: () -> T): T {
258         validateModification()
259         return block().also { modification = set.modification }
260     }
261 
validateModificationnull262     private fun validateModification() {
263         if (set.modification != modification) {
264             throw ConcurrentModificationException()
265         }
266     }
267 }
268