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