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