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