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