1 /*
2  * Copyright 2022 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.foundation.gestures
18 
19 import androidx.compose.foundation.gestures.ContentInViewNode.Request
20 import androidx.compose.foundation.internal.checkPrecondition
21 import androidx.compose.runtime.collection.mutableVectorOf
22 import androidx.compose.ui.geometry.Rect
23 import kotlin.contracts.ExperimentalContracts
24 import kotlin.contracts.contract
25 import kotlin.coroutines.resume
26 import kotlinx.coroutines.CancellationException
27 
28 /**
29  * Ongoing requests from [ContentInViewNode.bringChildIntoView], with the invariant that it is
30  * always sorted by overlapping order: each item's bounds completely overlaps the next item.
31  *
32  * Requests are enqueued by calling [enqueue], which inserts the request at the correct position and
33  * cancels and removes any requests that it interrupts. When a request is enqueued, its continuation
34  * has a completion handler set that will remove the request from the queue when it's cancelled.
35  *
36  * One a request has been enqueued, it cannot be removed without completing the continuation. This
37  * helps prevent leaking requests. Requests are removed in two ways:
38  * 1. By an [enqueue] call for a request that doesn't overlap them, or
39  * 2. By calling [cancelAndRemoveAll], which does exactly what it says.
40  */
41 @OptIn(ExperimentalContracts::class)
42 internal class BringIntoViewRequestPriorityQueue {
43     private val requests = mutableVectorOf<Request>()
44 
45     val size: Int
46         get() = requests.size
47 
isEmptynull48     fun isEmpty(): Boolean = requests.isEmpty()
49 
50     /**
51      * Adds [request] to the queue, enforcing the invariants of that list:
52      * - It will be inserted in the correct position to preserve sorted order.
53      * - Any requests not contains by or containing this request will be evicted.
54      *
55      * After this function is called, [request] will always be either resumed or cancelled before
56      * it's removed from the queue, so the caller no longer needs to worry about completing it.
57      *
58      * @return True if the request was enqueued, false if it was not, e.g. because the rect function
59      *   returned null.
60      */
61     fun enqueue(request: Request): Boolean {
62         val requestBounds =
63             request.currentBounds()
64                 ?: run {
65                     request.continuation.resume(Unit)
66                     return false
67                 }
68 
69         // If the request is cancelled for any reason, remove it from the queue.
70         request.continuation.invokeOnCancellation { requests.remove(request) }
71 
72         for (i in requests.indices.reversed()) {
73             val r = requests[i]
74             val rBounds = r.currentBounds() ?: continue
75             val intersection = requestBounds.intersect(rBounds)
76             if (intersection == requestBounds) {
77                 // The current item fully contains the new request, so insert it after.
78                 requests.add(i + 1, request)
79                 return true
80             } else if (intersection != rBounds) {
81                 // The new request and the current item do not fully overlap, so cancel the
82                 // current item and all requests after it, remove them, then continue the
83                 // search to the next-largest request.
84                 val cause =
85                     CancellationException(
86                         "bringIntoView call interrupted by a newer, non-overlapping call"
87                     )
88                 for (j in requests.size - 1..i) {
89                     // This mutates the list while iterating, but since we're iterating
90                     // backwards in both cases, it's fine.
91                     // Cancelling the continuation will remove the request from the queue.
92                     requests[i].continuation.cancel(cause)
93                 }
94             }
95             // Otherwise the new request fully contains the current item, so keep searching up
96             // the queue.
97         }
98 
99         // No existing request contained the new one. Either the new requests contains all
100         // existing requests and it should be the new head of the queue, or all other requests
101         // were removed.
102         requests.add(0, request)
103         return true
104     }
105 
forEachFromSmallestnull106     inline fun forEachFromSmallest(block: (bounds: Rect?) -> Unit) {
107         contract { callsInPlace(block) }
108         requests.forEachReversed { block(it.currentBounds()) }
109     }
110 
resumeAndRemoveAllnull111     fun resumeAndRemoveAll() {
112         for (i in requests.indices) {
113             requests[i].continuation.resume(Unit)
114         }
115         requests.clear()
116     }
117 
resumeAndRemoveWhilenull118     inline fun resumeAndRemoveWhile(block: (bounds: Rect?) -> Boolean) {
119         contract { callsInPlace(block) }
120         while (requests.isNotEmpty()) {
121             if (block(requests.last().currentBounds())) {
122                 requests.removeAt(requests.lastIndex).continuation.resume(Unit)
123             } else {
124                 return
125             }
126         }
127     }
128 
cancelAndRemoveAllnull129     fun cancelAndRemoveAll(cause: Throwable?) {
130         // The continuation completion handler will remove the request from the queue when it's
131         // cancelled, so we need to make a copy of the list before iterating to avoid concurrent
132         // mutation.
133         requests.map { it.continuation }.forEach { it.cancel(cause) }
134         checkPrecondition(requests.isEmpty()) { "uncancelled requests present" }
135     }
136 }
137