f8b23ea362ab2fd160dc2524e049f5fe1724a7fb
[WebKit-https.git] / Source / WebCore / Modules / indexeddb / server / MemoryObjectStoreCursor.cpp
1 /*
2  * Copyright (C) 2015 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "MemoryObjectStoreCursor.h"
28
29 #if ENABLE(INDEXED_DATABASE)
30
31 #include "IDBGetResult.h"
32 #include "Logging.h"
33 #include "MemoryObjectStore.h"
34
35 namespace WebCore {
36 namespace IDBServer {
37
38 MemoryObjectStoreCursor::MemoryObjectStoreCursor(MemoryObjectStore& objectStore, const IDBCursorInfo& info)
39     : MemoryCursor(info)
40     , m_objectStore(objectStore)
41     , m_remainingRange(info.range())
42 {
43     LOG(IndexedDB, "MemoryObjectStoreCursor::MemoryObjectStoreCursor %s", info.range().loggingString().utf8().data());
44
45     auto* orderedKeys = objectStore.orderedKeys();
46     if (!orderedKeys)
47         return;
48
49     setFirstInRemainingRange(*orderedKeys);
50 }
51
52 void MemoryObjectStoreCursor::objectStoreCleared()
53 {
54     m_iterator = WTF::nullopt;
55 }
56
57 void MemoryObjectStoreCursor::keyDeleted(const IDBKeyData& key)
58 {
59     if (m_currentPositionKey != key)
60         return;
61
62     m_iterator = WTF::nullopt;
63 }
64
65 void MemoryObjectStoreCursor::keyAdded(IDBKeyDataSet::iterator iterator)
66 {
67     if (m_iterator)
68         return;
69
70     if (*iterator == m_currentPositionKey)
71         m_iterator = iterator;
72 }
73
74 void MemoryObjectStoreCursor::setFirstInRemainingRange(IDBKeyDataSet& set)
75 {
76     m_iterator = WTF::nullopt;
77
78     if (m_info.isDirectionForward()) {
79         setForwardIteratorFromRemainingRange(set);
80         if (m_iterator) {
81             m_remainingRange.lowerKey = **m_iterator;
82             m_remainingRange.lowerOpen = true;
83         }
84     } else {
85         setReverseIteratorFromRemainingRange(set);
86         if (m_iterator) {
87             m_remainingRange.upperKey = **m_iterator;
88             m_remainingRange.upperOpen = true;
89         }
90     }
91
92     ASSERT(!m_iterator || *m_iterator != set.end());
93 }
94
95 void MemoryObjectStoreCursor::setForwardIteratorFromRemainingRange(IDBKeyDataSet& set)
96 {
97     if (!set.size()) {
98         m_iterator = WTF::nullopt;
99         return;
100     }
101
102     if (m_remainingRange.isExactlyOneKey()) {
103         m_iterator = set.find(m_remainingRange.lowerKey);
104         if (*m_iterator == set.end())
105             m_iterator = WTF::nullopt;
106
107         return;
108     }
109
110     m_iterator = WTF::nullopt;
111
112     auto lowest = set.lower_bound(m_remainingRange.lowerKey);
113     if (lowest == set.end())
114         return;
115
116     if (m_remainingRange.lowerOpen && *lowest == m_remainingRange.lowerKey) {
117         ++lowest;
118         if (lowest == set.end())
119             return;
120     }
121
122     if (!m_remainingRange.upperKey.isNull()) {
123         if (lowest->compare(m_remainingRange.upperKey) > 0)
124             return;
125
126         if (m_remainingRange.upperOpen && *lowest == m_remainingRange.upperKey)
127             return;
128     }
129
130     m_iterator = lowest;
131 }
132
133 void MemoryObjectStoreCursor::setReverseIteratorFromRemainingRange(IDBKeyDataSet& set)
134 {
135     if (!set.size()) {
136         m_iterator = WTF::nullopt;
137         return;
138     }
139
140     if (m_remainingRange.isExactlyOneKey()) {
141         m_iterator = set.find(m_remainingRange.lowerKey);
142         if (*m_iterator == set.end())
143             m_iterator = WTF::nullopt;
144
145         return;
146     }
147
148     if (!m_remainingRange.upperKey.isValid()) {
149         m_iterator = --set.end();
150         if (!m_remainingRange.containsKey(**m_iterator))
151             m_iterator = WTF::nullopt;
152
153         return;
154     }
155
156     m_iterator = WTF::nullopt;
157
158     // This is one record past the actual key we're looking for.
159     auto highest = set.upper_bound(m_remainingRange.upperKey);
160
161     if (highest == set.begin())
162         return;
163
164     // This is one record before that, which *is* the key we're looking for.
165     --highest;
166
167     if (m_remainingRange.upperOpen && *highest == m_remainingRange.upperKey) {
168         if (highest == set.begin())
169             return;
170         --highest;
171     }
172
173     if (!m_remainingRange.lowerKey.isNull()) {
174         if (highest->compare(m_remainingRange.lowerKey) < 0)
175             return;
176
177         if (m_remainingRange.lowerOpen && *highest == m_remainingRange.lowerKey)
178             return;
179     }
180
181     m_iterator = highest;
182 }
183
184 void MemoryObjectStoreCursor::currentData(IDBGetResult& data)
185 {
186     if (!m_iterator) {
187         m_currentPositionKey = { };
188         data = { };
189         return;
190     }
191
192     m_currentPositionKey = **m_iterator;
193     if (m_info.cursorType() == IndexedDB::CursorType::KeyOnly)
194         data = { m_currentPositionKey, m_currentPositionKey };
195     else {
196         IDBValue value = { m_objectStore.valueForKeyRange(m_currentPositionKey), { }, { }, { } };
197         data = { m_currentPositionKey, m_currentPositionKey, WTFMove(value) };
198     }
199 }
200
201 void MemoryObjectStoreCursor::incrementForwardIterator(IDBKeyDataSet& set, const IDBKeyData& key, uint32_t count)
202 {
203     // We might need to re-grab the current iterator.
204     // e.g. If the record it was pointed to had been deleted.
205     bool didResetIterator = false;
206     if (!m_iterator) {
207         if (!m_currentPositionKey.isValid())
208             return;
209
210         m_remainingRange.lowerKey = m_currentPositionKey;
211         m_remainingRange.lowerOpen = false;
212         setFirstInRemainingRange(set);
213
214         didResetIterator = true;
215     }
216
217     if (!m_iterator)
218         return;
219
220     ASSERT(*m_iterator != set.end());
221
222     if (key.isValid()) {
223         // If iterating to a key, the count passed in must be zero, as there is no way to iterate by both a count and to a key.
224         ASSERT(!count);
225
226         if (!m_info.range().containsKey(key))
227             return;
228
229         if ((*m_iterator)->compare(key) < 0) {
230             m_remainingRange.lowerKey = key;
231             m_remainingRange.lowerOpen = false;
232             setFirstInRemainingRange(set);
233         }
234
235         return;
236     }
237
238     if (!count)
239         count = 1;
240
241     // If the forwardIterator was reset because it's previous record had been deleted,
242     // we might have already advanced past the current position, eating one one of the iteration counts.
243     if (didResetIterator && (*m_iterator)->compare(m_currentPositionKey) > 0)
244         --count;
245
246     while (count) {
247         --count;
248         ++*m_iterator;
249
250         if (*m_iterator == set.end() || !m_info.range().containsKey(**m_iterator)) {
251             m_iterator = WTF::nullopt;
252             return;
253         }
254     }
255 }
256
257 void MemoryObjectStoreCursor::incrementReverseIterator(IDBKeyDataSet& set, const IDBKeyData& key, uint32_t count)
258 {
259     // We might need to re-grab the current iterator.
260     // e.g. If the record it was pointed to had been deleted.
261     bool didResetIterator = false;
262     if (!m_iterator) {
263         if (!m_currentPositionKey.isValid())
264             return;
265
266         m_remainingRange.upperKey = m_currentPositionKey;
267         m_remainingRange.upperOpen = false;
268         setFirstInRemainingRange(set);
269
270         didResetIterator = true;
271     }
272
273     if (*m_iterator == set.end())
274         return;
275
276     if (key.isValid()) {
277         // If iterating to a key, the count passed in must be zero, as there is no way to iterate by both a count and to a key.
278         ASSERT(!count);
279
280         if (!m_info.range().containsKey(key))
281             return;
282
283         if ((*m_iterator)->compare(key) > 0) {
284             m_remainingRange.upperKey = key;
285             m_remainingRange.upperOpen = false;
286
287             setFirstInRemainingRange(set);
288         }
289
290         return;
291     }
292
293     if (!count)
294         count = 1;
295
296     // If the reverseIterator was reset because it's previous record had been deleted,
297     // we might have already advanced past the current position, eating one one of the iteration counts.
298     if (didResetIterator && (*m_iterator)->compare(m_currentPositionKey) < 0)
299         --count;
300
301     while (count) {
302         if (*m_iterator == set.begin()) {
303             m_iterator = WTF::nullopt;
304             return;
305         }
306
307         --count;
308         --*m_iterator;
309
310         if (!m_info.range().containsKey(**m_iterator)) {
311             m_iterator = WTF::nullopt;
312             return;
313         }
314     }
315 }
316
317 void MemoryObjectStoreCursor::iterate(const IDBKeyData& key, const IDBKeyData& primaryKeyData, uint32_t count, IDBGetResult& outData)
318 {
319     LOG(IndexedDB, "MemoryObjectStoreCursor::iterate to key %s", key.loggingString().utf8().data());
320
321     ASSERT_UNUSED(primaryKeyData, primaryKeyData.isNull());
322
323     if (!m_objectStore.orderedKeys()) {
324         m_currentPositionKey = { };
325         outData = { };
326         return;
327     }
328
329     if (key.isValid() && !m_info.range().containsKey(key)) {
330         m_currentPositionKey = { };
331         outData = { };
332         return;
333     }
334
335     auto* set = m_objectStore.orderedKeys();
336     if (set) {
337         if (m_info.isDirectionForward())
338             incrementForwardIterator(*set, key, count);
339         else
340             incrementReverseIterator(*set, key, count);
341     }
342
343     m_currentPositionKey = { };
344
345     if (!m_iterator) {
346         outData = { };
347         return;
348     }
349
350     currentData(outData);
351 }
352
353 } // namespace IDBServer
354 } // namespace WebCore
355
356 #endif // ENABLE(INDEXED_DATABASE)