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