Source/WebCore: IndexedDB: Propagate more leveldb errors to IDBIndex and IDBObjectStore
[WebKit-https.git] / Source / WebCore / Modules / indexeddb / IDBBackingStore.cpp
1 /*
2  * Copyright (C) 2011 Google 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  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "IDBBackingStore.h"
28
29 #if ENABLE(INDEXED_DATABASE)
30
31 #include "FileSystem.h"
32 #include "HistogramSupport.h"
33 #include "IDBFactoryBackendImpl.h"
34 #include "IDBKey.h"
35 #include "IDBKeyPath.h"
36 #include "IDBKeyRange.h"
37 #include "IDBLevelDBCoding.h"
38 #include "IDBMetadata.h"
39 #include "IDBTracing.h"
40 #include "LevelDBComparator.h"
41 #include "LevelDBDatabase.h"
42 #include "LevelDBIterator.h"
43 #include "LevelDBSlice.h"
44 #include "LevelDBTransaction.h"
45 #include "SecurityOrigin.h"
46 #include <wtf/Assertions.h>
47
48 namespace WebCore {
49
50 using namespace IDBLevelDBCoding;
51
52 const int64_t KeyGeneratorInitialNumber = 1; // From the IndexedDB specification.
53
54 enum IDBLevelDBBackingStoreInternalErrorType {
55     IDBLevelDBBackingStoreReadError,
56     IDBLevelDBBackingStoreWriteError,
57     IDBLevelDBBackingStoreConsistencyError,
58     IDBLevelDBBackingStoreReadErrorFindKeyInIndex,
59     IDBLevelDBBackingStoreReadErrorGetIDBDatabaseMetaData,
60     IDBLevelDBBackingStoreReadErrorGetIndexes,
61     IDBLevelDBBackingStoreReadErrorGetKeyGeneratorCurrentNumber,
62     IDBLevelDBBackingStoreReadErrorGetObjectStores,
63     IDBLevelDBBackingStoreReadErrorGetRecord,
64     IDBLevelDBBackingStoreReadErrorKeyExistsInObjectStore,
65     IDBLevelDBBackingStoreReadErrorLoadCurrentRow,
66     IDBLevelDBBackingStoreReadErrorSetupMetadata,
67     IDBLevelDBBackingStoreReadErrorGetPrimaryKeyViaIndex,
68     IDBLevelDBBackingStoreReadErrorKeyExistsInIndex,
69     IDBLevelDBBackingStoreReadErrorVersionExists,
70     IDBLevelDBBackingStoreInternalErrorMax,
71 };
72 static inline void recordInternalError(IDBLevelDBBackingStoreInternalErrorType type)
73 {
74     HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.InternalError", type, IDBLevelDBBackingStoreInternalErrorMax);
75 }
76
77 // Use to signal conditions that usually indicate developer error, but could be caused by data corruption.
78 // A macro is used instead of an inline function so that the assert and log report the line number.
79 #define InternalError(type) \
80     do { \
81         ASSERT_NOT_REACHED(); \
82         LOG_ERROR("Internal IndexedDB Error: %s", #type); \
83         recordInternalError(type); \
84     } while (0)
85
86 template <typename DBOrTransaction>
87 static bool getBool(DBOrTransaction* db, const LevelDBSlice& key, bool& foundBool)
88 {
89     Vector<char> result;
90     if (!db->get(key, result))
91         return false;
92
93     foundBool = decodeBool(result.begin(), result.end());
94     return true;
95 }
96
97 static void putBool(LevelDBTransaction* transaction, const LevelDBSlice& key, bool value)
98 {
99     transaction->put(key, encodeBool(value));
100 }
101
102 template <typename DBOrTransaction>
103 static bool getInt(DBOrTransaction* db, const LevelDBSlice& key, int64_t& foundInt)
104 {
105     Vector<char> result;
106     bool found = false;
107     bool ok = db->safeGet(key, result, found);
108     // FIXME: Notify the caller if !ok.
109     ASSERT_UNUSED(ok, ok);
110     if (!found)
111         return false;
112
113     foundInt = decodeInt(result.begin(), result.end());
114     return true;
115 }
116
117 static void putInt(LevelDBTransaction* transaction, const LevelDBSlice& key, int64_t value)
118 {
119     ASSERT(value >= 0);
120     transaction->put(key, encodeInt(value));
121 }
122
123 template <typename DBOrTransaction>
124 static bool getVarInt(DBOrTransaction* db, const LevelDBSlice& key, int64_t& foundInt)
125 {
126     Vector<char> result;
127     bool found = false;
128     bool ok = db->safeGet(key, result, found);
129     // FIXME: Notify the caller if !ok.
130     ASSERT_UNUSED(ok, ok);
131     if (!found)
132         return false;
133
134     return decodeVarInt(result.begin(), result.end(), foundInt) == result.end();
135 }
136
137 static void putVarInt(LevelDBTransaction* transaction, const LevelDBSlice& key, int64_t value)
138 {
139     transaction->put(key, encodeVarInt(value));
140 }
141
142 template <typename DBOrTransaction>
143 static bool getString(DBOrTransaction* db, const LevelDBSlice& key, String& foundString)
144 {
145     Vector<char> result;
146     bool found = false;
147     bool ok = db->safeGet(key, result, found);
148     // FIXME: Notify the caller if !ok.
149     ASSERT_UNUSED(ok, ok);
150     if (!found)
151         return false;
152
153     foundString = decodeString(result.begin(), result.end());
154     return true;
155 }
156
157 static void putString(LevelDBTransaction* transaction, const LevelDBSlice& key, const String& value)
158 {
159     transaction->put(key, encodeString(value));
160 }
161
162 static void putIDBKeyPath(LevelDBTransaction* transaction, const LevelDBSlice& key, const IDBKeyPath& value)
163 {
164     transaction->put(key, encodeIDBKeyPath(value));
165 }
166
167 static int compareKeys(const LevelDBSlice& a, const LevelDBSlice& b)
168 {
169     return compare(a, b);
170 }
171
172 static int compareIndexKeys(const LevelDBSlice& a, const LevelDBSlice& b)
173 {
174     return compare(a, b, true);
175 }
176
177 class Comparator : public LevelDBComparator {
178 public:
179     virtual int compare(const LevelDBSlice& a, const LevelDBSlice& b) const { return IDBLevelDBCoding::compare(a, b); }
180     virtual const char* name() const { return "idb_cmp1"; }
181 };
182
183 const int64_t latestSchemaVersion = 1;
184 static bool isSchemaKnown(LevelDBDatabase* db)
185 {
186     int64_t schemaVersion = 0;
187     const Vector<char> metaDataKey = SchemaVersionKey::encode();
188     if (!getInt(db, metaDataKey, schemaVersion))
189         return true;
190     return schemaVersion <= latestSchemaVersion;
191 }
192
193 static bool setUpMetadata(LevelDBDatabase* db, const String& origin)
194 {
195     const Vector<char> metaDataKey = SchemaVersionKey::encode();
196     RefPtr<LevelDBTransaction> transaction = LevelDBTransaction::create(db);
197
198     int64_t schemaVersion = 0;
199     if (!getInt(transaction.get(), metaDataKey, schemaVersion)) {
200         schemaVersion = latestSchemaVersion;
201         putInt(transaction.get(), metaDataKey, latestSchemaVersion);
202     } else {
203         ASSERT(schemaVersion <= latestSchemaVersion);
204         if (!schemaVersion) {
205             schemaVersion = latestSchemaVersion;
206             putInt(transaction.get(), metaDataKey, schemaVersion);
207             const Vector<char> startKey = DatabaseNameKey::encodeMinKeyForOrigin(origin);
208             const Vector<char> stopKey = DatabaseNameKey::encodeStopKeyForOrigin(origin);
209             OwnPtr<LevelDBIterator> it = db->createIterator();
210             for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
211                 int64_t databaseId = 0;
212                 if (!getInt(transaction.get(), it->key(), databaseId)) {
213                     InternalError(IDBLevelDBBackingStoreReadErrorSetupMetadata);
214                     return false;
215                 }
216                 Vector<char> intVersionKey = DatabaseMetaDataKey::encode(databaseId, DatabaseMetaDataKey::UserIntVersion);
217                 putVarInt(transaction.get(), intVersionKey, IDBDatabaseMetadata::DefaultIntVersion);
218             }
219         }
220     }
221
222     ASSERT(schemaVersion == latestSchemaVersion);
223     if (!transaction->commit()) {
224         InternalError(IDBLevelDBBackingStoreWriteError);
225         return false;
226     }
227     return true;
228 }
229
230 template <typename DBOrTransaction>
231 static int64_t getMaxObjectStoreId(DBOrTransaction* db, int64_t databaseId)
232 {
233     const Vector<char> maxObjectStoreIdKey = DatabaseMetaDataKey::encode(databaseId, DatabaseMetaDataKey::MaxObjectStoreId);
234     return getMaxObjectStoreId(db, maxObjectStoreIdKey);
235 }
236
237 template <typename DBOrTransaction>
238 static int64_t getMaxObjectStoreId(DBOrTransaction* db, const Vector<char>& maxObjectStoreIdKey)
239 {
240     int64_t maxObjectStoreId = -1;
241     if (!getInt(db, maxObjectStoreIdKey, maxObjectStoreId))
242         maxObjectStoreId = 0;
243
244     ASSERT(maxObjectStoreId >= 0);
245     return maxObjectStoreId;
246 }
247
248 IDBBackingStore::IDBBackingStore(const String& identifier, IDBFactoryBackendImpl* factory, PassOwnPtr<LevelDBDatabase> db)
249     : m_identifier(identifier)
250     , m_factory(factory)
251     , m_db(db)
252 {
253     m_factory->addIDBBackingStore(identifier, this);
254 }
255
256 IDBBackingStore::IDBBackingStore()
257 {
258 }
259
260 IDBBackingStore::~IDBBackingStore()
261 {
262     // Only null in tests.
263     if (m_factory)
264         m_factory->removeIDBBackingStore(m_identifier);
265
266     // m_db's destructor uses m_comparator. The order of destruction is important.
267     m_db.clear();
268     m_comparator.clear();
269 }
270
271 enum IDBLevelDBBackingStoreOpenResult {
272     IDBLevelDBBackingStoreOpenMemory,
273     IDBLevelDBBackingStoreOpenSuccess,
274     IDBLevelDBBackingStoreOpenFailedDirectory,
275     IDBLevelDBBackingStoreOpenFailedUnknownSchema,
276     IDBLevelDBBackingStoreOpenCleanupDestroyFailed,
277     IDBLevelDBBackingStoreOpenCleanupReopenFailed,
278     IDBLevelDBBackingStoreOpenCleanupReopenSuccess,
279     IDBLevelDBBackingStoreOpenMax,
280 };
281
282 PassRefPtr<IDBBackingStore> IDBBackingStore::open(SecurityOrigin* securityOrigin, const String& pathBaseArg, const String& fileIdentifier, IDBFactoryBackendImpl* factory)
283 {
284     IDB_TRACE("IDBBackingStore::open");
285     String pathBase = pathBaseArg;
286
287     OwnPtr<LevelDBComparator> comparator = adoptPtr(new Comparator());
288     OwnPtr<LevelDBDatabase> db;
289
290     if (pathBase.isEmpty()) {
291         HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenMemory, IDBLevelDBBackingStoreOpenMax);
292         db = LevelDBDatabase::openInMemory(comparator.get());
293     } else {
294         if (!makeAllDirectories(pathBase)) {
295             LOG_ERROR("Unable to create IndexedDB database path %s", pathBase.utf8().data());
296             HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenFailedDirectory, IDBLevelDBBackingStoreOpenMax);
297             return PassRefPtr<IDBBackingStore>();
298         }
299
300         String path = pathByAppendingComponent(pathBase, securityOrigin->databaseIdentifier() + ".indexeddb.leveldb");
301
302         db = LevelDBDatabase::open(path, comparator.get());
303         if (db && !isSchemaKnown(db.get())) {
304             LOG_ERROR("IndexedDB backing store had unknown schema, treating it as failure to open");
305             HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenFailedUnknownSchema, IDBLevelDBBackingStoreOpenMax);
306             db.clear();
307         }
308
309         if (db)
310             HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenSuccess, IDBLevelDBBackingStoreOpenMax);
311         else {
312             LOG_ERROR("IndexedDB backing store open failed, attempting cleanup");
313             bool success = LevelDBDatabase::destroy(path);
314             if (!success) {
315                 LOG_ERROR("IndexedDB backing store cleanup failed");
316                 HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenCleanupDestroyFailed, IDBLevelDBBackingStoreOpenMax);
317                 return PassRefPtr<IDBBackingStore>();
318             }
319
320             LOG_ERROR("IndexedDB backing store cleanup succeeded, reopening");
321             db = LevelDBDatabase::open(path, comparator.get());
322             if (!db) {
323                 LOG_ERROR("IndexedDB backing store reopen after recovery failed");
324                 HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenCleanupReopenFailed, IDBLevelDBBackingStoreOpenMax);
325                 return PassRefPtr<IDBBackingStore>();
326             }
327             HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenCleanupReopenSuccess, IDBLevelDBBackingStoreOpenMax);
328         }
329     }
330
331     if (!db)
332         return PassRefPtr<IDBBackingStore>();
333
334     // FIXME: Handle comparator name changes.
335
336     RefPtr<IDBBackingStore> backingStore(adoptRef(new IDBBackingStore(fileIdentifier, factory, db.release())));
337     backingStore->m_comparator = comparator.release();
338
339     if (!setUpMetadata(backingStore->m_db.get(), fileIdentifier))
340         return PassRefPtr<IDBBackingStore>();
341
342     return backingStore.release();
343 }
344
345 Vector<String> IDBBackingStore::getDatabaseNames()
346 {
347     Vector<String> foundNames;
348     const Vector<char> startKey = DatabaseNameKey::encodeMinKeyForOrigin(m_identifier);
349     const Vector<char> stopKey = DatabaseNameKey::encodeStopKeyForOrigin(m_identifier);
350
351     ASSERT(foundNames.isEmpty());
352
353     OwnPtr<LevelDBIterator> it = m_db->createIterator();
354     for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
355         const char* p = it->key().begin();
356         const char* limit = it->key().end();
357
358         DatabaseNameKey databaseNameKey;
359         p = DatabaseNameKey::decode(p, limit, &databaseNameKey);
360         ASSERT(p);
361
362         foundNames.append(databaseNameKey.databaseName());
363     }
364     return foundNames;
365 }
366
367 bool IDBBackingStore::getIDBDatabaseMetaData(const String& name, IDBDatabaseMetadata* metadata)
368 {
369     const Vector<char> key = DatabaseNameKey::encode(m_identifier, name);
370
371     bool ok = getInt(m_db.get(), key, metadata->id);
372     if (!ok)
373         return false;
374
375     ok = getString(m_db.get(), DatabaseMetaDataKey::encode(metadata->id, DatabaseMetaDataKey::UserVersion), metadata->version);
376     if (!ok) {
377         InternalError(IDBLevelDBBackingStoreReadErrorGetIDBDatabaseMetaData);
378         return false;
379     }
380
381     ok = getVarInt(m_db.get(), DatabaseMetaDataKey::encode(metadata->id, DatabaseMetaDataKey::UserIntVersion), metadata->intVersion);
382     if (!ok) {
383         InternalError(IDBLevelDBBackingStoreReadErrorGetIDBDatabaseMetaData);
384         return false;
385     }
386     if (metadata->intVersion == IDBDatabaseMetadata::DefaultIntVersion)
387         metadata->intVersion = IDBDatabaseMetadata::NoIntVersion;
388
389     metadata->maxObjectStoreId = getMaxObjectStoreId(m_db.get(), metadata->id);
390
391     return true;
392 }
393
394 static int64_t getNewDatabaseId(LevelDBDatabase* db)
395 {
396     RefPtr<LevelDBTransaction> transaction = LevelDBTransaction::create(db);
397
398     int64_t maxDatabaseId = -1;
399     if (!getInt(transaction.get(), MaxDatabaseIdKey::encode(), maxDatabaseId))
400         maxDatabaseId = 0;
401
402     ASSERT(maxDatabaseId >= 0);
403
404     int64_t databaseId = maxDatabaseId + 1;
405     putInt(transaction.get(), MaxDatabaseIdKey::encode(), databaseId);
406     if (!transaction->commit()) {
407         InternalError(IDBLevelDBBackingStoreWriteError);
408         return -1;
409     }
410     return databaseId;
411 }
412
413 bool IDBBackingStore::createIDBDatabaseMetaData(const String& name, const String& version, int64_t intVersion, int64_t& rowId)
414 {
415     rowId = getNewDatabaseId(m_db.get());
416     if (rowId < 0)
417         return false;
418
419     if (intVersion == IDBDatabaseMetadata::NoIntVersion)
420         intVersion = IDBDatabaseMetadata::DefaultIntVersion;
421
422     RefPtr<LevelDBTransaction> transaction = LevelDBTransaction::create(m_db.get());
423     putInt(transaction.get(), DatabaseNameKey::encode(m_identifier, name), rowId);
424     putString(transaction.get(), DatabaseMetaDataKey::encode(rowId, DatabaseMetaDataKey::UserVersion), version);
425     putVarInt(transaction.get(), DatabaseMetaDataKey::encode(rowId, DatabaseMetaDataKey::UserIntVersion), intVersion);
426     if (!transaction->commit()) {
427         InternalError(IDBLevelDBBackingStoreWriteError);
428         return false;
429     }
430     return true;
431 }
432
433 bool IDBBackingStore::updateIDBDatabaseIntVersion(IDBBackingStore::Transaction* transaction, int64_t rowId, int64_t intVersion)
434 {
435     if (intVersion == IDBDatabaseMetadata::NoIntVersion)
436         intVersion = IDBDatabaseMetadata::DefaultIntVersion;
437     ASSERT_WITH_MESSAGE(intVersion >= 0, "intVersion was %lld", static_cast<long long>(intVersion));
438     putVarInt(Transaction::levelDBTransactionFrom(transaction), DatabaseMetaDataKey::encode(rowId, DatabaseMetaDataKey::UserIntVersion), intVersion);
439     return true;
440 }
441
442 bool IDBBackingStore::updateIDBDatabaseMetaData(IDBBackingStore::Transaction* transaction, int64_t rowId, const String& version)
443 {
444     putString(Transaction::levelDBTransactionFrom(transaction), DatabaseMetaDataKey::encode(rowId, DatabaseMetaDataKey::UserVersion), version);
445     return true;
446 }
447
448 static void deleteRange(LevelDBTransaction* transaction, const Vector<char>& begin, const Vector<char>& end)
449 {
450     OwnPtr<LevelDBIterator> it = transaction->createIterator();
451     for (it->seek(begin); it->isValid() && compareKeys(it->key(), end) < 0; it->next())
452         transaction->remove(it->key());
453 }
454
455
456 bool IDBBackingStore::deleteDatabase(const String& name)
457 {
458     IDB_TRACE("IDBBackingStore::deleteDatabase");
459     OwnPtr<LevelDBWriteOnlyTransaction> transaction = LevelDBWriteOnlyTransaction::create(m_db.get());
460
461     IDBDatabaseMetadata metadata;
462     if (!getIDBDatabaseMetaData(name, &metadata))
463         return true;
464
465     const Vector<char> startKey = DatabaseMetaDataKey::encode(metadata.id, DatabaseMetaDataKey::OriginName);
466     const Vector<char> stopKey = DatabaseMetaDataKey::encode(metadata.id + 1, DatabaseMetaDataKey::OriginName);
467     OwnPtr<LevelDBIterator> it = m_db->createIterator();
468     for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next())
469         transaction->remove(it->key());
470
471     const Vector<char> key = DatabaseNameKey::encode(m_identifier, name);
472     transaction->remove(key);
473
474     return transaction->commit();
475 }
476
477 static bool checkObjectStoreAndMetaDataType(const LevelDBIterator* it, const Vector<char>& stopKey, int64_t objectStoreId, int64_t metaDataType)
478 {
479     if (!it->isValid() || compareKeys(it->key(), stopKey) >= 0)
480         return false;
481
482     ObjectStoreMetaDataKey metaDataKey;
483     const char* p = ObjectStoreMetaDataKey::decode(it->key().begin(), it->key().end(), &metaDataKey);
484     ASSERT_UNUSED(p, p);
485     if (metaDataKey.objectStoreId() != objectStoreId)
486         return false;
487     if (metaDataKey.metaDataType() != metaDataType)
488         return false;
489     return true;
490 }
491
492 Vector<IDBObjectStoreMetadata> IDBBackingStore::getObjectStores(int64_t databaseId)
493 {
494     IDB_TRACE("IDBBackingStore::getObjectStores");
495     Vector<IDBObjectStoreMetadata> objectStores;
496     const Vector<char> startKey = ObjectStoreMetaDataKey::encode(databaseId, 1, 0);
497     const Vector<char> stopKey = ObjectStoreMetaDataKey::encodeMaxKey(databaseId);
498
499     OwnPtr<LevelDBIterator> it = m_db->createIterator();
500     it->seek(startKey);
501     while (it->isValid() && compareKeys(it->key(), stopKey) < 0) {
502         const char* p = it->key().begin();
503         const char* limit = it->key().end();
504
505         ObjectStoreMetaDataKey metaDataKey;
506         p = ObjectStoreMetaDataKey::decode(p, limit, &metaDataKey);
507         ASSERT(p);
508         if (metaDataKey.metaDataType() != ObjectStoreMetaDataKey::Name) {
509             InternalError(IDBLevelDBBackingStoreReadErrorGetObjectStores);
510             // Possible stale metadata, but don't fail the load.
511             it->next();
512             continue;
513         }
514
515         int64_t objectStoreId = metaDataKey.objectStoreId();
516
517         // FIXME: Do this by direct key lookup rather than iteration, to simplify.
518         String objectStoreName = decodeString(it->value().begin(), it->value().end());
519
520         it->next();
521         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::KeyPath)) {
522             InternalError(IDBLevelDBBackingStoreReadErrorGetObjectStores);
523             break;
524         }
525         IDBKeyPath keyPath = decodeIDBKeyPath(it->value().begin(), it->value().end());
526
527         it->next();
528         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::AutoIncrement)) {
529             InternalError(IDBLevelDBBackingStoreReadErrorGetObjectStores);
530             break;
531         }
532         bool autoIncrement = decodeBool(it->value().begin(), it->value().end());
533
534         it->next(); // Is evicatble.
535         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::Evictable)) {
536             InternalError(IDBLevelDBBackingStoreReadErrorGetObjectStores);
537             break;
538         }
539
540         it->next(); // Last version.
541         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::LastVersion)) {
542             InternalError(IDBLevelDBBackingStoreReadErrorGetObjectStores);
543             break;
544         }
545
546         it->next(); // Maximum index id allocated.
547         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::MaxIndexId)) {
548             InternalError(IDBLevelDBBackingStoreReadErrorGetObjectStores);
549             break;
550         }
551         int64_t maxIndexId = decodeInt(it->value().begin(), it->value().end());
552
553         it->next(); // [optional] has key path (is not null)
554         if (checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::HasKeyPath)) {
555             bool hasKeyPath = decodeBool(it->value().begin(), it->value().end());
556             // This check accounts for two layers of legacy coding:
557             // (1) Initially, hasKeyPath was added to distinguish null vs. string.
558             // (2) Later, null vs. string vs. array was stored in the keyPath itself.
559             // So this check is only relevant for string-type keyPaths.
560             if (!hasKeyPath && (keyPath.type() == IDBKeyPath::StringType && !keyPath.string().isEmpty())) {
561                 InternalError(IDBLevelDBBackingStoreReadErrorGetObjectStores);
562                 break;
563             }
564             if (!hasKeyPath)
565                 keyPath = IDBKeyPath();
566             it->next();
567         }
568
569         int64_t keyGeneratorCurrentNumber = -1;
570         if (checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber)) {
571             keyGeneratorCurrentNumber = decodeInt(it->value().begin(), it->value().end());
572             // FIXME: Return keyGeneratorCurrentNumber, cache in object store, and write lazily to backing store.
573             // For now, just assert that if it was written it was valid.
574             ASSERT_UNUSED(keyGeneratorCurrentNumber, keyGeneratorCurrentNumber >= KeyGeneratorInitialNumber);
575             it->next();
576         }
577
578         objectStores.append(IDBObjectStoreMetadata(objectStoreName, objectStoreId, keyPath, autoIncrement, maxIndexId));
579     }
580     return objectStores;
581 }
582
583 static bool setMaxObjectStoreId(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId)
584 {
585     const Vector<char> maxObjectStoreIdKey = DatabaseMetaDataKey::encode(databaseId, DatabaseMetaDataKey::MaxObjectStoreId);
586     int64_t maxObjectStoreId = getMaxObjectStoreId(transaction, maxObjectStoreIdKey);
587
588     if (objectStoreId <= maxObjectStoreId) {
589         InternalError(IDBLevelDBBackingStoreConsistencyError);
590         return false;
591     }
592     putInt(transaction, maxObjectStoreIdKey, objectStoreId);
593     return true;
594 }
595
596 bool IDBBackingStore::createObjectStore(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const String& name, const IDBKeyPath& keyPath, bool autoIncrement)
597 {
598     IDB_TRACE("IDBBackingStore::createObjectStore");
599     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
600     if (!setMaxObjectStoreId(levelDBTransaction, databaseId, objectStoreId))
601         return false;
602
603     const Vector<char> nameKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::Name);
604     const Vector<char> keyPathKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyPath);
605     const Vector<char> autoIncrementKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::AutoIncrement);
606     const Vector<char> evictableKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::Evictable);
607     const Vector<char> lastVersionKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::LastVersion);
608     const Vector<char> maxIndexIdKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::MaxIndexId);
609     const Vector<char> hasKeyPathKey  = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::HasKeyPath);
610     const Vector<char> keyGeneratorCurrentNumberKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber);
611     const Vector<char> namesKey = ObjectStoreNamesKey::encode(databaseId, name);
612
613     putString(levelDBTransaction, nameKey, name);
614     putIDBKeyPath(levelDBTransaction, keyPathKey, keyPath);
615     putInt(levelDBTransaction, autoIncrementKey, autoIncrement);
616     putInt(levelDBTransaction, evictableKey, false);
617     putInt(levelDBTransaction, lastVersionKey, 1);
618     putInt(levelDBTransaction, maxIndexIdKey, MinimumIndexId);
619     putBool(levelDBTransaction, hasKeyPathKey, !keyPath.isNull());
620     putInt(levelDBTransaction, keyGeneratorCurrentNumberKey, KeyGeneratorInitialNumber);
621     putInt(levelDBTransaction, namesKey, objectStoreId);
622     return true;
623 }
624
625 void IDBBackingStore::deleteObjectStore(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId)
626 {
627     IDB_TRACE("IDBBackingStore::deleteObjectStore");
628     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
629
630     String objectStoreName;
631     getString(levelDBTransaction, ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::Name), objectStoreName);
632
633     deleteRange(levelDBTransaction, ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, 0), ObjectStoreMetaDataKey::encodeMaxKey(databaseId, objectStoreId));
634
635     levelDBTransaction->remove(ObjectStoreNamesKey::encode(databaseId, objectStoreName));
636
637     deleteRange(levelDBTransaction, IndexFreeListKey::encode(databaseId, objectStoreId, 0), IndexFreeListKey::encodeMaxKey(databaseId, objectStoreId));
638     deleteRange(levelDBTransaction, IndexMetaDataKey::encode(databaseId, objectStoreId, 0, 0), IndexMetaDataKey::encodeMaxKey(databaseId, objectStoreId));
639
640     clearObjectStore(transaction, databaseId, objectStoreId);
641 }
642
643 bool IDBBackingStore::getRecord(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKey& key, String& record)
644 {
645     IDB_TRACE("IDBBackingStore::getRecord");
646     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
647
648     const Vector<char> leveldbKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
649     Vector<char> data;
650
651     bool found = false;
652     bool ok = levelDBTransaction->safeGet(leveldbKey, data, found);
653     if (!ok) {
654         record = String();
655         InternalError(IDBLevelDBBackingStoreReadErrorGetRecord);
656         return false;
657     }
658
659     int64_t version;
660     const char* p = decodeVarInt(data.begin(), data.end(), version);
661     if (!p) {
662         InternalError(IDBLevelDBBackingStoreReadErrorGetRecord);
663         record = String();
664         return false;
665     }
666
667     record = decodeString(p, data.end());
668     return true;
669 }
670
671 static int64_t getNewVersionNumber(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId)
672 {
673     const Vector<char> lastVersionKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::LastVersion);
674
675     int64_t lastVersion = -1;
676     if (!getInt(transaction, lastVersionKey, lastVersion))
677         lastVersion = 0;
678
679     ASSERT(lastVersion >= 0);
680
681     int64_t version = lastVersion + 1;
682     putInt(transaction, lastVersionKey, version);
683
684     ASSERT(version > lastVersion); // FIXME: Think about how we want to handle the overflow scenario.
685
686     return version;
687 }
688
689 void IDBBackingStore::putRecord(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKey& key, const String& value, RecordIdentifier* recordIdentifier)
690 {
691     IDB_TRACE("IDBBackingStore::putRecord");
692     ASSERT(key.isValid());
693     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
694     int64_t version = getNewVersionNumber(levelDBTransaction, databaseId, objectStoreId);
695     const Vector<char> objectStoredataKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
696
697     Vector<char> v;
698     v.append(encodeVarInt(version));
699     v.append(encodeString(value));
700
701     levelDBTransaction->put(objectStoredataKey, v);
702
703     const Vector<char> existsEntryKey = ExistsEntryKey::encode(databaseId, objectStoreId, key);
704     levelDBTransaction->put(existsEntryKey, encodeInt(version));
705
706     recordIdentifier->reset(encodeIDBKey(key), version);
707 }
708
709 void IDBBackingStore::clearObjectStore(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId)
710 {
711     IDB_TRACE("IDBBackingStore::clearObjectStore");
712     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
713     const Vector<char> startKey = KeyPrefix(databaseId, objectStoreId, 0).encode();
714     const Vector<char> stopKey = KeyPrefix(databaseId, objectStoreId + 1, 0).encode();
715
716     deleteRange(levelDBTransaction, startKey, stopKey);
717 }
718
719 void IDBBackingStore::deleteRecord(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const RecordIdentifier& recordIdentifier)
720 {
721     IDB_TRACE("IDBBackingStore::deleteRecord");
722     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
723
724     const Vector<char> objectStoreDataKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, recordIdentifier.primaryKey());
725     levelDBTransaction->remove(objectStoreDataKey);
726
727     const Vector<char> existsEntryKey = ExistsEntryKey::encode(databaseId, objectStoreId, recordIdentifier.primaryKey());
728     levelDBTransaction->remove(existsEntryKey);
729 }
730
731
732 bool IDBBackingStore::getKeyGeneratorCurrentNumber(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t& keyGeneratorCurrentNumber)
733 {
734     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
735
736     const Vector<char> keyGeneratorCurrentNumberKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber);
737
738     keyGeneratorCurrentNumber = -1;
739     Vector<char> data;
740
741     bool found = false;
742     bool ok = levelDBTransaction->safeGet(keyGeneratorCurrentNumberKey, data, found);
743     if (!ok) {
744         InternalError(IDBLevelDBBackingStoreReadErrorGetKeyGeneratorCurrentNumber);
745         return false;
746     }
747     if (found)
748         keyGeneratorCurrentNumber = decodeInt(data.begin(), data.end());
749     else {
750         // Previously, the key generator state was not stored explicitly but derived from the
751         // maximum numeric key present in existing data. This violates the spec as the data may
752         // be cleared but the key generator state must be preserved.
753         const Vector<char> startKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, minIDBKey());
754         const Vector<char> stopKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, maxIDBKey());
755
756         OwnPtr<LevelDBIterator> it = levelDBTransaction->createIterator();
757         int64_t maxNumericKey = 0;
758
759         for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
760             const char* p = it->key().begin();
761             const char* limit = it->key().end();
762
763             ObjectStoreDataKey dataKey;
764             p = ObjectStoreDataKey::decode(p, limit, &dataKey);
765             ASSERT(p);
766
767             if (dataKey.userKey()->type() == IDBKey::NumberType) {
768                 int64_t n = static_cast<int64_t>(dataKey.userKey()->number());
769                 if (n > maxNumericKey)
770                     maxNumericKey = n;
771             }
772         }
773
774         keyGeneratorCurrentNumber = maxNumericKey + 1;
775     }
776
777     return keyGeneratorCurrentNumber;
778 }
779
780 bool IDBBackingStore::maybeUpdateKeyGeneratorCurrentNumber(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t newNumber, bool checkCurrent)
781 {
782     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
783
784     if (checkCurrent) {
785         int64_t currentNumber;
786         bool ok = getKeyGeneratorCurrentNumber(transaction, databaseId, objectStoreId, currentNumber);
787         if (!ok)
788             return false;
789         if (newNumber <= currentNumber)
790             return true;
791     }
792
793     const Vector<char> keyGeneratorCurrentNumberKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber);
794     putInt(levelDBTransaction, keyGeneratorCurrentNumberKey, newNumber);
795     return true;
796 }
797
798 bool IDBBackingStore::keyExistsInObjectStore(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKey& key, RecordIdentifier* foundRecordIdentifier, bool& found)
799 {
800     IDB_TRACE("IDBBackingStore::keyExistsInObjectStore");
801     found = false;
802     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
803     const Vector<char> leveldbKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
804     Vector<char> data;
805
806     bool ok = levelDBTransaction->safeGet(leveldbKey, data, found);
807     if (!ok) {
808         InternalError(IDBLevelDBBackingStoreReadErrorKeyExistsInObjectStore);
809         return false;
810     }
811     if (!found)
812         return true;
813
814     int64_t version;
815     if (!decodeVarInt(data.begin(), data.end(), version))
816         return false;
817
818     foundRecordIdentifier->reset(encodeIDBKey(key), version);
819     return true;
820 }
821
822 static bool checkIndexAndMetaDataKey(const LevelDBIterator* it, const Vector<char>& stopKey, int64_t indexId, unsigned char metaDataType)
823 {
824     if (!it->isValid() || compareKeys(it->key(), stopKey) >= 0)
825         return false;
826
827     IndexMetaDataKey metaDataKey;
828     const char* p = IndexMetaDataKey::decode(it->key().begin(), it->key().end(), &metaDataKey);
829     ASSERT_UNUSED(p, p);
830     if (metaDataKey.indexId() != indexId)
831         return false;
832     if (metaDataKey.metaDataType() != metaDataType)
833         return false;
834     return true;
835 }
836
837
838 Vector<IDBIndexMetadata> IDBBackingStore::getIndexes(int64_t databaseId, int64_t objectStoreId)
839 {
840     IDB_TRACE("IDBBackingStore::getIndexes");
841     Vector<IDBIndexMetadata> indexes;
842     const Vector<char> startKey = IndexMetaDataKey::encode(databaseId, objectStoreId, 0, 0);
843     const Vector<char> stopKey = IndexMetaDataKey::encode(databaseId, objectStoreId + 1, 0, 0);
844
845     ASSERT(indexes.isEmpty());
846
847     OwnPtr<LevelDBIterator> it = m_db->createIterator();
848     it->seek(startKey);
849     while (it->isValid() && compareKeys(it->key(), stopKey) < 0) {
850         const char* p = it->key().begin();
851         const char* limit = it->key().end();
852
853         IndexMetaDataKey metaDataKey;
854         p = IndexMetaDataKey::decode(p, limit, &metaDataKey);
855         ASSERT(p);
856         if (metaDataKey.metaDataType() != IndexMetaDataKey::Name) {
857             InternalError(IDBLevelDBBackingStoreReadErrorGetIndexes);
858             // Possible stale metadata due to http://webkit.org/b/85557 but don't fail the load.
859             it->next();
860             continue;
861         }
862
863         // FIXME: Do this by direct key lookup rather than iteration, to simplify.
864         int64_t indexId = metaDataKey.indexId();
865         String indexName = decodeString(it->value().begin(), it->value().end());
866
867         it->next(); // unique flag
868         if (!checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::Unique)) {
869             InternalError(IDBLevelDBBackingStoreReadErrorGetIndexes);
870             break;
871         }
872         bool indexUnique = decodeBool(it->value().begin(), it->value().end());
873
874         it->next(); // keyPath
875         if (!checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::KeyPath)) {
876             InternalError(IDBLevelDBBackingStoreReadErrorGetIndexes);
877             break;
878         }
879         IDBKeyPath keyPath = decodeIDBKeyPath(it->value().begin(), it->value().end());
880
881         it->next(); // [optional] multiEntry flag
882         bool indexMultiEntry = false;
883         if (checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::MultiEntry)) {
884             indexMultiEntry = decodeBool(it->value().begin(), it->value().end());
885             it->next();
886         }
887
888         indexes.append(IDBIndexMetadata(indexName, indexId, keyPath, indexUnique, indexMultiEntry));
889     }
890     return indexes;
891 }
892
893 static bool setMaxIndexId(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId)
894 {
895     int64_t maxIndexId = -1;
896     const Vector<char> maxIndexIdKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::MaxIndexId);
897     if (!getInt(transaction, maxIndexIdKey, maxIndexId))
898         maxIndexId = MinimumIndexId;
899
900     if (indexId <= maxIndexId) {
901         InternalError(IDBLevelDBBackingStoreConsistencyError);
902         return false;
903     }
904
905     putInt(transaction, maxIndexIdKey, indexId);
906     return true;
907 }
908
909 bool IDBBackingStore::createIndex(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const String& name, const IDBKeyPath& keyPath, bool isUnique, bool isMultiEntry)
910 {
911     IDB_TRACE("IDBBackingStore::createIndex");
912     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
913     if (!setMaxIndexId(levelDBTransaction, databaseId, objectStoreId, indexId))
914         return false;
915
916     const Vector<char> nameKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::Name);
917     const Vector<char> uniqueKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::Unique);
918     const Vector<char> keyPathKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::KeyPath);
919     const Vector<char> multiEntryKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::MultiEntry);
920
921     putString(levelDBTransaction, nameKey, name);
922     putBool(levelDBTransaction, uniqueKey, isUnique);
923     putIDBKeyPath(levelDBTransaction, keyPathKey, keyPath);
924     putBool(levelDBTransaction, multiEntryKey, isMultiEntry);
925     return true;
926 }
927
928 void IDBBackingStore::deleteIndex(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId)
929 {
930     IDB_TRACE("IDBBackingStore::deleteIndex");
931     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
932
933     const Vector<char> indexMetaDataStart = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, 0);
934     const Vector<char> indexMetaDataEnd = IndexMetaDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
935     deleteRange(levelDBTransaction, indexMetaDataStart, indexMetaDataEnd);
936
937     const Vector<char> indexDataStart = IndexDataKey::encodeMinKey(databaseId, objectStoreId, indexId);
938     const Vector<char> indexDataEnd = IndexDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
939     deleteRange(levelDBTransaction, indexDataStart, indexDataEnd);
940 }
941
942 void IDBBackingStore::putIndexDataForRecord(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, const RecordIdentifier& recordIdentifier)
943 {
944     IDB_TRACE("IDBBackingStore::putIndexDataForRecord");
945     ASSERT(key.isValid());
946     ASSERT(indexId >= MinimumIndexId);
947
948     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
949     const Vector<char> indexDataKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, encodeIDBKey(key), recordIdentifier.primaryKey());
950
951     Vector<char> data;
952     data.append(encodeVarInt(recordIdentifier.version()));
953     data.append(recordIdentifier.primaryKey());
954
955     levelDBTransaction->put(indexDataKey, data);
956 }
957
958 static bool findGreatestKeyLessThanOrEqual(LevelDBTransaction* transaction, const Vector<char>& target, Vector<char>& foundKey)
959 {
960     OwnPtr<LevelDBIterator> it = transaction->createIterator();
961     it->seek(target);
962
963     if (!it->isValid()) {
964         it->seekToLast();
965         if (!it->isValid())
966             return false;
967     }
968
969     while (compareIndexKeys(it->key(), target) > 0) {
970         it->prev();
971         if (!it->isValid())
972             return false;
973     }
974
975     do {
976         foundKey.clear();
977         foundKey.append(it->key().begin(), it->key().end() - it->key().begin());
978
979         // There can be several index keys that compare equal. We want the last one.
980         it->next();
981     } while (it->isValid() && !compareIndexKeys(it->key(), target));
982
983     return true;
984 }
985
986 static bool versionExists(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t version, const Vector<char>& encodedPrimaryKey, bool& exists)
987 {
988     const Vector<char> key = ExistsEntryKey::encode(databaseId, objectStoreId, encodedPrimaryKey);
989     Vector<char> data;
990
991     bool ok = transaction->safeGet(key, data, exists);
992     if (!ok) {
993         InternalError(IDBLevelDBBackingStoreReadErrorVersionExists);
994         return false;
995     }
996     if (!exists)
997         return true;
998
999     exists = (decodeInt(data.begin(), data.end()) == version);
1000     return true;
1001 }
1002
1003 bool IDBBackingStore::findKeyInIndex(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, Vector<char>& foundEncodedPrimaryKey, bool& found)
1004 {
1005     IDB_TRACE("IDBBackingStore::findKeyInIndex");
1006     ASSERT(foundEncodedPrimaryKey.isEmpty());
1007     found = false;
1008
1009     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1010     const Vector<char> leveldbKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, key);
1011     OwnPtr<LevelDBIterator> it = levelDBTransaction->createIterator();
1012     it->seek(leveldbKey);
1013
1014     for (;;) {
1015         if (!it->isValid())
1016             return true;
1017         if (compareIndexKeys(it->key(), leveldbKey) > 0)
1018             return true;
1019
1020         int64_t version;
1021         const char* p = decodeVarInt(it->value().begin(), it->value().end(), version);
1022         if (!p) {
1023             InternalError(IDBLevelDBBackingStoreReadErrorFindKeyInIndex);
1024             return false;
1025         }
1026         foundEncodedPrimaryKey.append(p, it->value().end() - p);
1027
1028         bool exists = false;
1029         bool ok = versionExists(levelDBTransaction, databaseId, objectStoreId, version, foundEncodedPrimaryKey, exists);
1030         if (!ok)
1031             return false;
1032         if (!exists) {
1033             // Delete stale index data entry and continue.
1034             levelDBTransaction->remove(it->key());
1035             it->next();
1036             continue;
1037         }
1038         found = true;
1039         return true;
1040     }
1041 }
1042
1043 bool IDBBackingStore::getPrimaryKeyViaIndex(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, RefPtr<IDBKey>& primaryKey)
1044 {
1045     IDB_TRACE("IDBBackingStore::getPrimaryKeyViaIndex");
1046
1047     bool found = false;
1048     Vector<char> foundEncodedPrimaryKey;
1049     bool ok = findKeyInIndex(transaction, databaseId, objectStoreId, indexId, key, foundEncodedPrimaryKey, found);
1050     if (!ok) {
1051         InternalError(IDBLevelDBBackingStoreReadErrorGetPrimaryKeyViaIndex);
1052         return false;
1053     }
1054     if (found) {
1055         decodeIDBKey(foundEncodedPrimaryKey.begin(), foundEncodedPrimaryKey.end(), primaryKey);
1056         return true;
1057     }
1058
1059     return true;
1060 }
1061
1062 bool IDBBackingStore::keyExistsInIndex(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& indexKey, RefPtr<IDBKey>& foundPrimaryKey, bool& exists)
1063 {
1064     IDB_TRACE("IDBBackingStore::keyExistsInIndex");
1065
1066     exists = false;
1067     Vector<char> foundEncodedPrimaryKey;
1068     bool ok = findKeyInIndex(transaction, databaseId, objectStoreId, indexId, indexKey, foundEncodedPrimaryKey, exists);
1069     if (!ok) {
1070         InternalError(IDBLevelDBBackingStoreReadErrorKeyExistsInIndex);
1071         return false;
1072     }
1073     if (!exists)
1074         return true;
1075
1076     decodeIDBKey(foundEncodedPrimaryKey.begin(), foundEncodedPrimaryKey.end(), foundPrimaryKey);
1077     return true;
1078 }
1079
1080 IDBBackingStore::Cursor::Cursor(const IDBBackingStore::Cursor* other)
1081     : m_transaction(other->m_transaction)
1082     , m_cursorOptions(other->m_cursorOptions)
1083     , m_currentKey(other->m_currentKey)
1084 {
1085     if (other->m_iterator) {
1086         m_iterator = m_transaction->createIterator();
1087
1088         if (other->m_iterator->isValid()) {
1089             m_iterator->seek(other->m_iterator->key());
1090             ASSERT(m_iterator->isValid());
1091         }
1092     }
1093 }
1094
1095 bool IDBBackingStore::Cursor::firstSeek()
1096 {
1097     m_iterator = m_transaction->createIterator();
1098     if (m_cursorOptions.forward)
1099         m_iterator->seek(m_cursorOptions.lowKey);
1100     else
1101         m_iterator->seek(m_cursorOptions.highKey);
1102
1103     return continueFunction(0, Ready);
1104 }
1105
1106 bool IDBBackingStore::Cursor::advance(unsigned long count)
1107 {
1108     while (count--) {
1109         if (!continueFunction())
1110             return false;
1111     }
1112     return true;
1113 }
1114
1115 bool IDBBackingStore::Cursor::continueFunction(const IDBKey* key, IteratorState nextState)
1116 {
1117     RefPtr<IDBKey> previousKey = m_currentKey;
1118
1119     // When iterating with PREV_NO_DUPLICATE, spec requires that the
1120     // value we yield for each key is the first duplicate in forwards
1121     // order.
1122     RefPtr<IDBKey> lastDuplicateKey;
1123
1124     bool forward = m_cursorOptions.forward;
1125
1126     for (;;) {
1127         if (nextState == Seek) {
1128             if (forward)
1129                 m_iterator->next();
1130             else
1131                 m_iterator->prev();
1132         } else
1133             nextState = Seek; // for subsequent iterations
1134
1135         if (!m_iterator->isValid()) {
1136             if (!forward && lastDuplicateKey.get()) {
1137                 // We need to walk forward because we hit the end of
1138                 // the data.
1139                 forward = true;
1140                 continue;
1141             }
1142
1143             return false;
1144         }
1145
1146         if (isPastBounds()) {
1147             if (!forward && lastDuplicateKey.get()) {
1148                 // We need to walk forward because now we're beyond the
1149                 // bounds defined by the cursor.
1150                 forward = true;
1151                 continue;
1152             }
1153
1154             return false;
1155         }
1156
1157         if (!haveEnteredRange())
1158             continue;
1159
1160         // The row may not load because there's a stale entry in the
1161         // index. This is not fatal.
1162         if (!loadCurrentRow())
1163             continue;
1164
1165         if (key) {
1166             if (forward) {
1167                 if (m_currentKey->isLessThan(key))
1168                     continue;
1169             } else {
1170                 if (key->isLessThan(m_currentKey.get()))
1171                     continue;
1172             }
1173         }
1174
1175         if (m_cursorOptions.unique) {
1176
1177             if (m_currentKey->isEqual(previousKey.get())) {
1178                 // We should never be able to walk forward all the way
1179                 // to the previous key.
1180                 ASSERT(!lastDuplicateKey.get());
1181                 continue;
1182             }
1183
1184             if (!forward) {
1185                 if (!lastDuplicateKey.get()) {
1186                     lastDuplicateKey = m_currentKey;
1187                     continue;
1188                 }
1189
1190                 // We need to walk forward because we hit the boundary
1191                 // between key ranges.
1192                 if (!lastDuplicateKey->isEqual(m_currentKey.get())) {
1193                     forward = true;
1194                     continue;
1195                 }
1196
1197                 continue;
1198             }
1199         }
1200         break;
1201     }
1202
1203     ASSERT(!lastDuplicateKey.get() || (forward && lastDuplicateKey->isEqual(m_currentKey.get())));
1204     return true;
1205 }
1206
1207 bool IDBBackingStore::Cursor::haveEnteredRange() const
1208 {
1209     if (m_cursorOptions.forward) {
1210         if (m_cursorOptions.lowOpen)
1211             return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) > 0;
1212
1213         return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) >= 0;
1214     }
1215     if (m_cursorOptions.highOpen)
1216         return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) < 0;
1217
1218     return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) <= 0;
1219 }
1220
1221 bool IDBBackingStore::Cursor::isPastBounds() const
1222 {
1223     if (m_cursorOptions.forward) {
1224         if (m_cursorOptions.highOpen)
1225             return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) >= 0;
1226         return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) > 0;
1227     }
1228
1229     if (m_cursorOptions.lowOpen)
1230         return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) <= 0;
1231     return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) < 0;
1232 }
1233
1234 class ObjectStoreKeyCursorImpl : public IDBBackingStore::Cursor {
1235 public:
1236     static PassRefPtr<ObjectStoreKeyCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1237     {
1238         return adoptRef(new ObjectStoreKeyCursorImpl(transaction, cursorOptions));
1239     }
1240
1241     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1242     {
1243         return adoptRef(new ObjectStoreKeyCursorImpl(this));
1244     }
1245
1246     // IDBBackingStore::Cursor
1247     virtual String value() const { ASSERT_NOT_REACHED(); return String(); }
1248     virtual bool loadCurrentRow();
1249
1250 private:
1251     ObjectStoreKeyCursorImpl(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1252         : IDBBackingStore::Cursor(transaction, cursorOptions)
1253     {
1254     }
1255
1256     ObjectStoreKeyCursorImpl(const ObjectStoreKeyCursorImpl* other)
1257         : IDBBackingStore::Cursor(other)
1258     {
1259     }
1260
1261 };
1262
1263 bool ObjectStoreKeyCursorImpl::loadCurrentRow()
1264 {
1265     const char* keyPosition = m_iterator->key().begin();
1266     const char* keyLimit = m_iterator->key().end();
1267
1268     ObjectStoreDataKey objectStoreDataKey;
1269     keyPosition = ObjectStoreDataKey::decode(keyPosition, keyLimit, &objectStoreDataKey);
1270     if (!keyPosition) {
1271         InternalError(IDBLevelDBBackingStoreReadErrorLoadCurrentRow);
1272         return false;
1273     }
1274
1275     m_currentKey = objectStoreDataKey.userKey();
1276
1277     int64_t version;
1278     const char* valuePosition = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), version);
1279     if (!valuePosition) {
1280         InternalError(IDBLevelDBBackingStoreReadErrorLoadCurrentRow);
1281         return false;
1282     }
1283
1284     // FIXME: This re-encodes what was just decoded; try and optimize.
1285     m_recordIdentifier.reset(encodeIDBKey(*m_currentKey), version);
1286
1287     return true;
1288 }
1289
1290 class ObjectStoreCursorImpl : public IDBBackingStore::Cursor {
1291 public:
1292     static PassRefPtr<ObjectStoreCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1293     {
1294         return adoptRef(new ObjectStoreCursorImpl(transaction, cursorOptions));
1295     }
1296
1297     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1298     {
1299         return adoptRef(new ObjectStoreCursorImpl(this));
1300     }
1301
1302     // IDBBackingStore::Cursor
1303     virtual String value() const { return m_currentValue; }
1304     virtual bool loadCurrentRow();
1305
1306 private:
1307     ObjectStoreCursorImpl(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1308         : IDBBackingStore::Cursor(transaction, cursorOptions)
1309     {
1310     }
1311
1312     ObjectStoreCursorImpl(const ObjectStoreCursorImpl* other)
1313         : IDBBackingStore::Cursor(other)
1314         , m_currentValue(other->m_currentValue)
1315     {
1316     }
1317
1318     String m_currentValue;
1319 };
1320
1321 bool ObjectStoreCursorImpl::loadCurrentRow()
1322 {
1323     const char* keyPosition = m_iterator->key().begin();
1324     const char* keyLimit = m_iterator->key().end();
1325
1326     ObjectStoreDataKey objectStoreDataKey;
1327     keyPosition = ObjectStoreDataKey::decode(keyPosition, keyLimit, &objectStoreDataKey);
1328     if (!keyPosition) {
1329         InternalError(IDBLevelDBBackingStoreReadErrorLoadCurrentRow);
1330         return false;
1331     }
1332
1333     m_currentKey = objectStoreDataKey.userKey();
1334
1335     int64_t version;
1336     const char* valuePosition = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), version);
1337     if (!valuePosition) {
1338         InternalError(IDBLevelDBBackingStoreReadErrorLoadCurrentRow);
1339         return false;
1340     }
1341
1342     // FIXME: This re-encodes what was just decoded; try and optimize.
1343     m_recordIdentifier.reset(encodeIDBKey(*m_currentKey), version);
1344
1345     m_currentValue = decodeString(valuePosition, m_iterator->value().end());
1346
1347     return true;
1348 }
1349
1350 class IndexKeyCursorImpl : public IDBBackingStore::Cursor {
1351 public:
1352     static PassRefPtr<IndexKeyCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1353     {
1354         return adoptRef(new IndexKeyCursorImpl(transaction, cursorOptions));
1355     }
1356
1357     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1358     {
1359         return adoptRef(new IndexKeyCursorImpl(this));
1360     }
1361
1362     // IDBBackingStore::Cursor
1363     virtual String value() const { ASSERT_NOT_REACHED(); return String(); }
1364     virtual PassRefPtr<IDBKey> primaryKey() const { return m_primaryKey; }
1365     virtual const IDBBackingStore::RecordIdentifier& recordIdentifier() const { ASSERT_NOT_REACHED(); return m_recordIdentifier; }
1366     virtual bool loadCurrentRow();
1367
1368 private:
1369     IndexKeyCursorImpl(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1370         : IDBBackingStore::Cursor(transaction, cursorOptions)
1371     {
1372     }
1373
1374     IndexKeyCursorImpl(const IndexKeyCursorImpl* other)
1375         : IDBBackingStore::Cursor(other)
1376         , m_primaryKey(other->m_primaryKey)
1377     {
1378     }
1379
1380     RefPtr<IDBKey> m_primaryKey;
1381 };
1382
1383 bool IndexKeyCursorImpl::loadCurrentRow()
1384 {
1385     const char* keyPosition = m_iterator->key().begin();
1386     const char* keyLimit = m_iterator->key().end();
1387
1388     IndexDataKey indexDataKey;
1389     keyPosition = IndexDataKey::decode(keyPosition, keyLimit, &indexDataKey);
1390
1391     m_currentKey = indexDataKey.userKey();
1392
1393     int64_t indexDataVersion;
1394     const char* valuePosition = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), indexDataVersion);
1395     if (!valuePosition) {
1396         InternalError(IDBLevelDBBackingStoreReadErrorLoadCurrentRow);
1397         return false;
1398     }
1399
1400     valuePosition = decodeIDBKey(valuePosition, m_iterator->value().end(), m_primaryKey);
1401     if (!valuePosition) {
1402         InternalError(IDBLevelDBBackingStoreReadErrorLoadCurrentRow);
1403         return false;
1404     }
1405
1406     Vector<char> primaryLevelDBKey = ObjectStoreDataKey::encode(indexDataKey.databaseId(), indexDataKey.objectStoreId(), *m_primaryKey);
1407
1408     Vector<char> result;
1409     if (!m_transaction->get(primaryLevelDBKey, result)) {
1410         m_transaction->remove(m_iterator->key());
1411         return false;
1412     }
1413
1414     int64_t objectStoreDataVersion;
1415     const char* t = decodeVarInt(result.begin(), result.end(), objectStoreDataVersion);
1416     if (!t) {
1417         InternalError(IDBLevelDBBackingStoreReadErrorLoadCurrentRow);
1418         return false;
1419     }
1420
1421     if (objectStoreDataVersion != indexDataVersion) {
1422         m_transaction->remove(m_iterator->key());
1423         return false;
1424     }
1425
1426     return true;
1427 }
1428
1429 class IndexCursorImpl : public IDBBackingStore::Cursor {
1430 public:
1431     static PassRefPtr<IndexCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1432     {
1433         return adoptRef(new IndexCursorImpl(transaction, cursorOptions));
1434     }
1435
1436     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1437     {
1438         return adoptRef(new IndexCursorImpl(this));
1439     }
1440
1441     // IDBBackingStore::Cursor
1442     virtual String value() const { return m_value; }
1443     virtual PassRefPtr<IDBKey> primaryKey() const { return m_primaryKey; }
1444     virtual const IDBBackingStore::RecordIdentifier& recordIdentifier() const { ASSERT_NOT_REACHED(); return m_recordIdentifier; }
1445     bool loadCurrentRow();
1446
1447 private:
1448     IndexCursorImpl(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1449         : IDBBackingStore::Cursor(transaction, cursorOptions)
1450     {
1451     }
1452
1453     IndexCursorImpl(const IndexCursorImpl* other)
1454         : IDBBackingStore::Cursor(other)
1455         , m_primaryKey(other->m_primaryKey)
1456         , m_value(other->m_value)
1457         , m_primaryLevelDBKey(other->m_primaryLevelDBKey)
1458     {
1459     }
1460
1461     RefPtr<IDBKey> m_primaryKey;
1462     String m_value;
1463     Vector<char> m_primaryLevelDBKey;
1464 };
1465
1466 bool IndexCursorImpl::loadCurrentRow()
1467 {
1468     const char* keyPosition = m_iterator->key().begin();
1469     const char* keyLimit = m_iterator->key().end();
1470
1471     IndexDataKey indexDataKey;
1472     keyPosition = IndexDataKey::decode(keyPosition, keyLimit, &indexDataKey);
1473
1474     m_currentKey = indexDataKey.userKey();
1475
1476     const char* valuePosition = m_iterator->value().begin();
1477     const char* valueLimit = m_iterator->value().end();
1478
1479     int64_t indexDataVersion;
1480     valuePosition = decodeVarInt(valuePosition, valueLimit, indexDataVersion);
1481     if (!valuePosition) {
1482         InternalError(IDBLevelDBBackingStoreReadErrorLoadCurrentRow);
1483         return false;
1484     }
1485     valuePosition = decodeIDBKey(valuePosition, valueLimit, m_primaryKey);
1486     if (!valuePosition) {
1487         InternalError(IDBLevelDBBackingStoreReadErrorLoadCurrentRow);
1488         return false;
1489     }
1490
1491     m_primaryLevelDBKey = ObjectStoreDataKey::encode(indexDataKey.databaseId(), indexDataKey.objectStoreId(), *m_primaryKey);
1492
1493     Vector<char> result;
1494     if (!m_transaction->get(m_primaryLevelDBKey, result)) {
1495         m_transaction->remove(m_iterator->key());
1496         return false;
1497     }
1498
1499     int64_t objectStoreDataVersion;
1500     const char* t = decodeVarInt(result.begin(), result.end(), objectStoreDataVersion);
1501     if (!t) {
1502         InternalError(IDBLevelDBBackingStoreReadErrorLoadCurrentRow);
1503         return false;
1504     }
1505
1506     if (objectStoreDataVersion != indexDataVersion) {
1507         m_transaction->remove(m_iterator->key());
1508         return false;
1509     }
1510
1511     m_value = decodeString(t, result.end());
1512     return true;
1513 }
1514
1515 bool objectStoreCursorOptions(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IDBCursor::Direction direction, IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1516 {
1517     bool lowerBound = range && range->lower();
1518     bool upperBound = range && range->upper();
1519     cursorOptions.forward = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::NEXT);
1520     cursorOptions.unique = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::PREV_NO_DUPLICATE);
1521
1522     if (!lowerBound) {
1523         cursorOptions.lowKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, minIDBKey());
1524         cursorOptions.lowOpen = true; // Not included.
1525     } else {
1526         cursorOptions.lowKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, *range->lower());
1527         cursorOptions.lowOpen = range->lowerOpen();
1528     }
1529
1530     if (!upperBound) {
1531         cursorOptions.highKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, maxIDBKey());
1532
1533         if (cursorOptions.forward)
1534             cursorOptions.highOpen = true; // Not included.
1535         else {
1536             // We need a key that exists.
1537             if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, cursorOptions.highKey))
1538                 return false;
1539             cursorOptions.highOpen = false;
1540         }
1541     } else {
1542         cursorOptions.highKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, *range->upper());
1543         cursorOptions.highOpen = range->upperOpen();
1544
1545         if (!cursorOptions.forward) {
1546             // For reverse cursors, we need a key that exists.
1547             Vector<char> foundHighKey;
1548             if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, foundHighKey))
1549                 return false;
1550
1551             // If the target key should not be included, but we end up with a smaller key, we should include that.
1552             if (cursorOptions.highOpen && compareIndexKeys(foundHighKey, cursorOptions.highKey) < 0)
1553                 cursorOptions.highOpen = false;
1554
1555             cursorOptions.highKey = foundHighKey;
1556         }
1557     }
1558
1559     return true;
1560 }
1561
1562 bool indexCursorOptions(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IDBCursor::Direction direction, IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1563 {
1564     ASSERT(transaction);
1565     bool lowerBound = range && range->lower();
1566     bool upperBound = range && range->upper();
1567     cursorOptions.forward = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::NEXT);
1568     cursorOptions.unique = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::PREV_NO_DUPLICATE);
1569
1570     if (!lowerBound) {
1571         cursorOptions.lowKey = IndexDataKey::encodeMinKey(databaseId, objectStoreId, indexId);
1572         cursorOptions.lowOpen = false; // Included.
1573     } else {
1574         cursorOptions.lowKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->lower());
1575         cursorOptions.lowOpen = range->lowerOpen();
1576     }
1577
1578     if (!upperBound) {
1579         cursorOptions.highKey = IndexDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
1580         cursorOptions.highOpen = false; // Included.
1581
1582         if (!cursorOptions.forward) { // We need a key that exists.
1583             if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, cursorOptions.highKey))
1584                 return false;
1585             cursorOptions.highOpen = false;
1586         }
1587     } else {
1588         cursorOptions.highKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->upper());
1589         cursorOptions.highOpen = range->upperOpen();
1590
1591         Vector<char> foundHighKey;
1592         if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, foundHighKey)) // Seek to the *last* key in the set of non-unique keys.
1593             return false;
1594
1595         // If the target key should not be included, but we end up with a smaller key, we should include that.
1596         if (cursorOptions.highOpen && compareIndexKeys(foundHighKey, cursorOptions.highKey) < 0)
1597             cursorOptions.highOpen = false;
1598
1599         cursorOptions.highKey = foundHighKey;
1600     }
1601
1602     return true;
1603 }
1604
1605 PassRefPtr<IDBBackingStore::Cursor> IDBBackingStore::openObjectStoreCursor(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IDBCursor::Direction direction)
1606 {
1607     IDB_TRACE("IDBBackingStore::openObjectStoreCursor");
1608     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1609     IDBBackingStore::Cursor::CursorOptions cursorOptions;
1610     if (!objectStoreCursorOptions(levelDBTransaction, databaseId, objectStoreId, range, direction, cursorOptions))
1611         return 0;
1612     RefPtr<ObjectStoreCursorImpl> cursor = ObjectStoreCursorImpl::create(levelDBTransaction, cursorOptions);
1613     if (!cursor->firstSeek())
1614         return 0;
1615
1616     return cursor.release();
1617 }
1618
1619 PassRefPtr<IDBBackingStore::Cursor> IDBBackingStore::openObjectStoreKeyCursor(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IDBCursor::Direction direction)
1620 {
1621     IDB_TRACE("IDBBackingStore::openObjectStoreKeyCursor");
1622     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1623     IDBBackingStore::Cursor::CursorOptions cursorOptions;
1624     if (!objectStoreCursorOptions(levelDBTransaction, databaseId, objectStoreId, range, direction, cursorOptions))
1625         return 0;
1626     RefPtr<ObjectStoreKeyCursorImpl> cursor = ObjectStoreKeyCursorImpl::create(levelDBTransaction, cursorOptions);
1627     if (!cursor->firstSeek())
1628         return 0;
1629
1630     return cursor.release();
1631 }
1632
1633 PassRefPtr<IDBBackingStore::Cursor> IDBBackingStore::openIndexKeyCursor(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IDBCursor::Direction direction)
1634 {
1635     IDB_TRACE("IDBBackingStore::openIndexKeyCursor");
1636     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1637     IDBBackingStore::Cursor::CursorOptions cursorOptions;
1638     if (!indexCursorOptions(levelDBTransaction, databaseId, objectStoreId, indexId, range, direction, cursorOptions))
1639         return 0;
1640     RefPtr<IndexKeyCursorImpl> cursor = IndexKeyCursorImpl::create(levelDBTransaction, cursorOptions);
1641     if (!cursor->firstSeek())
1642         return 0;
1643
1644     return cursor.release();
1645 }
1646
1647 PassRefPtr<IDBBackingStore::Cursor> IDBBackingStore::openIndexCursor(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IDBCursor::Direction direction)
1648 {
1649     IDB_TRACE("IDBBackingStore::openIndexCursor");
1650     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1651     IDBBackingStore::Cursor::CursorOptions cursorOptions;
1652     if (!indexCursorOptions(levelDBTransaction, databaseId, objectStoreId, indexId, range, direction, cursorOptions))
1653         return 0;
1654     RefPtr<IndexCursorImpl> cursor = IndexCursorImpl::create(levelDBTransaction, cursorOptions);
1655     if (!cursor->firstSeek())
1656         return 0;
1657
1658     return cursor.release();
1659 }
1660
1661 IDBBackingStore::Transaction::Transaction(IDBBackingStore* backingStore)
1662     : m_backingStore(backingStore)
1663 {
1664 }
1665
1666 void IDBBackingStore::Transaction::begin()
1667 {
1668     IDB_TRACE("IDBBackingStore::Transaction::begin");
1669     ASSERT(!m_transaction);
1670     m_transaction = LevelDBTransaction::create(m_backingStore->m_db.get());
1671 }
1672
1673 bool IDBBackingStore::Transaction::commit()
1674 {
1675     IDB_TRACE("IDBBackingStore::Transaction::commit");
1676     ASSERT(m_transaction);
1677     bool result = m_transaction->commit();
1678     m_transaction.clear();
1679     return result;
1680 }
1681
1682 void IDBBackingStore::Transaction::rollback()
1683 {
1684     IDB_TRACE("IDBBackingStore::Transaction::rollback");
1685     ASSERT(m_transaction);
1686     m_transaction->rollback();
1687     m_transaction.clear();
1688 }
1689
1690 } // namespace WebCore
1691
1692 #endif // ENABLE(INDEXED_DATABASE)