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