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