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