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