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