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