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
35namespace WebCore {
36namespace IDBServer {
37
38MemoryObjectStoreCursor::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
52void MemoryObjectStoreCursor::objectStoreCleared()
53{
54 m_iterator = WTF::nullopt;
55}
56
57void MemoryObjectStoreCursor::keyDeleted(const IDBKeyData& key)
58{
59 if (m_currentPositionKey != key)
60 return;
61
62 m_iterator = WTF::nullopt;
63}
64
65void MemoryObjectStoreCursor::keyAdded(IDBKeyDataSet::iterator iterator)
66{
67 if (m_iterator)
68 return;
69
70 if (*iterator == m_currentPositionKey)
71 m_iterator = iterator;
72}
73
74void 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
95void 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
133void 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
184void 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), m_objectStore.info().keyPath() };
198 }
199}
200
201void 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
257void 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
317void 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)
357