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