Replace static_cast<SVGStyledElement> with toSVGStyledElement()
[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 void IDBBackingStore::getObjectStores(int64_t databaseId, IDBDatabaseMetadata::ObjectStoreMap* objectStores)
640 {
641     IDB_TRACE("IDBBackingStore::getObjectStores");
642     const Vector<char> startKey = ObjectStoreMetaDataKey::encode(databaseId, 1, 0);
643     const Vector<char> stopKey = ObjectStoreMetaDataKey::encodeMaxKey(databaseId);
644
645     ASSERT(objectStores->isEmpty());
646
647     OwnPtr<LevelDBIterator> it = m_db->createIterator();
648     it->seek(startKey);
649     while (it->isValid() && compareKeys(it->key(), stopKey) < 0) {
650         const char* p = it->key().begin();
651         const char* limit = it->key().end();
652
653         ObjectStoreMetaDataKey metaDataKey;
654         p = ObjectStoreMetaDataKey::decode(p, limit, &metaDataKey);
655         ASSERT(p);
656         if (metaDataKey.metaDataType() != ObjectStoreMetaDataKey::Name) {
657             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
658             // Possible stale metadata, but don't fail the load.
659             it->next();
660             continue;
661         }
662
663         int64_t objectStoreId = metaDataKey.objectStoreId();
664
665         // FIXME: Do this by direct key lookup rather than iteration, to simplify.
666         String objectStoreName = decodeString(it->value().begin(), it->value().end());
667
668         it->next();
669         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::KeyPath)) {
670             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
671             break;
672         }
673         IDBKeyPath keyPath = decodeIDBKeyPath(it->value().begin(), it->value().end());
674
675         it->next();
676         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::AutoIncrement)) {
677             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
678             break;
679         }
680         bool autoIncrement = decodeBool(it->value().begin(), it->value().end());
681
682         it->next(); // Is evicatble.
683         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::Evictable)) {
684             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
685             break;
686         }
687
688         it->next(); // Last version.
689         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::LastVersion)) {
690             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
691             break;
692         }
693
694         it->next(); // Maximum index id allocated.
695         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::MaxIndexId)) {
696             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
697             break;
698         }
699         int64_t maxIndexId = decodeInt(it->value().begin(), it->value().end());
700
701         it->next(); // [optional] has key path (is not null)
702         if (checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::HasKeyPath)) {
703             bool hasKeyPath = decodeBool(it->value().begin(), it->value().end());
704             // This check accounts for two layers of legacy coding:
705             // (1) Initially, hasKeyPath was added to distinguish null vs. string.
706             // (2) Later, null vs. string vs. array was stored in the keyPath itself.
707             // So this check is only relevant for string-type keyPaths.
708             if (!hasKeyPath && (keyPath.type() == IDBKeyPath::StringType && !keyPath.string().isEmpty())) {
709                 INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
710                 break;
711             }
712             if (!hasKeyPath)
713                 keyPath = IDBKeyPath();
714             it->next();
715         }
716
717         int64_t keyGeneratorCurrentNumber = -1;
718         if (checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber)) {
719             keyGeneratorCurrentNumber = decodeInt(it->value().begin(), it->value().end());
720             // FIXME: Return keyGeneratorCurrentNumber, cache in object store, and write lazily to backing store.
721             // For now, just assert that if it was written it was valid.
722             ASSERT_UNUSED(keyGeneratorCurrentNumber, keyGeneratorCurrentNumber >= KeyGeneratorInitialNumber);
723             it->next();
724         }
725
726         IDBObjectStoreMetadata metadata(objectStoreName, objectStoreId, keyPath, autoIncrement, maxIndexId);
727         getIndexes(databaseId, objectStoreId, &metadata.indexes);
728         objectStores->set(objectStoreId, metadata);
729     }
730 }
731
732 WARN_UNUSED_RETURN static bool setMaxObjectStoreId(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId)
733 {
734     const Vector<char> maxObjectStoreIdKey = DatabaseMetaDataKey::encode(databaseId, DatabaseMetaDataKey::MaxObjectStoreId);
735     int64_t maxObjectStoreId = -1;
736     bool ok = getMaxObjectStoreId(transaction, maxObjectStoreIdKey, maxObjectStoreId);
737     if (!ok) {
738         INTERNAL_READ_ERROR(SetMaxObjectStoreId);
739         return false;
740     }
741
742     if (objectStoreId <= maxObjectStoreId) {
743         INTERNAL_CONSISTENCY_ERROR(SetMaxObjectStoreId);
744         return false;
745     }
746     putInt(transaction, maxObjectStoreIdKey, objectStoreId);
747     return true;
748 }
749
750 bool IDBBackingStore::createObjectStore(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const String& name, const IDBKeyPath& keyPath, bool autoIncrement)
751 {
752     IDB_TRACE("IDBBackingStore::createObjectStore");
753     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
754     if (!setMaxObjectStoreId(levelDBTransaction, databaseId, objectStoreId))
755         return false;
756
757     const Vector<char> nameKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::Name);
758     const Vector<char> keyPathKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyPath);
759     const Vector<char> autoIncrementKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::AutoIncrement);
760     const Vector<char> evictableKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::Evictable);
761     const Vector<char> lastVersionKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::LastVersion);
762     const Vector<char> maxIndexIdKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::MaxIndexId);
763     const Vector<char> hasKeyPathKey  = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::HasKeyPath);
764     const Vector<char> keyGeneratorCurrentNumberKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber);
765     const Vector<char> namesKey = ObjectStoreNamesKey::encode(databaseId, name);
766
767     putString(levelDBTransaction, nameKey, name);
768     putIDBKeyPath(levelDBTransaction, keyPathKey, keyPath);
769     putInt(levelDBTransaction, autoIncrementKey, autoIncrement);
770     putInt(levelDBTransaction, evictableKey, false);
771     putInt(levelDBTransaction, lastVersionKey, 1);
772     putInt(levelDBTransaction, maxIndexIdKey, MinimumIndexId);
773     putBool(levelDBTransaction, hasKeyPathKey, !keyPath.isNull());
774     putInt(levelDBTransaction, keyGeneratorCurrentNumberKey, KeyGeneratorInitialNumber);
775     putInt(levelDBTransaction, namesKey, objectStoreId);
776     return true;
777 }
778
779 bool IDBBackingStore::deleteObjectStore(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId)
780 {
781     IDB_TRACE("IDBBackingStore::deleteObjectStore");
782     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
783
784     String objectStoreName;
785     bool found = false;
786     bool ok = getString(levelDBTransaction, ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::Name), objectStoreName, found);
787     if (!ok) {
788         INTERNAL_READ_ERROR(DeleteObjectStore);
789         return false;
790     }
791     if (!found) {
792         INTERNAL_CONSISTENCY_ERROR(DeleteObjectStore);
793         return false;
794     }
795
796     deleteRange(levelDBTransaction, ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, 0), ObjectStoreMetaDataKey::encodeMaxKey(databaseId, objectStoreId));
797
798     levelDBTransaction->remove(ObjectStoreNamesKey::encode(databaseId, objectStoreName));
799
800     deleteRange(levelDBTransaction, IndexFreeListKey::encode(databaseId, objectStoreId, 0), IndexFreeListKey::encodeMaxKey(databaseId, objectStoreId));
801     deleteRange(levelDBTransaction, IndexMetaDataKey::encode(databaseId, objectStoreId, 0, 0), IndexMetaDataKey::encodeMaxKey(databaseId, objectStoreId));
802
803     clearObjectStore(transaction, databaseId, objectStoreId);
804     return true;
805 }
806
807 bool IDBBackingStore::getRecord(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKey& key, Vector<char>& record)
808 {
809     IDB_TRACE("IDBBackingStore::getRecord");
810     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
811
812     const Vector<char> leveldbKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
813     Vector<char> data;
814
815     record.clear();
816
817     bool found = false;
818     bool ok = levelDBTransaction->safeGet(leveldbKey, data, found);
819     if (!ok) {
820         INTERNAL_READ_ERROR(GetRecord);
821         return false;
822     }
823     if (!found)
824         return true;
825
826     int64_t version;
827     const char* p = decodeVarInt(data.begin(), data.end(), version);
828     if (!p) {
829         INTERNAL_READ_ERROR(GetRecord);
830         return false;
831     }
832
833     record.appendRange(p, static_cast<const char*>(data.end()));
834     return true;
835 }
836
837 WARN_UNUSED_RETURN static bool getNewVersionNumber(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t& newVersionNumber)
838 {
839     const Vector<char> lastVersionKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::LastVersion);
840
841     newVersionNumber = -1;
842     int64_t lastVersion = -1;
843     bool found = false;
844     bool ok = getInt(transaction, lastVersionKey, lastVersion, found);
845     if (!ok) {
846         INTERNAL_READ_ERROR(GetNewVersionNumber);
847         return false;
848     }
849     if (!found)
850         lastVersion = 0;
851
852     ASSERT(lastVersion >= 0);
853
854     int64_t version = lastVersion + 1;
855     putInt(transaction, lastVersionKey, version);
856
857     ASSERT(version > lastVersion); // FIXME: Think about how we want to handle the overflow scenario.
858
859     newVersionNumber = version;
860     return true;
861 }
862
863 bool IDBBackingStore::putRecord(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKey& key, PassRefPtr<SharedBuffer> prpValue, RecordIdentifier* recordIdentifier)
864 {
865     IDB_TRACE("IDBBackingStore::putRecord");
866     ASSERT(key.isValid());
867     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
868     int64_t version = -1;
869     bool ok = getNewVersionNumber(levelDBTransaction, databaseId, objectStoreId, version);
870     if (!ok)
871         return false;
872     ASSERT(version >= 0);
873     const Vector<char> objectStoredataKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
874
875     Vector<char> v;
876     v.append(encodeVarInt(version));
877     RefPtr<SharedBuffer> value = prpValue;
878     ASSERT(value);
879     v.append(value->data(), value->size());
880
881     levelDBTransaction->put(objectStoredataKey, v);
882
883     const Vector<char> existsEntryKey = ExistsEntryKey::encode(databaseId, objectStoreId, key);
884     levelDBTransaction->put(existsEntryKey, encodeInt(version));
885
886     recordIdentifier->reset(encodeIDBKey(key), version);
887     return true;
888 }
889
890 void IDBBackingStore::clearObjectStore(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId)
891 {
892     IDB_TRACE("IDBBackingStore::clearObjectStore");
893     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
894     const Vector<char> startKey = KeyPrefix(databaseId, objectStoreId, 0).encode();
895     const Vector<char> stopKey = KeyPrefix(databaseId, objectStoreId + 1, 0).encode();
896
897     deleteRange(levelDBTransaction, startKey, stopKey);
898 }
899
900 void IDBBackingStore::deleteRecord(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const RecordIdentifier& recordIdentifier)
901 {
902     IDB_TRACE("IDBBackingStore::deleteRecord");
903     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
904
905     const Vector<char> objectStoreDataKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, recordIdentifier.primaryKey());
906     levelDBTransaction->remove(objectStoreDataKey);
907
908     const Vector<char> existsEntryKey = ExistsEntryKey::encode(databaseId, objectStoreId, recordIdentifier.primaryKey());
909     levelDBTransaction->remove(existsEntryKey);
910 }
911
912
913 bool IDBBackingStore::getKeyGeneratorCurrentNumber(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t& keyGeneratorCurrentNumber)
914 {
915     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
916
917     const Vector<char> keyGeneratorCurrentNumberKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber);
918
919     keyGeneratorCurrentNumber = -1;
920     Vector<char> data;
921
922     bool found = false;
923     bool ok = levelDBTransaction->safeGet(keyGeneratorCurrentNumberKey, data, found);
924     if (!ok) {
925         INTERNAL_READ_ERROR(GetKeyGeneratorCurrentNumber);
926         return false;
927     }
928     if (found)
929         keyGeneratorCurrentNumber = decodeInt(data.begin(), data.end());
930     else {
931         // Previously, the key generator state was not stored explicitly but derived from the
932         // maximum numeric key present in existing data. This violates the spec as the data may
933         // be cleared but the key generator state must be preserved.
934         const Vector<char> startKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, minIDBKey());
935         const Vector<char> stopKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, maxIDBKey());
936
937         OwnPtr<LevelDBIterator> it = levelDBTransaction->createIterator();
938         int64_t maxNumericKey = 0;
939
940         for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
941             const char* p = it->key().begin();
942             const char* limit = it->key().end();
943
944             ObjectStoreDataKey dataKey;
945             p = ObjectStoreDataKey::decode(p, limit, &dataKey);
946             ASSERT(p);
947
948             if (dataKey.userKey()->type() == IDBKey::NumberType) {
949                 int64_t n = static_cast<int64_t>(dataKey.userKey()->number());
950                 if (n > maxNumericKey)
951                     maxNumericKey = n;
952             }
953         }
954
955         keyGeneratorCurrentNumber = maxNumericKey + 1;
956     }
957
958     return keyGeneratorCurrentNumber;
959 }
960
961 bool IDBBackingStore::maybeUpdateKeyGeneratorCurrentNumber(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t newNumber, bool checkCurrent)
962 {
963     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
964
965     if (checkCurrent) {
966         int64_t currentNumber;
967         bool ok = getKeyGeneratorCurrentNumber(transaction, databaseId, objectStoreId, currentNumber);
968         if (!ok)
969             return false;
970         if (newNumber <= currentNumber)
971             return true;
972     }
973
974     const Vector<char> keyGeneratorCurrentNumberKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber);
975     putInt(levelDBTransaction, keyGeneratorCurrentNumberKey, newNumber);
976     return true;
977 }
978
979 bool IDBBackingStore::keyExistsInObjectStore(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKey& key, RecordIdentifier* foundRecordIdentifier, bool& found)
980 {
981     IDB_TRACE("IDBBackingStore::keyExistsInObjectStore");
982     found = false;
983     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
984     const Vector<char> leveldbKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
985     Vector<char> data;
986
987     bool ok = levelDBTransaction->safeGet(leveldbKey, data, found);
988     if (!ok) {
989         INTERNAL_READ_ERROR(KeyExistsInObjectStore);
990         return false;
991     }
992     if (!found)
993         return true;
994
995     int64_t version;
996     if (!decodeVarInt(data.begin(), data.end(), version))
997         return false;
998
999     foundRecordIdentifier->reset(encodeIDBKey(key), version);
1000     return true;
1001 }
1002
1003 static bool checkIndexAndMetaDataKey(const LevelDBIterator* it, const Vector<char>& stopKey, int64_t indexId, unsigned char metaDataType)
1004 {
1005     if (!it->isValid() || compareKeys(it->key(), stopKey) >= 0)
1006         return false;
1007
1008     IndexMetaDataKey metaDataKey;
1009     const char* p = IndexMetaDataKey::decode(it->key().begin(), it->key().end(), &metaDataKey);
1010     ASSERT_UNUSED(p, p);
1011     if (metaDataKey.indexId() != indexId)
1012         return false;
1013     if (metaDataKey.metaDataType() != metaDataType)
1014         return false;
1015     return true;
1016 }
1017
1018
1019 // FIXME: This should do some error handling rather than plowing ahead when bad data is encountered.
1020 void IDBBackingStore::getIndexes(int64_t databaseId, int64_t objectStoreId, IDBObjectStoreMetadata::IndexMap* indexes)
1021 {
1022     IDB_TRACE("IDBBackingStore::getIndexes");
1023     const Vector<char> startKey = IndexMetaDataKey::encode(databaseId, objectStoreId, 0, 0);
1024     const Vector<char> stopKey = IndexMetaDataKey::encode(databaseId, objectStoreId + 1, 0, 0);
1025
1026     ASSERT(indexes->isEmpty());
1027
1028     OwnPtr<LevelDBIterator> it = m_db->createIterator();
1029     it->seek(startKey);
1030     while (it->isValid() && compareKeys(it->key(), stopKey) < 0) {
1031         const char* p = it->key().begin();
1032         const char* limit = it->key().end();
1033
1034         IndexMetaDataKey metaDataKey;
1035         p = IndexMetaDataKey::decode(p, limit, &metaDataKey);
1036         ASSERT(p);
1037         if (metaDataKey.metaDataType() != IndexMetaDataKey::Name) {
1038             INTERNAL_CONSISTENCY_ERROR(GetIndexes);
1039             // Possible stale metadata due to http://webkit.org/b/85557 but don't fail the load.
1040             it->next();
1041             continue;
1042         }
1043
1044         // FIXME: Do this by direct key lookup rather than iteration, to simplify.
1045         int64_t indexId = metaDataKey.indexId();
1046         String indexName = decodeString(it->value().begin(), it->value().end());
1047
1048         it->next(); // unique flag
1049         if (!checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::Unique)) {
1050             INTERNAL_CONSISTENCY_ERROR(GetIndexes);
1051             break;
1052         }
1053         bool indexUnique = decodeBool(it->value().begin(), it->value().end());
1054
1055         it->next(); // keyPath
1056         if (!checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::KeyPath)) {
1057             INTERNAL_CONSISTENCY_ERROR(GetIndexes);
1058             break;
1059         }
1060         IDBKeyPath keyPath = decodeIDBKeyPath(it->value().begin(), it->value().end());
1061
1062         it->next(); // [optional] multiEntry flag
1063         bool indexMultiEntry = false;
1064         if (checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::MultiEntry)) {
1065             indexMultiEntry = decodeBool(it->value().begin(), it->value().end());
1066             it->next();
1067         }
1068
1069         indexes->set(indexId, IDBIndexMetadata(indexName, indexId, keyPath, indexUnique, indexMultiEntry));
1070     }
1071 }
1072
1073 WARN_UNUSED_RETURN static bool setMaxIndexId(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1074 {
1075     int64_t maxIndexId = -1;
1076     const Vector<char> maxIndexIdKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::MaxIndexId);
1077     bool found = false;
1078     bool ok = getInt(transaction, maxIndexIdKey, maxIndexId, found);
1079     if (!ok) {
1080         INTERNAL_READ_ERROR(SetMaxIndexId);
1081         return false;
1082     }
1083     if (!found)
1084         maxIndexId = MinimumIndexId;
1085
1086     if (indexId <= maxIndexId) {
1087         INTERNAL_CONSISTENCY_ERROR(SetMaxIndexId);
1088         return false;
1089     }
1090
1091     putInt(transaction, maxIndexIdKey, indexId);
1092     return true;
1093 }
1094
1095 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)
1096 {
1097     IDB_TRACE("IDBBackingStore::createIndex");
1098     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1099     if (!setMaxIndexId(levelDBTransaction, databaseId, objectStoreId, indexId))
1100         return false;
1101
1102     const Vector<char> nameKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::Name);
1103     const Vector<char> uniqueKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::Unique);
1104     const Vector<char> keyPathKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::KeyPath);
1105     const Vector<char> multiEntryKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::MultiEntry);
1106
1107     putString(levelDBTransaction, nameKey, name);
1108     putBool(levelDBTransaction, uniqueKey, isUnique);
1109     putIDBKeyPath(levelDBTransaction, keyPathKey, keyPath);
1110     putBool(levelDBTransaction, multiEntryKey, isMultiEntry);
1111     return true;
1112 }
1113
1114 void IDBBackingStore::deleteIndex(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1115 {
1116     IDB_TRACE("IDBBackingStore::deleteIndex");
1117     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1118
1119     const Vector<char> indexMetaDataStart = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, 0);
1120     const Vector<char> indexMetaDataEnd = IndexMetaDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
1121     deleteRange(levelDBTransaction, indexMetaDataStart, indexMetaDataEnd);
1122
1123     const Vector<char> indexDataStart = IndexDataKey::encodeMinKey(databaseId, objectStoreId, indexId);
1124     const Vector<char> indexDataEnd = IndexDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
1125     deleteRange(levelDBTransaction, indexDataStart, indexDataEnd);
1126 }
1127
1128 void IDBBackingStore::putIndexDataForRecord(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, const RecordIdentifier& recordIdentifier)
1129 {
1130     IDB_TRACE("IDBBackingStore::putIndexDataForRecord");
1131     ASSERT(key.isValid());
1132     ASSERT(indexId >= MinimumIndexId);
1133
1134     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1135     const Vector<char> indexDataKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, encodeIDBKey(key), recordIdentifier.primaryKey());
1136
1137     Vector<char> data;
1138     data.append(encodeVarInt(recordIdentifier.version()));
1139     data.append(recordIdentifier.primaryKey());
1140
1141     levelDBTransaction->put(indexDataKey, data);
1142 }
1143
1144 static bool findGreatestKeyLessThanOrEqual(LevelDBTransaction* transaction, const Vector<char>& target, Vector<char>& foundKey)
1145 {
1146     OwnPtr<LevelDBIterator> it = transaction->createIterator();
1147     it->seek(target);
1148
1149     if (!it->isValid()) {
1150         it->seekToLast();
1151         if (!it->isValid())
1152             return false;
1153     }
1154
1155     while (compareIndexKeys(it->key(), target) > 0) {
1156         it->prev();
1157         if (!it->isValid())
1158             return false;
1159     }
1160
1161     do {
1162         foundKey.clear();
1163         foundKey.append(it->key().begin(), it->key().end() - it->key().begin());
1164
1165         // There can be several index keys that compare equal. We want the last one.
1166         it->next();
1167     } while (it->isValid() && !compareIndexKeys(it->key(), target));
1168
1169     return true;
1170 }
1171
1172 static bool versionExists(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t version, const Vector<char>& encodedPrimaryKey, bool& exists)
1173 {
1174     const Vector<char> key = ExistsEntryKey::encode(databaseId, objectStoreId, encodedPrimaryKey);
1175     Vector<char> data;
1176
1177     bool ok = transaction->safeGet(key, data, exists);
1178     if (!ok) {
1179         INTERNAL_READ_ERROR(VersionExists);
1180         return false;
1181     }
1182     if (!exists)
1183         return true;
1184
1185     exists = (decodeInt(data.begin(), data.end()) == version);
1186     return true;
1187 }
1188
1189 bool IDBBackingStore::findKeyInIndex(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, Vector<char>& foundEncodedPrimaryKey, bool& found)
1190 {
1191     IDB_TRACE("IDBBackingStore::findKeyInIndex");
1192     ASSERT(foundEncodedPrimaryKey.isEmpty());
1193     found = false;
1194
1195     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1196     const Vector<char> leveldbKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, key);
1197     OwnPtr<LevelDBIterator> it = levelDBTransaction->createIterator();
1198     it->seek(leveldbKey);
1199
1200     for (;;) {
1201         if (!it->isValid())
1202             return true;
1203         if (compareIndexKeys(it->key(), leveldbKey) > 0)
1204             return true;
1205
1206         int64_t version;
1207         const char* p = decodeVarInt(it->value().begin(), it->value().end(), version);
1208         if (!p) {
1209             INTERNAL_READ_ERROR(FindKeyInIndex);
1210             return false;
1211         }
1212         foundEncodedPrimaryKey.append(p, it->value().end() - p);
1213
1214         bool exists = false;
1215         bool ok = versionExists(levelDBTransaction, databaseId, objectStoreId, version, foundEncodedPrimaryKey, exists);
1216         if (!ok)
1217             return false;
1218         if (!exists) {
1219             // Delete stale index data entry and continue.
1220             levelDBTransaction->remove(it->key());
1221             it->next();
1222             continue;
1223         }
1224         found = true;
1225         return true;
1226     }
1227 }
1228
1229 bool IDBBackingStore::getPrimaryKeyViaIndex(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, RefPtr<IDBKey>& primaryKey)
1230 {
1231     IDB_TRACE("IDBBackingStore::getPrimaryKeyViaIndex");
1232
1233     bool found = false;
1234     Vector<char> foundEncodedPrimaryKey;
1235     bool ok = findKeyInIndex(transaction, databaseId, objectStoreId, indexId, key, foundEncodedPrimaryKey, found);
1236     if (!ok) {
1237         INTERNAL_READ_ERROR(GetPrimaryKeyViaIndex);
1238         return false;
1239     }
1240     if (found) {
1241         decodeIDBKey(foundEncodedPrimaryKey.begin(), foundEncodedPrimaryKey.end(), primaryKey);
1242         return true;
1243     }
1244
1245     return true;
1246 }
1247
1248 bool IDBBackingStore::keyExistsInIndex(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& indexKey, RefPtr<IDBKey>& foundPrimaryKey, bool& exists)
1249 {
1250     IDB_TRACE("IDBBackingStore::keyExistsInIndex");
1251
1252     exists = false;
1253     Vector<char> foundEncodedPrimaryKey;
1254     bool ok = findKeyInIndex(transaction, databaseId, objectStoreId, indexId, indexKey, foundEncodedPrimaryKey, exists);
1255     if (!ok) {
1256         INTERNAL_READ_ERROR(KeyExistsInIndex);
1257         return false;
1258     }
1259     if (!exists)
1260         return true;
1261
1262     decodeIDBKey(foundEncodedPrimaryKey.begin(), foundEncodedPrimaryKey.end(), foundPrimaryKey);
1263     return true;
1264 }
1265
1266 IDBBackingStore::Cursor::Cursor(const IDBBackingStore::Cursor* other)
1267     : m_transaction(other->m_transaction)
1268     , m_cursorOptions(other->m_cursorOptions)
1269     , m_currentKey(other->m_currentKey)
1270 {
1271     if (other->m_iterator) {
1272         m_iterator = m_transaction->createIterator();
1273
1274         if (other->m_iterator->isValid()) {
1275             m_iterator->seek(other->m_iterator->key());
1276             ASSERT(m_iterator->isValid());
1277         }
1278     }
1279 }
1280
1281 bool IDBBackingStore::Cursor::firstSeek()
1282 {
1283     m_iterator = m_transaction->createIterator();
1284     if (m_cursorOptions.forward)
1285         m_iterator->seek(m_cursorOptions.lowKey);
1286     else
1287         m_iterator->seek(m_cursorOptions.highKey);
1288
1289     return continueFunction(0, Ready);
1290 }
1291
1292 bool IDBBackingStore::Cursor::advance(unsigned long count)
1293 {
1294     while (count--) {
1295         if (!continueFunction())
1296             return false;
1297     }
1298     return true;
1299 }
1300
1301 bool IDBBackingStore::Cursor::continueFunction(const IDBKey* key, IteratorState nextState)
1302 {
1303     RefPtr<IDBKey> previousKey = m_currentKey;
1304
1305     // When iterating with PrevNoDuplicate, spec requires that the
1306     // value we yield for each key is the first duplicate in forwards
1307     // order.
1308     RefPtr<IDBKey> lastDuplicateKey;
1309
1310     bool forward = m_cursorOptions.forward;
1311
1312     for (;;) {
1313         if (nextState == Seek) {
1314             if (forward)
1315                 m_iterator->next();
1316             else
1317                 m_iterator->prev();
1318         } else
1319             nextState = Seek; // for subsequent iterations
1320
1321         if (!m_iterator->isValid()) {
1322             if (!forward && lastDuplicateKey.get()) {
1323                 // We need to walk forward because we hit the end of
1324                 // the data.
1325                 forward = true;
1326                 continue;
1327             }
1328
1329             return false;
1330         }
1331
1332         if (isPastBounds()) {
1333             if (!forward && lastDuplicateKey.get()) {
1334                 // We need to walk forward because now we're beyond the
1335                 // bounds defined by the cursor.
1336                 forward = true;
1337                 continue;
1338             }
1339
1340             return false;
1341         }
1342
1343         if (!haveEnteredRange())
1344             continue;
1345
1346         // The row may not load because there's a stale entry in the
1347         // index. This is not fatal.
1348         if (!loadCurrentRow())
1349             continue;
1350
1351         if (key) {
1352             if (forward) {
1353                 if (m_currentKey->isLessThan(key))
1354                     continue;
1355             } else {
1356                 if (key->isLessThan(m_currentKey.get()))
1357                     continue;
1358             }
1359         }
1360
1361         if (m_cursorOptions.unique) {
1362
1363             if (m_currentKey->isEqual(previousKey.get())) {
1364                 // We should never be able to walk forward all the way
1365                 // to the previous key.
1366                 ASSERT(!lastDuplicateKey.get());
1367                 continue;
1368             }
1369
1370             if (!forward) {
1371                 if (!lastDuplicateKey.get()) {
1372                     lastDuplicateKey = m_currentKey;
1373                     continue;
1374                 }
1375
1376                 // We need to walk forward because we hit the boundary
1377                 // between key ranges.
1378                 if (!lastDuplicateKey->isEqual(m_currentKey.get())) {
1379                     forward = true;
1380                     continue;
1381                 }
1382
1383                 continue;
1384             }
1385         }
1386         break;
1387     }
1388
1389     ASSERT(!lastDuplicateKey.get() || (forward && lastDuplicateKey->isEqual(m_currentKey.get())));
1390     return true;
1391 }
1392
1393 bool IDBBackingStore::Cursor::haveEnteredRange() const
1394 {
1395     if (m_cursorOptions.forward) {
1396         if (m_cursorOptions.lowOpen)
1397             return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) > 0;
1398
1399         return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) >= 0;
1400     }
1401     if (m_cursorOptions.highOpen)
1402         return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) < 0;
1403
1404     return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) <= 0;
1405 }
1406
1407 bool IDBBackingStore::Cursor::isPastBounds() const
1408 {
1409     if (m_cursorOptions.forward) {
1410         if (m_cursorOptions.highOpen)
1411             return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) >= 0;
1412         return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) > 0;
1413     }
1414
1415     if (m_cursorOptions.lowOpen)
1416         return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) <= 0;
1417     return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) < 0;
1418 }
1419
1420 class ObjectStoreKeyCursorImpl : public IDBBackingStore::Cursor {
1421 public:
1422     static PassRefPtr<ObjectStoreKeyCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1423     {
1424         return adoptRef(new ObjectStoreKeyCursorImpl(transaction, cursorOptions));
1425     }
1426
1427     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1428     {
1429         return adoptRef(new ObjectStoreKeyCursorImpl(this));
1430     }
1431
1432     // IDBBackingStore::Cursor
1433     virtual PassRefPtr<SharedBuffer> value() const { ASSERT_NOT_REACHED(); return 0; }
1434     virtual bool loadCurrentRow();
1435
1436 private:
1437     ObjectStoreKeyCursorImpl(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1438         : IDBBackingStore::Cursor(transaction, cursorOptions)
1439     {
1440     }
1441
1442     ObjectStoreKeyCursorImpl(const ObjectStoreKeyCursorImpl* other)
1443         : IDBBackingStore::Cursor(other)
1444     {
1445     }
1446 };
1447
1448 bool ObjectStoreKeyCursorImpl::loadCurrentRow()
1449 {
1450     const char* keyPosition = m_iterator->key().begin();
1451     const char* keyLimit = m_iterator->key().end();
1452
1453     ObjectStoreDataKey objectStoreDataKey;
1454     keyPosition = ObjectStoreDataKey::decode(keyPosition, keyLimit, &objectStoreDataKey);
1455     if (!keyPosition) {
1456         INTERNAL_READ_ERROR(LoadCurrentRow);
1457         return false;
1458     }
1459
1460     m_currentKey = objectStoreDataKey.userKey();
1461
1462     int64_t version;
1463     const char* valuePosition = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), version);
1464     if (!valuePosition) {
1465         INTERNAL_READ_ERROR(LoadCurrentRow);
1466         return false;
1467     }
1468
1469     // FIXME: This re-encodes what was just decoded; try and optimize.
1470     m_recordIdentifier.reset(encodeIDBKey(*m_currentKey), version);
1471
1472     return true;
1473 }
1474
1475 class ObjectStoreCursorImpl : public IDBBackingStore::Cursor {
1476 public:
1477     static PassRefPtr<ObjectStoreCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1478     {
1479         return adoptRef(new ObjectStoreCursorImpl(transaction, cursorOptions));
1480     }
1481
1482     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1483     {
1484         return adoptRef(new ObjectStoreCursorImpl(this));
1485     }
1486
1487     // IDBBackingStore::Cursor
1488     virtual PassRefPtr<SharedBuffer> value() const { return m_currentValue; }
1489     virtual bool loadCurrentRow();
1490
1491 private:
1492     ObjectStoreCursorImpl(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1493         : IDBBackingStore::Cursor(transaction, cursorOptions)
1494     {
1495     }
1496
1497     ObjectStoreCursorImpl(const ObjectStoreCursorImpl* other)
1498         : IDBBackingStore::Cursor(other)
1499         , m_currentValue(other->m_currentValue)
1500     {
1501     }
1502
1503     RefPtr<SharedBuffer> m_currentValue;
1504 };
1505
1506 bool ObjectStoreCursorImpl::loadCurrentRow()
1507 {
1508     const char* keyPosition = m_iterator->key().begin();
1509     const char* keyLimit = m_iterator->key().end();
1510
1511     ObjectStoreDataKey objectStoreDataKey;
1512     keyPosition = ObjectStoreDataKey::decode(keyPosition, keyLimit, &objectStoreDataKey);
1513     if (!keyPosition) {
1514         INTERNAL_READ_ERROR(LoadCurrentRow);
1515         return false;
1516     }
1517
1518     m_currentKey = objectStoreDataKey.userKey();
1519
1520     int64_t version;
1521     const char* valuePosition = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), version);
1522     if (!valuePosition) {
1523         INTERNAL_READ_ERROR(LoadCurrentRow);
1524         return false;
1525     }
1526
1527     // FIXME: This re-encodes what was just decoded; try and optimize.
1528     m_recordIdentifier.reset(encodeIDBKey(*m_currentKey), version);
1529
1530     Vector<char> value;
1531     value.append(valuePosition, m_iterator->value().end() - valuePosition);
1532     m_currentValue = SharedBuffer::adoptVector(value);
1533     return true;
1534 }
1535
1536 class IndexKeyCursorImpl : public IDBBackingStore::Cursor {
1537 public:
1538     static PassRefPtr<IndexKeyCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1539     {
1540         return adoptRef(new IndexKeyCursorImpl(transaction, cursorOptions));
1541     }
1542
1543     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1544     {
1545         return adoptRef(new IndexKeyCursorImpl(this));
1546     }
1547
1548     // IDBBackingStore::Cursor
1549     virtual PassRefPtr<SharedBuffer> value() const { ASSERT_NOT_REACHED(); return 0; }
1550     virtual PassRefPtr<IDBKey> primaryKey() const { return m_primaryKey; }
1551     virtual const IDBBackingStore::RecordIdentifier& recordIdentifier() const { ASSERT_NOT_REACHED(); return m_recordIdentifier; }
1552     virtual bool loadCurrentRow();
1553
1554 private:
1555     IndexKeyCursorImpl(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1556         : IDBBackingStore::Cursor(transaction, cursorOptions)
1557     {
1558     }
1559
1560     IndexKeyCursorImpl(const IndexKeyCursorImpl* other)
1561         : IDBBackingStore::Cursor(other)
1562         , m_primaryKey(other->m_primaryKey)
1563     {
1564     }
1565
1566     RefPtr<IDBKey> m_primaryKey;
1567 };
1568
1569 bool IndexKeyCursorImpl::loadCurrentRow()
1570 {
1571     const char* keyPosition = m_iterator->key().begin();
1572     const char* keyLimit = m_iterator->key().end();
1573
1574     IndexDataKey indexDataKey;
1575     keyPosition = IndexDataKey::decode(keyPosition, keyLimit, &indexDataKey);
1576
1577     m_currentKey = indexDataKey.userKey();
1578
1579     int64_t indexDataVersion;
1580     const char* valuePosition = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), indexDataVersion);
1581     if (!valuePosition) {
1582         INTERNAL_READ_ERROR(LoadCurrentRow);
1583         return false;
1584     }
1585
1586     valuePosition = decodeIDBKey(valuePosition, m_iterator->value().end(), m_primaryKey);
1587     if (!valuePosition) {
1588         INTERNAL_READ_ERROR(LoadCurrentRow);
1589         return false;
1590     }
1591
1592     Vector<char> primaryLevelDBKey = ObjectStoreDataKey::encode(indexDataKey.databaseId(), indexDataKey.objectStoreId(), *m_primaryKey);
1593
1594     Vector<char> result;
1595     bool found = false;
1596     bool ok = m_transaction->safeGet(primaryLevelDBKey, result, found);
1597     if (!ok) {
1598         INTERNAL_READ_ERROR(LoadCurrentRow);
1599         return false;
1600     }
1601     if (!found) {
1602         m_transaction->remove(m_iterator->key());
1603         return false;
1604     }
1605
1606     int64_t objectStoreDataVersion;
1607     const char* t = decodeVarInt(result.begin(), result.end(), objectStoreDataVersion);
1608     if (!t) {
1609         INTERNAL_READ_ERROR(LoadCurrentRow);
1610         return false;
1611     }
1612
1613     if (objectStoreDataVersion != indexDataVersion) {
1614         m_transaction->remove(m_iterator->key());
1615         return false;
1616     }
1617
1618     return true;
1619 }
1620
1621 class IndexCursorImpl : public IDBBackingStore::Cursor {
1622 public:
1623     static PassRefPtr<IndexCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1624     {
1625         return adoptRef(new IndexCursorImpl(transaction, cursorOptions));
1626     }
1627
1628     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1629     {
1630         return adoptRef(new IndexCursorImpl(this));
1631     }
1632
1633     // IDBBackingStore::Cursor
1634     virtual PassRefPtr<SharedBuffer> value() const { return m_currentValue; }
1635     virtual PassRefPtr<IDBKey> primaryKey() const { return m_primaryKey; }
1636     virtual const IDBBackingStore::RecordIdentifier& recordIdentifier() const { ASSERT_NOT_REACHED(); return m_recordIdentifier; }
1637     bool loadCurrentRow();
1638
1639 private:
1640     IndexCursorImpl(LevelDBTransaction* transaction, const IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1641         : IDBBackingStore::Cursor(transaction, cursorOptions)
1642     {
1643     }
1644
1645     IndexCursorImpl(const IndexCursorImpl* other)
1646         : IDBBackingStore::Cursor(other)
1647         , m_primaryKey(other->m_primaryKey)
1648         , m_currentValue(other->m_currentValue)
1649         , m_primaryLevelDBKey(other->m_primaryLevelDBKey)
1650     {
1651     }
1652
1653     RefPtr<IDBKey> m_primaryKey;
1654     RefPtr<SharedBuffer> m_currentValue;
1655     Vector<char> m_primaryLevelDBKey;
1656 };
1657
1658 bool IndexCursorImpl::loadCurrentRow()
1659 {
1660     const char* keyPosition = m_iterator->key().begin();
1661     const char* keyLimit = m_iterator->key().end();
1662
1663     IndexDataKey indexDataKey;
1664     keyPosition = IndexDataKey::decode(keyPosition, keyLimit, &indexDataKey);
1665
1666     m_currentKey = indexDataKey.userKey();
1667
1668     const char* valuePosition = m_iterator->value().begin();
1669     const char* valueLimit = m_iterator->value().end();
1670
1671     int64_t indexDataVersion;
1672     valuePosition = decodeVarInt(valuePosition, valueLimit, indexDataVersion);
1673     if (!valuePosition) {
1674         INTERNAL_READ_ERROR(LoadCurrentRow);
1675         return false;
1676     }
1677     valuePosition = decodeIDBKey(valuePosition, valueLimit, m_primaryKey);
1678     if (!valuePosition) {
1679         INTERNAL_READ_ERROR(LoadCurrentRow);
1680         return false;
1681     }
1682
1683     m_primaryLevelDBKey = ObjectStoreDataKey::encode(indexDataKey.databaseId(), indexDataKey.objectStoreId(), *m_primaryKey);
1684
1685     Vector<char> result;
1686     bool found = false;
1687     bool ok = m_transaction->safeGet(m_primaryLevelDBKey, result, found);
1688     if (!ok) {
1689         INTERNAL_READ_ERROR(LoadCurrentRow);
1690         return false;
1691     }
1692     if (!found) {
1693         m_transaction->remove(m_iterator->key());
1694         return false;
1695     }
1696
1697     int64_t objectStoreDataVersion;
1698     valuePosition = decodeVarInt(result.begin(), result.end(), objectStoreDataVersion);
1699     if (!valuePosition) {
1700         INTERNAL_READ_ERROR(LoadCurrentRow);
1701         return false;
1702     }
1703
1704     if (objectStoreDataVersion != indexDataVersion) {
1705         m_transaction->remove(m_iterator->key());
1706         return false;
1707     }
1708
1709     Vector<char> value;
1710     value.append(valuePosition, result.end() - valuePosition);
1711     m_currentValue = SharedBuffer::adoptVector(value);
1712     return true;
1713 }
1714
1715 bool objectStoreCursorOptions(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IndexedDB::CursorDirection direction, IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1716 {
1717     bool lowerBound = range && range->lower();
1718     bool upperBound = range && range->upper();
1719     cursorOptions.forward = (direction == IndexedDB::CursorNextNoDuplicate || direction == IndexedDB::CursorNext);
1720     cursorOptions.unique = (direction == IndexedDB::CursorNextNoDuplicate || direction == IndexedDB::CursorPrevNoDuplicate);
1721
1722     if (!lowerBound) {
1723         cursorOptions.lowKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, minIDBKey());
1724         cursorOptions.lowOpen = true; // Not included.
1725     } else {
1726         cursorOptions.lowKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, *range->lower());
1727         cursorOptions.lowOpen = range->lowerOpen();
1728     }
1729
1730     if (!upperBound) {
1731         cursorOptions.highKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, maxIDBKey());
1732
1733         if (cursorOptions.forward)
1734             cursorOptions.highOpen = true; // Not included.
1735         else {
1736             // We need a key that exists.
1737             if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, cursorOptions.highKey))
1738                 return false;
1739             cursorOptions.highOpen = false;
1740         }
1741     } else {
1742         cursorOptions.highKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, *range->upper());
1743         cursorOptions.highOpen = range->upperOpen();
1744
1745         if (!cursorOptions.forward) {
1746             // For reverse cursors, we need a key that exists.
1747             Vector<char> foundHighKey;
1748             if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, foundHighKey))
1749                 return false;
1750
1751             // If the target key should not be included, but we end up with a smaller key, we should include that.
1752             if (cursorOptions.highOpen && compareIndexKeys(foundHighKey, cursorOptions.highKey) < 0)
1753                 cursorOptions.highOpen = false;
1754
1755             cursorOptions.highKey = foundHighKey;
1756         }
1757     }
1758
1759     return true;
1760 }
1761
1762 bool indexCursorOptions(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IndexedDB::CursorDirection direction, IDBBackingStore::Cursor::CursorOptions& cursorOptions)
1763 {
1764     ASSERT(transaction);
1765     bool lowerBound = range && range->lower();
1766     bool upperBound = range && range->upper();
1767     cursorOptions.forward = (direction == IndexedDB::CursorNextNoDuplicate || direction == IndexedDB::CursorNext);
1768     cursorOptions.unique = (direction == IndexedDB::CursorNextNoDuplicate || direction == IndexedDB::CursorPrevNoDuplicate);
1769
1770     if (!lowerBound) {
1771         cursorOptions.lowKey = IndexDataKey::encodeMinKey(databaseId, objectStoreId, indexId);
1772         cursorOptions.lowOpen = false; // Included.
1773     } else {
1774         cursorOptions.lowKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->lower());
1775         cursorOptions.lowOpen = range->lowerOpen();
1776     }
1777
1778     if (!upperBound) {
1779         cursorOptions.highKey = IndexDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
1780         cursorOptions.highOpen = false; // Included.
1781
1782         if (!cursorOptions.forward) { // We need a key that exists.
1783             if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, cursorOptions.highKey))
1784                 return false;
1785             cursorOptions.highOpen = false;
1786         }
1787     } else {
1788         cursorOptions.highKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->upper());
1789         cursorOptions.highOpen = range->upperOpen();
1790
1791         Vector<char> foundHighKey;
1792         if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, foundHighKey)) // Seek to the *last* key in the set of non-unique keys.
1793             return false;
1794
1795         // If the target key should not be included, but we end up with a smaller key, we should include that.
1796         if (cursorOptions.highOpen && compareIndexKeys(foundHighKey, cursorOptions.highKey) < 0)
1797             cursorOptions.highOpen = false;
1798
1799         cursorOptions.highKey = foundHighKey;
1800     }
1801
1802     return true;
1803 }
1804
1805 PassRefPtr<IDBBackingStore::Cursor> IDBBackingStore::openObjectStoreCursor(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IndexedDB::CursorDirection direction)
1806 {
1807     IDB_TRACE("IDBBackingStore::openObjectStoreCursor");
1808     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1809     IDBBackingStore::Cursor::CursorOptions cursorOptions;
1810     if (!objectStoreCursorOptions(levelDBTransaction, databaseId, objectStoreId, range, direction, cursorOptions))
1811         return 0;
1812     RefPtr<ObjectStoreCursorImpl> cursor = ObjectStoreCursorImpl::create(levelDBTransaction, cursorOptions);
1813     if (!cursor->firstSeek())
1814         return 0;
1815
1816     return cursor.release();
1817 }
1818
1819 PassRefPtr<IDBBackingStore::Cursor> IDBBackingStore::openObjectStoreKeyCursor(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IndexedDB::CursorDirection direction)
1820 {
1821     IDB_TRACE("IDBBackingStore::openObjectStoreKeyCursor");
1822     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1823     IDBBackingStore::Cursor::CursorOptions cursorOptions;
1824     if (!objectStoreCursorOptions(levelDBTransaction, databaseId, objectStoreId, range, direction, cursorOptions))
1825         return 0;
1826     RefPtr<ObjectStoreKeyCursorImpl> cursor = ObjectStoreKeyCursorImpl::create(levelDBTransaction, cursorOptions);
1827     if (!cursor->firstSeek())
1828         return 0;
1829
1830     return cursor.release();
1831 }
1832
1833 PassRefPtr<IDBBackingStore::Cursor> IDBBackingStore::openIndexKeyCursor(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IndexedDB::CursorDirection direction)
1834 {
1835     IDB_TRACE("IDBBackingStore::openIndexKeyCursor");
1836     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1837     IDBBackingStore::Cursor::CursorOptions cursorOptions;
1838     if (!indexCursorOptions(levelDBTransaction, databaseId, objectStoreId, indexId, range, direction, cursorOptions))
1839         return 0;
1840     RefPtr<IndexKeyCursorImpl> cursor = IndexKeyCursorImpl::create(levelDBTransaction, cursorOptions);
1841     if (!cursor->firstSeek())
1842         return 0;
1843
1844     return cursor.release();
1845 }
1846
1847 PassRefPtr<IDBBackingStore::Cursor> IDBBackingStore::openIndexCursor(IDBBackingStore::Transaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IndexedDB::CursorDirection direction)
1848 {
1849     IDB_TRACE("IDBBackingStore::openIndexCursor");
1850     LevelDBTransaction* levelDBTransaction = IDBBackingStore::Transaction::levelDBTransactionFrom(transaction);
1851     IDBBackingStore::Cursor::CursorOptions cursorOptions;
1852     if (!indexCursorOptions(levelDBTransaction, databaseId, objectStoreId, indexId, range, direction, cursorOptions))
1853         return 0;
1854     RefPtr<IndexCursorImpl> cursor = IndexCursorImpl::create(levelDBTransaction, cursorOptions);
1855     if (!cursor->firstSeek())
1856         return 0;
1857
1858     return cursor.release();
1859 }
1860
1861 IDBBackingStore::Transaction::Transaction(IDBBackingStore* backingStore)
1862     : m_backingStore(backingStore)
1863 {
1864 }
1865
1866 void IDBBackingStore::Transaction::begin()
1867 {
1868     IDB_TRACE("IDBBackingStore::Transaction::begin");
1869     ASSERT(!m_transaction);
1870     m_transaction = LevelDBTransaction::create(m_backingStore->m_db.get());
1871 }
1872
1873 bool IDBBackingStore::Transaction::commit()
1874 {
1875     IDB_TRACE("IDBBackingStore::Transaction::commit");
1876     ASSERT(m_transaction);
1877     bool result = m_transaction->commit();
1878     m_transaction.clear();
1879     if (!result)
1880         INTERNAL_WRITE_ERROR(TransactionCommit);
1881     return result;
1882 }
1883
1884 void IDBBackingStore::Transaction::rollback()
1885 {
1886     IDB_TRACE("IDBBackingStore::Transaction::rollback");
1887     ASSERT(m_transaction);
1888     m_transaction->rollback();
1889     m_transaction.clear();
1890 }
1891
1892 } // namespace WebCore
1893
1894 #endif // ENABLE(INDEXED_DATABASE)