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