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
49namespace WebCore {
50
51using namespace IDBLevelDBCoding;
52
53const int64_t KeyGeneratorInitialNumber = 1; // From the IndexedDB specification.
54
55enum 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
91static void putBool(LevelDBTransaction* transaction, const LevelDBSlice& key, bool value)
92{
93    transaction->put(key, encodeBool(value));
94}
95
96template <typename DBOrTransaction>
97static 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
110static void putInt(LevelDBTransaction* transaction, const LevelDBSlice& key, int64_t value)
111{
112    ASSERT(value >= 0);
113    transaction->put(key, encodeInt(value));
114}
115
116template <typename DBOrTransaction>
117WARN_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
130static void putVarInt(LevelDBTransaction* transaction, const LevelDBSlice& key, int64_t value)
131{
132    transaction->put(key, encodeVarInt(value));
133}
134
135template <typename DBOrTransaction>
136WARN_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
150static void putString(LevelDBTransaction* transaction, const LevelDBSlice& key, const String& value)
151{
152    transaction->put(key, encodeString(value));
153}
154
155static void putIDBKeyPath(LevelDBTransaction* transaction, const LevelDBSlice& key, const IDBKeyPath& value)
156{
157    transaction->put(key, encodeIDBKeyPath(value));
158}
159
160static int compareKeys(const LevelDBSlice& a, const LevelDBSlice& b)
161{
162    return compare(a, b);
163}
164
165int IDBBackingStoreLevelDB::compareIndexKeys(const LevelDBSlice& a, const LevelDBSlice& b)
166{
167    return compare(a, b, true);
168}
169
170class Comparator : public LevelDBComparator {
171public:
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.
179const int64_t latestKnownSchemaVersion = 2;
180WARN_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
215WARN_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
296template <typename DBOrTransaction>
297WARN_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
304template <typename DBOrTransaction>
305WARN_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
319class DefaultLevelDBFactory : public LevelDBFactory {
320public:
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
331IDBBackingStoreLevelDB::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
339IDBBackingStoreLevelDB::~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
346PassRefPtr<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
352PassRefPtr<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
405PassRefPtr<IDBBackingStoreLevelDB> IDBBackingStoreLevelDB::openInMemory(const String& identifier)
406{
407    DefaultLevelDBFactory levelDBFactory;
408    return IDBBackingStoreLevelDB::openInMemory(identifier, &levelDBFactory);
409}
410
411PassRefPtr<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
425PassRefPtr<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
436Vector<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
458bool 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
509void 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
567WARN_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.
595bool 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
612bool 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
620static 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
627void 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
662static 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.
678bool 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
775WARN_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
793bool 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
824bool 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
853bool 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
885WARN_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
911bool 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
941bool 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
954bool 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
971bool 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
1021bool 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
1041bool 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
1067static 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.
1084bool 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
1140WARN_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
1162bool 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
1183bool 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
1200bool 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
1219static 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
1247static 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
1264bool 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
1306bool 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
1327bool 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
1348bool 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
1381PassRefPtr<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
1398bool 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
1406class ObjectStoreKeyCursorImpl : public IDBBackingStoreCursorLevelDB {
1407public:
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
1422protected:
1423    virtual Vector<char> encodeKey(const IDBKey &key)
1424    {
1425        return ObjectStoreDataKey::encode(m_cursorOptions.databaseId, m_cursorOptions.objectStoreId, key);
1426    }
1427
1428private:
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
1440bool 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
1467class ObjectStoreCursorImpl : public IDBBackingStoreCursorLevelDB {
1468public:
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
1483protected:
1484    virtual Vector<char> encodeKey(const IDBKey &key)
1485    {
1486        return ObjectStoreDataKey::encode(m_cursorOptions.databaseId, m_cursorOptions.objectStoreId, key);
1487    }
1488
1489private:
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
1504bool 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
1534class IndexKeyCursorImpl final : public IDBBackingStoreCursorLevelDB {
1535public:
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
1552protected:
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
1558private:
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
1573bool 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
1625class IndexCursorImpl final : public IDBBackingStoreCursorLevelDB {
1626public:
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
1643protected:
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
1649private:
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
1668bool 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
1725static 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
1775static 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}
1824PassRefPtr<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
1839PassRefPtr<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
1853PassRefPtr<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
1867PassRefPtr<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
1881void IDBBackingStoreLevelDB::establishBackingStoreTransaction(int64_t transactionID)
1882{
1883    ASSERT(!m_backingStoreTransactions.contains(transactionID));
1884    m_backingStoreTransactions.set(transactionID, IDBBackingStoreTransactionLevelDB::create(transactionID, this));
1885}
1886
1887void 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)
1896