c7ef752cc0cc77453c28c4a9a137a8ce8d5e29c5
[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
29 #if ENABLE(INDEXED_DATABASE)
30 #if USE(LEVELDB)
31
32 #include <wtf/Assertions.h>
33 #include "FileSystem.h"
34 #include "IDBFactoryBackendImpl.h"
35 #include "IDBKeyRange.h"
36 #include "IDBLevelDBCoding.h"
37 #include "LevelDBComparator.h"
38 #include "LevelDBDatabase.h"
39 #include "LevelDBIterator.h"
40 #include "LevelDBSlice.h"
41 #include "LevelDBTransaction.h"
42 #include "SecurityOrigin.h"
43
44 namespace WebCore {
45
46 using namespace IDBLevelDBCoding;
47
48 template <typename DBOrTransaction>
49 static bool getBool(DBOrTransaction* db, const Vector<char>& key, bool& foundBool)
50 {
51     Vector<char> result;
52     if (!db->get(key, result))
53         return false;
54
55     foundBool = decodeBool(result.begin(), result.end());
56     return true;
57 }
58
59 template <typename DBOrTransaction>
60 static bool putBool(DBOrTransaction* db, const Vector<char>& key, bool value)
61 {
62     return db->put(key, encodeBool(value));
63 }
64
65 template <typename DBOrTransaction>
66 static bool getInt(DBOrTransaction* db, const Vector<char>& key, int64_t& foundInt)
67 {
68     Vector<char> result;
69     if (!db->get(key, result))
70         return false;
71
72     foundInt = decodeInt(result.begin(), result.end());
73     return true;
74 }
75
76 template <typename DBOrTransaction>
77 static bool putInt(DBOrTransaction* db, const Vector<char>& key, int64_t value)
78 {
79     return db->put(key, encodeInt(value));
80 }
81
82 template <typename DBOrTransaction>
83 static bool getString(DBOrTransaction* db, const Vector<char>& key, String& foundString)
84 {
85     Vector<char> result;
86     if (!db->get(key, result))
87         return false;
88
89     foundString = decodeString(result.begin(), result.end());
90     return true;
91 }
92
93 template <typename DBOrTransaction>
94 static bool putString(DBOrTransaction* db, const Vector<char> key, const String& value)
95 {
96     if (!db->put(key, encodeString(value)))
97         return false;
98     return true;
99 }
100
101 static int compareKeys(const LevelDBSlice& a, const LevelDBSlice& b)
102 {
103     return compare(a, b);
104 }
105
106 static int compareIndexKeys(const LevelDBSlice& a, const LevelDBSlice& b)
107 {
108     return compare(a, b, true);
109 }
110
111 class Comparator : public LevelDBComparator {
112 public:
113     virtual int compare(const LevelDBSlice& a, const LevelDBSlice& b) const { return IDBLevelDBCoding::compare(a, b); }
114     virtual const char* name() const { return "idb_cmp1"; }
115 };
116
117 static bool setUpMetadata(LevelDBDatabase* db)
118 {
119     const Vector<char> metaDataKey = SchemaVersionKey::encode();
120
121     int64_t schemaVersion = 0;
122     if (!getInt(db, metaDataKey, schemaVersion)) {
123         schemaVersion = 0;
124         if (!putInt(db, metaDataKey, schemaVersion))
125             return false;
126     }
127
128     // FIXME: Eventually, we'll need to be able to transition between schemas.
129     if (schemaVersion)
130         return false; // Don't know what to do with this version.
131
132     return true;
133 }
134
135 IDBLevelDBBackingStore::IDBLevelDBBackingStore(const String& identifier, IDBFactoryBackendImpl* factory, PassOwnPtr<LevelDBDatabase> db)
136     : m_identifier(identifier)
137     , m_factory(factory)
138     , m_db(db)
139 {
140     m_factory->addIDBBackingStore(identifier, this);
141 }
142
143 IDBLevelDBBackingStore::~IDBLevelDBBackingStore()
144 {
145     m_factory->removeIDBBackingStore(m_identifier);
146
147     // m_db's destructor uses m_comparator. The order of destruction is important.
148     m_db.clear();
149     m_comparator.clear();
150 }
151
152 PassRefPtr<IDBBackingStore> IDBLevelDBBackingStore::open(SecurityOrigin* securityOrigin, const String& pathBaseArg, const String& fileIdentifier, IDBFactoryBackendImpl* factory)
153 {
154     String pathBase = pathBaseArg;
155
156     OwnPtr<LevelDBComparator> comparator = adoptPtr(new Comparator());
157     OwnPtr<LevelDBDatabase> db;
158
159     if (pathBase.isEmpty())
160         db = LevelDBDatabase::openInMemory(comparator.get());
161     else {
162         if (!makeAllDirectories(pathBase)) {
163             LOG_ERROR("Unable to create IndexedDB database path %s", pathBase.utf8().data());
164             return PassRefPtr<IDBBackingStore>();
165         }
166         // FIXME: We should eventually use the same LevelDB database for all origins.
167         String path = pathByAppendingComponent(pathBase, securityOrigin->databaseIdentifier() + ".indexeddb.leveldb");
168
169         db = LevelDBDatabase::open(path, comparator.get());
170
171         if (!db) {
172             LOG_ERROR("IndexedDB backing store open failed, attempting cleanup");
173             bool success = LevelDBDatabase::destroy(path);
174             if (!success) {
175                 LOG_ERROR("IndexedDB backing store cleanup failed");
176                 return PassRefPtr<IDBBackingStore>();
177             }
178
179             LOG_ERROR("IndexedDB backing store cleanup succeeded, reopening");
180             db = LevelDBDatabase::open(path, comparator.get());
181             if (!db) {
182                 LOG_ERROR("IndexedDB backing store reopen after recovery failed");
183                 return PassRefPtr<IDBBackingStore>();
184             }
185         }
186     }
187
188     if (!db)
189         return PassRefPtr<IDBBackingStore>();
190
191     // FIXME: Handle comparator name changes.
192
193     RefPtr<IDBLevelDBBackingStore> backingStore(adoptRef(new IDBLevelDBBackingStore(fileIdentifier, factory, db.release())));
194     backingStore->m_comparator = comparator.release();
195
196     if (!setUpMetadata(backingStore->m_db.get()))
197         return PassRefPtr<IDBBackingStore>();
198
199     return backingStore.release();
200 }
201
202 void IDBLevelDBBackingStore::getDatabaseNames(Vector<String>& foundNames)
203 {
204     const Vector<char> startKey = DatabaseNameKey::encodeMinKeyForOrigin(m_identifier);
205     const Vector<char> stopKey = DatabaseNameKey::encodeStopKeyForOrigin(m_identifier);
206
207     ASSERT(foundNames.isEmpty());
208
209     OwnPtr<LevelDBIterator> it = m_db->createIterator();
210     for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
211         const char *p = it->key().begin();
212         const char *limit = it->key().end();
213
214         DatabaseNameKey databaseNameKey;
215         p = DatabaseNameKey::decode(p, limit, &databaseNameKey);
216         ASSERT(p);
217
218         foundNames.append(databaseNameKey.databaseName());
219     }
220 }
221
222 bool IDBLevelDBBackingStore::getIDBDatabaseMetaData(const String& name, String& foundVersion, int64_t& foundId)
223 {
224     const Vector<char> key = DatabaseNameKey::encode(m_identifier, name);
225
226     bool ok = getInt(m_db.get(), key, foundId);
227     if (!ok)
228         return false;
229
230     ok = getString(m_db.get(), DatabaseMetaDataKey::encode(foundId, DatabaseMetaDataKey::kUserVersion), foundVersion);
231     if (!ok)
232         return false;
233
234     return true;
235 }
236
237 static int64_t getNewDatabaseId(LevelDBDatabase* db)
238 {
239     int64_t maxDatabaseId = -1;
240     if (!getInt(db, MaxDatabaseIdKey::encode(), maxDatabaseId))
241         maxDatabaseId = 0;
242
243     ASSERT(maxDatabaseId >= 0);
244
245     int64_t databaseId = maxDatabaseId + 1;
246     if (!putInt(db, MaxDatabaseIdKey::encode(), databaseId))
247         return -1;
248
249     return databaseId;
250 }
251
252 bool IDBLevelDBBackingStore::createIDBDatabaseMetaData(const String& name, const String& version, int64_t& rowId)
253 {
254     rowId = getNewDatabaseId(m_db.get());
255     if (rowId < 0)
256         return false;
257
258     const Vector<char> key = DatabaseNameKey::encode(m_identifier, name);
259     if (!putInt(m_db.get(), key, rowId))
260         return false;
261     if (!putString(m_db.get(), DatabaseMetaDataKey::encode(rowId, DatabaseMetaDataKey::kUserVersion), version))
262         return false;
263     return true;
264 }
265
266 bool IDBLevelDBBackingStore::updateIDBDatabaseMetaData(int64_t rowId, const String& version)
267 {
268     ASSERT(m_currentTransaction);
269     if (!putString(m_currentTransaction.get(), DatabaseMetaDataKey::encode(rowId, DatabaseMetaDataKey::kUserVersion), version))
270         return false;
271
272     return true;
273 }
274
275 static bool deleteRange(LevelDBTransaction* transaction, const Vector<char>& begin, const Vector<char>& end)
276 {
277     OwnPtr<LevelDBIterator> it = transaction->createIterator();
278     for (it->seek(begin); it->isValid() && compareKeys(it->key(), end) < 0; it->next()) {
279         if (!transaction->remove(it->key()))
280             return false;
281     }
282
283     return true;
284 }
285
286
287 bool IDBLevelDBBackingStore::deleteDatabase(const String& name)
288 {
289     if (m_currentTransaction)
290         return false;
291
292     RefPtr<IDBLevelDBBackingStore::Transaction> transaction = IDBLevelDBBackingStore::Transaction::create(this);
293     transaction->begin();
294
295     int64_t databaseId;
296     String version;
297     if (!getIDBDatabaseMetaData(name, version, databaseId)) {
298         transaction->rollback();
299         return true;
300     }
301
302     const Vector<char> startKey = DatabaseMetaDataKey::encode(databaseId, DatabaseMetaDataKey::kOriginName);
303     const Vector<char> stopKey = DatabaseMetaDataKey::encode(databaseId + 1, DatabaseMetaDataKey::kOriginName);
304     if (!deleteRange(m_currentTransaction.get(), startKey, stopKey)) {
305         transaction->rollback();
306         return false;
307     }
308
309     const Vector<char> key = DatabaseNameKey::encode(m_identifier, name);
310     m_currentTransaction->remove(key);
311
312     return transaction->commit();
313 }
314
315 static bool checkObjectStoreAndMetaDataType(const LevelDBIterator* it, const Vector<char>& stopKey, int64_t objectStoreId, int64_t metaDataType)
316 {
317     if (!it->isValid() || compareKeys(it->key(), stopKey) >= 0)
318         return false;
319
320     ObjectStoreMetaDataKey metaDataKey;
321     const char* p = ObjectStoreMetaDataKey::decode(it->key().begin(), it->key().end(), &metaDataKey);
322     ASSERT_UNUSED(p, p);
323     if (metaDataKey.objectStoreId() != objectStoreId)
324         return false;
325     if (metaDataKey.metaDataType() != metaDataType)
326         return false;
327     return true;
328 }
329
330 void IDBLevelDBBackingStore::getObjectStores(int64_t databaseId, Vector<int64_t>& foundIds, Vector<String>& foundNames, Vector<String>& foundKeyPaths, Vector<bool>& foundAutoIncrementFlags)
331 {
332     const Vector<char> startKey = ObjectStoreMetaDataKey::encode(databaseId, 1, 0);
333     const Vector<char> stopKey = ObjectStoreMetaDataKey::encodeMaxKey(databaseId);
334
335     ASSERT(foundIds.isEmpty());
336     ASSERT(foundNames.isEmpty());
337     ASSERT(foundKeyPaths.isEmpty());
338     ASSERT(foundAutoIncrementFlags.isEmpty());
339
340     OwnPtr<LevelDBIterator> it = m_db->createIterator();
341     it->seek(startKey);
342     while (it->isValid() && compareKeys(it->key(), stopKey) < 0) {
343         const char *p = it->key().begin();
344         const char *limit = it->key().end();
345
346         ObjectStoreMetaDataKey metaDataKey;
347         p = ObjectStoreMetaDataKey::decode(p, limit, &metaDataKey);
348         ASSERT(p);
349         if (metaDataKey.metaDataType() != ObjectStoreMetaDataKey::kName) {
350             LOG_ERROR("Internal Indexed DB error.");
351             // Possible stale metadata, but don't fail the load.
352             it->next();
353             continue;
354         }
355
356         int64_t objectStoreId = metaDataKey.objectStoreId();
357
358         // FIXME: Do this by direct key lookup rather than iteration, to simplify.
359         String objectStoreName = decodeString(it->value().begin(), it->value().end());
360
361         it->next();
362         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::kKeyPath)) {
363             LOG_ERROR("Internal Indexed DB error.");
364             return;
365         }
366         String keyPath = decodeString(it->value().begin(), it->value().end());
367         bool hasKeyPath = true;
368
369         it->next();
370         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::kAutoIncrement)) {
371             LOG_ERROR("Internal Indexed DB error.");
372             return;
373         }
374         bool autoIncrement = decodeBool(it->value().begin(), it->value().end());
375
376         it->next(); // Is evicatble.
377         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::kEvictable)) {
378             LOG_ERROR("Internal Indexed DB error.");
379             return;
380         }
381
382         it->next(); // Last version.
383         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::kLastVersion)) {
384             LOG_ERROR("Internal Indexed DB error.");
385             return;
386         }
387
388         it->next(); // Maximum index id allocated.
389         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::kMaxIndexId)) {
390             LOG_ERROR("Internal Indexed DB error.");
391             return;
392         }
393
394         it->next(); // [optional] has key path (is not null)
395         if (checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::kHasKeyPath)) {
396             hasKeyPath = decodeBool(it->value().begin(), it->value().end());
397             if (!hasKeyPath && !keyPath.isEmpty()) {
398                 LOG_ERROR("Internal Indexed DB error.");
399                 return;
400             }
401             it->next();
402         }
403
404         foundIds.append(objectStoreId);
405         foundNames.append(objectStoreName);
406         foundKeyPaths.append(hasKeyPath ? keyPath : String());
407         foundAutoIncrementFlags.append(autoIncrement);
408     }
409 }
410
411 static int64_t getNewObjectStoreId(LevelDBTransaction* transaction, int64_t databaseId)
412 {
413     int64_t maxObjectStoreId = -1;
414     const Vector<char> maxObjectStoreIdKey = DatabaseMetaDataKey::encode(databaseId, DatabaseMetaDataKey::kMaxObjectStoreId);
415     if (!getInt(transaction, maxObjectStoreIdKey, maxObjectStoreId))
416         maxObjectStoreId = 0;
417
418     ASSERT(maxObjectStoreId >= 0);
419
420     int64_t objectStoreId = maxObjectStoreId + 1;
421     if (!putInt(transaction, maxObjectStoreIdKey, objectStoreId))
422         return -1;
423
424     return objectStoreId;
425 }
426
427 bool IDBLevelDBBackingStore::createObjectStore(int64_t databaseId, const String& name, const String& keyPath, bool autoIncrement, int64_t& assignedObjectStoreId)
428 {
429     ASSERT(m_currentTransaction);
430     int64_t objectStoreId = getNewObjectStoreId(m_currentTransaction.get(), databaseId);
431     if (objectStoreId < 0)
432         return false;
433
434     const Vector<char> nameKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::kName);
435     const Vector<char> keyPathKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::kKeyPath);
436     const Vector<char> autoIncrementKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::kAutoIncrement);
437     const Vector<char> evictableKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::kEvictable);
438     const Vector<char> lastVersionKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::kLastVersion);
439     const Vector<char> maxIndexIdKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::kMaxIndexId);
440     const Vector<char> hasKeyPathKey  = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::kHasKeyPath);
441     const Vector<char> namesKey = ObjectStoreNamesKey::encode(databaseId, name);
442
443     bool ok = putString(m_currentTransaction.get(), nameKey, name);
444     if (!ok) {
445         LOG_ERROR("Internal Indexed DB error.");
446         return false;
447     }
448
449     ok = putString(m_currentTransaction.get(), keyPathKey, keyPath);
450     if (!ok) {
451         LOG_ERROR("Internal Indexed DB error.");
452         return false;
453     }
454
455     ok = putInt(m_currentTransaction.get(), autoIncrementKey, autoIncrement);
456     if (!ok) {
457         LOG_ERROR("Internal Indexed DB error.");
458         return false;
459     }
460
461     ok = putInt(m_currentTransaction.get(), evictableKey, false);
462     if (!ok) {
463         LOG_ERROR("Internal Indexed DB error.");
464         return false;
465     }
466
467     ok = putInt(m_currentTransaction.get(), lastVersionKey, 1);
468     if (!ok) {
469         LOG_ERROR("Internal Indexed DB error.");
470         return false;
471     }
472
473     ok = putInt(m_currentTransaction.get(), maxIndexIdKey, kMinimumIndexId);
474     if (!ok) {
475         LOG_ERROR("Internal Indexed DB error.");
476         return false;
477     }
478
479     ok = putBool(m_currentTransaction.get(), hasKeyPathKey, !keyPath.isNull());
480     if (!ok) {
481         LOG_ERROR("Internal Indexed DB error.");
482         return false;
483     }
484
485     ok = putInt(m_currentTransaction.get(), namesKey, objectStoreId);
486     if (!ok) {
487         LOG_ERROR("Internal Indexed DB error.");
488         return false;
489     }
490
491     assignedObjectStoreId = objectStoreId;
492
493     return true;
494 }
495
496 void IDBLevelDBBackingStore::deleteObjectStore(int64_t databaseId, int64_t objectStoreId)
497 {
498     ASSERT(m_currentTransaction);
499
500     String objectStoreName;
501     getString(m_currentTransaction.get(), ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::kName), objectStoreName);
502
503     if (!deleteRange(m_currentTransaction.get(), ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, 0), ObjectStoreMetaDataKey::encodeMaxKey(databaseId, objectStoreId)))
504         return; // FIXME: Report error.
505
506     m_currentTransaction->remove(ObjectStoreNamesKey::encode(databaseId, objectStoreName));
507
508     if (!deleteRange(m_currentTransaction.get(), IndexFreeListKey::encode(databaseId, objectStoreId, 0), IndexFreeListKey::encodeMaxKey(databaseId, objectStoreId)))
509         return; // FIXME: Report error.
510     if (!deleteRange(m_currentTransaction.get(), IndexMetaDataKey::encode(databaseId, objectStoreId, 0, 0), IndexMetaDataKey::encodeMaxKey(databaseId, objectStoreId)))
511         return; // FIXME: Report error.
512
513     clearObjectStore(databaseId, objectStoreId);
514 }
515
516 String IDBLevelDBBackingStore::getObjectStoreRecord(int64_t databaseId, int64_t objectStoreId, const IDBKey& key)
517 {
518     const Vector<char> leveldbKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
519     Vector<char> data;
520
521     ASSERT(m_currentTransaction);
522     if (!m_currentTransaction->get(leveldbKey, data))
523         return String();
524
525     int64_t version;
526     const char* p = decodeVarInt(data.begin(), data.end(), version);
527     if (!p)
528         return String();
529     (void) version;
530
531     return decodeString(p, data.end());
532 }
533
534 namespace {
535 class LevelDBRecordIdentifier : public IDBBackingStore::ObjectStoreRecordIdentifier {
536 public:
537     static PassRefPtr<LevelDBRecordIdentifier> create(const Vector<char>& primaryKey, int64_t version) { return adoptRef(new LevelDBRecordIdentifier(primaryKey, version)); }
538     static PassRefPtr<LevelDBRecordIdentifier> create() { return adoptRef(new LevelDBRecordIdentifier()); }
539
540     virtual bool isValid() const { return m_primaryKey.isEmpty(); }
541     Vector<char> primaryKey() const { return m_primaryKey; }
542     void setPrimaryKey(const Vector<char>& primaryKey) { m_primaryKey = primaryKey; }
543     int64_t version() const { return m_version; }
544     void setVersion(int64_t version) { m_version = version; }
545
546 private:
547     LevelDBRecordIdentifier(const Vector<char>& primaryKey, int64_t version) : m_primaryKey(primaryKey), m_version(version) { ASSERT(!primaryKey.isEmpty()); }
548     LevelDBRecordIdentifier() : m_primaryKey(), m_version(-1) {}
549
550     Vector<char> m_primaryKey; // FIXME: Make it more clear that this is the *encoded* version of the key.
551     int64_t m_version;
552 };
553 }
554
555 static int64_t getNewVersionNumber(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId)
556 {
557     const Vector<char> lastVersionKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::kLastVersion);
558
559     int64_t lastVersion = -1;
560     if (!getInt(transaction, lastVersionKey, lastVersion))
561         lastVersion = 0;
562
563     ASSERT(lastVersion >= 0);
564
565     int64_t version = lastVersion + 1;
566     bool ok = putInt(transaction, lastVersionKey, version);
567     ASSERT_UNUSED(ok, ok);
568
569     ASSERT(version > lastVersion); // FIXME: Think about how we want to handle the overflow scenario.
570
571     return version;
572 }
573
574 bool IDBLevelDBBackingStore::putObjectStoreRecord(int64_t databaseId, int64_t objectStoreId, const IDBKey& key, const String& value, ObjectStoreRecordIdentifier* recordIdentifier)
575 {
576     ASSERT(m_currentTransaction);
577     int64_t version = getNewVersionNumber(m_currentTransaction.get(), databaseId, objectStoreId);
578     const Vector<char> objectStoredataKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
579
580     Vector<char> v;
581     v.append(encodeVarInt(version));
582     v.append(encodeString(value));
583
584     if (!m_currentTransaction->put(objectStoredataKey, v))
585         return false;
586
587     const Vector<char> existsEntryKey = ExistsEntryKey::encode(databaseId, objectStoreId, key);
588     if (!m_currentTransaction->put(existsEntryKey, encodeInt(version)))
589         return false;
590
591     LevelDBRecordIdentifier* levelDBRecordIdentifier = static_cast<LevelDBRecordIdentifier*>(recordIdentifier);
592     levelDBRecordIdentifier->setPrimaryKey(encodeIDBKey(key));
593     levelDBRecordIdentifier->setVersion(version);
594     return true;
595 }
596
597 void IDBLevelDBBackingStore::clearObjectStore(int64_t databaseId, int64_t objectStoreId)
598 {
599     ASSERT(m_currentTransaction);
600     const Vector<char> startKey = KeyPrefix(databaseId, objectStoreId, 0).encode();
601     const Vector<char> stopKey = KeyPrefix(databaseId, objectStoreId + 1, 0).encode();
602
603     deleteRange(m_currentTransaction.get(), startKey, stopKey);
604 }
605
606 PassRefPtr<IDBBackingStore::ObjectStoreRecordIdentifier> IDBLevelDBBackingStore::createInvalidRecordIdentifier()
607 {
608     return LevelDBRecordIdentifier::create();
609 }
610
611 void IDBLevelDBBackingStore::deleteObjectStoreRecord(int64_t databaseId, int64_t objectStoreId, const ObjectStoreRecordIdentifier* recordIdentifier)
612 {
613     ASSERT(m_currentTransaction);
614     const LevelDBRecordIdentifier* levelDBRecordIdentifier = static_cast<const LevelDBRecordIdentifier*>(recordIdentifier);
615
616     const Vector<char> objectStoreDataKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, levelDBRecordIdentifier->primaryKey());
617     m_currentTransaction->remove(objectStoreDataKey);
618
619     const Vector<char> existsEntryKey = ExistsEntryKey::encode(databaseId, objectStoreId, levelDBRecordIdentifier->primaryKey());
620     m_currentTransaction->remove(existsEntryKey);
621 }
622
623 int64_t IDBLevelDBBackingStore::nextAutoIncrementNumber(int64_t databaseId, int64_t objectStoreId)
624 {
625     ASSERT(m_currentTransaction);
626     const Vector<char> startKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, minIDBKey());
627     const Vector<char> stopKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, maxIDBKey());
628
629     OwnPtr<LevelDBIterator> it = m_currentTransaction->createIterator();
630
631     int64_t maxNumericKey = 0;
632
633     // FIXME: This does a forward scan over all keys. Improve it.
634     // Since all dates > all numbers, create Date(-Infinity) and seek backwards.
635
636     for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
637         const char *p = it->key().begin();
638         const char *limit = it->key().end();
639
640         ObjectStoreDataKey dataKey;
641         p = ObjectStoreDataKey::decode(p, limit, &dataKey);
642         ASSERT(p);
643
644         if (dataKey.userKey()->type() == IDBKey::NumberType) {
645             int64_t n = static_cast<int64_t>(dataKey.userKey()->number());
646             if (n > maxNumericKey)
647                 maxNumericKey = n;
648         }
649     }
650
651     return maxNumericKey + 1;
652 }
653
654 bool IDBLevelDBBackingStore::keyExistsInObjectStore(int64_t databaseId, int64_t objectStoreId, const IDBKey& key, ObjectStoreRecordIdentifier* foundRecordIdentifier)
655 {
656     ASSERT(m_currentTransaction);
657     const Vector<char> leveldbKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
658     Vector<char> data;
659
660     if (!m_currentTransaction->get(leveldbKey, data))
661         return false;
662
663     int64_t version;
664     if (!decodeVarInt(data.begin(), data.end(), version))
665         return false;
666
667     LevelDBRecordIdentifier* levelDBRecordIdentifier = static_cast<LevelDBRecordIdentifier*>(foundRecordIdentifier);
668     levelDBRecordIdentifier->setPrimaryKey(encodeIDBKey(key));
669     levelDBRecordIdentifier->setVersion(version);
670     return true;
671 }
672
673 bool IDBLevelDBBackingStore::forEachObjectStoreRecord(int64_t databaseId, int64_t objectStoreId, ObjectStoreRecordCallback& callback)
674 {
675     ASSERT(m_currentTransaction);
676     const Vector<char> startKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, minIDBKey());
677     const Vector<char> stopKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, maxIDBKey());
678
679     OwnPtr<LevelDBIterator> it = m_currentTransaction->createIterator();
680     for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
681         const char *p = it->key().begin();
682         const char *limit = it->key().end();
683         ObjectStoreDataKey dataKey;
684         p = ObjectStoreDataKey::decode(p, limit, &dataKey);
685         ASSERT(p);
686
687         RefPtr<IDBKey> primaryKey = dataKey.userKey();
688
689         int64_t version;
690         const char* q = decodeVarInt(it->value().begin(), it->value().end(), version);
691         if (!q)
692             return false;
693
694         RefPtr<LevelDBRecordIdentifier> ri = LevelDBRecordIdentifier::create(encodeIDBKey(*primaryKey), version);
695         String idbValue = decodeString(q, it->value().end());
696
697         if (!callback.callback(ri.get(), idbValue))
698             return false;
699     }
700
701     return true;
702 }
703
704 static bool checkIndexAndMetaDataKey(const LevelDBIterator* it, const Vector<char>& stopKey, int64_t indexId, unsigned char metaDataType)
705 {
706     if (!it->isValid() || compareKeys(it->key(), stopKey) >= 0)
707         return false;
708
709     IndexMetaDataKey metaDataKey;
710     const char* p = IndexMetaDataKey::decode(it->key().begin(), it->key().end(), &metaDataKey);
711     ASSERT_UNUSED(p, p);
712     if (metaDataKey.indexId() != indexId)
713         return false;
714     if (metaDataKey.metaDataType() != metaDataType)
715         return false;
716     return true;
717 }
718
719
720 void IDBLevelDBBackingStore::getIndexes(int64_t databaseId, int64_t objectStoreId, Vector<int64_t>& foundIds, Vector<String>& foundNames, Vector<String>& foundKeyPaths, Vector<bool>& foundUniqueFlags, Vector<bool>& foundMultiEntryFlags)
721 {
722     const Vector<char> startKey = IndexMetaDataKey::encode(databaseId, objectStoreId, 0, 0);
723     const Vector<char> stopKey = IndexMetaDataKey::encode(databaseId, objectStoreId + 1, 0, 0);
724
725     ASSERT(foundIds.isEmpty());
726     ASSERT(foundNames.isEmpty());
727     ASSERT(foundKeyPaths.isEmpty());
728     ASSERT(foundUniqueFlags.isEmpty());
729     ASSERT(foundMultiEntryFlags.isEmpty());
730
731     OwnPtr<LevelDBIterator> it = m_db->createIterator();
732     it->seek(startKey);
733     while (it->isValid() && compareKeys(it->key(), stopKey) < 0) {
734         const char* p = it->key().begin();
735         const char* limit = it->key().end();
736
737         IndexMetaDataKey metaDataKey;
738         p = IndexMetaDataKey::decode(p, limit, &metaDataKey);
739         ASSERT(p);
740         if (metaDataKey.metaDataType() != IndexMetaDataKey::kName) {
741             LOG_ERROR("Internal Indexed DB error.");
742             // Possible stale metadata due to http://webkit.org/b/85557 but don't fail the load.
743             it->next();
744             continue;
745         }
746
747         // FIXME: Do this by direct key lookup rather than iteration, to simplify.
748         int64_t indexId = metaDataKey.indexId();
749         String indexName = decodeString(it->value().begin(), it->value().end());
750
751         it->next(); // unique flag
752         if (!checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::kUnique)) {
753             LOG_ERROR("Internal Indexed DB error.");
754             return;
755         }
756         bool indexUnique = decodeBool(it->value().begin(), it->value().end());
757
758         it->next(); // keyPath
759         if (!checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::kKeyPath)) {
760             LOG_ERROR("Internal Indexed DB error.");
761             return;
762         }
763         String keyPath = decodeString(it->value().begin(), it->value().end());
764
765         it->next(); // [optional] multiEntry flag
766         bool indexMultiEntry = false;
767         if (checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::kMultiEntry)) {
768             indexMultiEntry = decodeBool(it->value().begin(), it->value().end());
769             it->next();
770         }
771
772         foundIds.append(indexId);
773         foundNames.append(indexName);
774         foundKeyPaths.append(keyPath);
775         foundUniqueFlags.append(indexUnique);
776         foundMultiEntryFlags.append(indexMultiEntry);
777     }
778 }
779
780 static int64_t getNewIndexId(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId)
781 {
782     int64_t maxIndexId = -1;
783     const Vector<char> maxIndexIdKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::kMaxIndexId);
784     if (!getInt(transaction, maxIndexIdKey, maxIndexId))
785         maxIndexId = kMinimumIndexId;
786
787     ASSERT(maxIndexId >= 0);
788
789     int64_t indexId = maxIndexId + 1;
790     if (!putInt(transaction, maxIndexIdKey, indexId))
791         return -1;
792
793     return indexId;
794 }
795
796 bool IDBLevelDBBackingStore::createIndex(int64_t databaseId, int64_t objectStoreId, const String& name, const String& keyPath, bool isUnique, bool isMultiEntry, int64_t& indexId)
797 {
798     ASSERT(m_currentTransaction);
799     indexId = getNewIndexId(m_currentTransaction.get(), databaseId, objectStoreId);
800     if (indexId < 0)
801         return false;
802
803     const Vector<char> nameKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::kName);
804     const Vector<char> uniqueKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::kUnique);
805     const Vector<char> keyPathKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::kKeyPath);
806     const Vector<char> multiEntryKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::kMultiEntry);
807
808     bool ok = putString(m_currentTransaction.get(), nameKey, name);
809     if (!ok) {
810         LOG_ERROR("Internal Indexed DB error.");
811         return false;
812     }
813
814     ok = putBool(m_currentTransaction.get(), uniqueKey, isUnique);
815     if (!ok) {
816         LOG_ERROR("Internal Indexed DB error.");
817         return false;
818     }
819
820     ok = putString(m_currentTransaction.get(), keyPathKey, keyPath);
821     if (!ok) {
822         LOG_ERROR("Internal Indexed DB error.");
823         return false;
824     }
825
826     ok = putBool(m_currentTransaction.get(), multiEntryKey, isMultiEntry);
827     if (!ok) {
828         LOG_ERROR("Internal Indexed DB error.");
829         return false;
830     }
831
832     return true;
833 }
834
835 void IDBLevelDBBackingStore::deleteIndex(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
836 {
837     ASSERT(m_currentTransaction);
838
839     const Vector<char> indexMetaDataStart = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, 0);
840     const Vector<char> indexMetaDataEnd = IndexMetaDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
841
842     if (!deleteRange(m_currentTransaction.get(), indexMetaDataStart, indexMetaDataEnd)) {
843         LOG_ERROR("Internal Indexed DB error.");
844         return;
845     }
846
847     const Vector<char> indexDataStart = IndexDataKey::encodeMinKey(databaseId, objectStoreId, indexId);
848     const Vector<char> indexDataEnd = IndexDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
849
850     if (!deleteRange(m_currentTransaction.get(), indexDataStart, indexDataEnd)) {
851         LOG_ERROR("Internal Indexed DB error.");
852         return;
853     }
854 }
855
856 bool IDBLevelDBBackingStore::putIndexDataForRecord(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, const ObjectStoreRecordIdentifier* recordIdentifier)
857 {
858     ASSERT(indexId >= kMinimumIndexId);
859     const LevelDBRecordIdentifier* levelDBRecordIdentifier = static_cast<const LevelDBRecordIdentifier*>(recordIdentifier);
860
861     ASSERT(m_currentTransaction);
862     const Vector<char> indexDataKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, encodeIDBKey(key), levelDBRecordIdentifier->primaryKey());
863
864     Vector<char> data;
865     data.append(encodeVarInt(levelDBRecordIdentifier->version()));
866     data.append(levelDBRecordIdentifier->primaryKey());
867
868     return m_currentTransaction->put(indexDataKey, data);
869 }
870
871 static bool findGreatestKeyLessThanOrEqual(LevelDBTransaction* transaction, const Vector<char>& target, Vector<char>& foundKey)
872 {
873     OwnPtr<LevelDBIterator> it = transaction->createIterator();
874     it->seek(target);
875
876     if (!it->isValid()) {
877         it->seekToLast();
878         if (!it->isValid())
879             return false;
880     }
881
882     while (compareIndexKeys(it->key(), target) > 0) {
883         it->prev();
884         if (!it->isValid())
885             return false;
886     }
887
888     do {
889         foundKey.clear();
890         foundKey.append(it->key().begin(), it->key().end() - it->key().begin());
891
892         // There can be several index keys that compare equal. We want the last one.
893         it->next();
894     } while (it->isValid() && !compareIndexKeys(it->key(), target));
895
896     return true;
897 }
898
899 bool IDBLevelDBBackingStore::deleteIndexDataForRecord(int64_t, int64_t, int64_t, const ObjectStoreRecordIdentifier*)
900 {
901     // FIXME: This isn't needed since we invalidate index data via the version number mechanism.
902     return true;
903 }
904
905 String IDBLevelDBBackingStore::getObjectViaIndex(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key)
906 {
907     RefPtr<IDBKey> primaryKey = getPrimaryKeyViaIndex(databaseId, objectStoreId, indexId, key);
908     if (!primaryKey)
909         return String();
910
911     return getObjectStoreRecord(databaseId, objectStoreId, *primaryKey);
912 }
913
914 static bool versionExists(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t version, const Vector<char>& encodedPrimaryKey)
915 {
916     const Vector<char> key = ExistsEntryKey::encode(databaseId, objectStoreId, encodedPrimaryKey);
917     Vector<char> data;
918
919     if (!transaction->get(key, data))
920         return false;
921
922     return decodeInt(data.begin(), data.end()) == version;
923 }
924
925 static bool findKeyInIndex(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, Vector<char>& foundEncodedPrimaryKey)
926 {
927     ASSERT(foundEncodedPrimaryKey.isEmpty());
928
929     const Vector<char> leveldbKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, key);
930     OwnPtr<LevelDBIterator> it = transaction->createIterator();
931     it->seek(leveldbKey);
932
933     for (;;) {
934         if (!it->isValid())
935             return false;
936         if (compareIndexKeys(it->key(), leveldbKey) > 0)
937             return false;
938
939         int64_t version;
940         const char* p = decodeVarInt(it->value().begin(), it->value().end(), version);
941         if (!p)
942             return false;
943         foundEncodedPrimaryKey.append(p, it->value().end() - p);
944
945         if (!versionExists(transaction, databaseId, objectStoreId, version, foundEncodedPrimaryKey)) {
946             // Delete stale index data entry and continue.
947             transaction->remove(it->key());
948             it->next();
949             continue;
950         }
951
952         return true;
953     }
954 }
955
956 PassRefPtr<IDBKey> IDBLevelDBBackingStore::getPrimaryKeyViaIndex(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key)
957 {
958     ASSERT(m_currentTransaction);
959
960     Vector<char> foundEncodedPrimaryKey;
961     if (findKeyInIndex(m_currentTransaction.get(), databaseId, objectStoreId, indexId, key, foundEncodedPrimaryKey)) {
962         RefPtr<IDBKey> primaryKey;
963         decodeIDBKey(foundEncodedPrimaryKey.begin(), foundEncodedPrimaryKey.end(), primaryKey);
964         return primaryKey.release();
965     }
966
967     return 0;
968 }
969
970 bool IDBLevelDBBackingStore::keyExistsInIndex(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& indexKey, RefPtr<IDBKey>& foundPrimaryKey)
971 {
972     ASSERT(m_currentTransaction);
973
974     Vector<char> foundEncodedPrimaryKey;
975     if (!findKeyInIndex(m_currentTransaction.get(), databaseId, objectStoreId, indexId, indexKey, foundEncodedPrimaryKey))
976         return false;
977
978     decodeIDBKey(foundEncodedPrimaryKey.begin(), foundEncodedPrimaryKey.end(), foundPrimaryKey);
979     return true;
980 }
981
982 namespace {
983
984 struct CursorOptions {
985     Vector<char> lowKey;
986     bool lowOpen;
987     Vector<char> highKey;
988     bool highOpen;
989     bool forward;
990     bool unique;
991 };
992
993 class CursorImplCommon : public IDBBackingStore::Cursor {
994 public:
995     // IDBBackingStore::Cursor
996     virtual bool advance(unsigned long);
997     virtual bool continueFunction(const IDBKey* = 0, IteratorState = Seek);
998     virtual PassRefPtr<IDBKey> key() { return m_currentKey; }
999     virtual PassRefPtr<IDBKey> primaryKey() { return m_currentKey; }
1000     virtual String value() = 0;
1001     virtual PassRefPtr<IDBBackingStore::ObjectStoreRecordIdentifier> objectStoreRecordIdentifier() = 0;
1002     virtual int64_t indexDataId() = 0;
1003     virtual void close() { }
1004
1005     virtual bool loadCurrentRow() = 0;
1006     bool firstSeek();
1007
1008 protected:
1009     CursorImplCommon(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1010         : m_transaction(transaction)
1011         , m_cursorOptions(cursorOptions)
1012     {
1013     }
1014
1015     CursorImplCommon(const CursorImplCommon* other)
1016         : m_transaction(other->m_transaction)
1017         , m_cursorOptions(other->m_cursorOptions)
1018         , m_currentKey(other->m_currentKey)
1019     {
1020         if (other->m_iterator) {
1021             m_iterator = m_transaction->createIterator();
1022
1023             if (other->m_iterator->isValid()) {
1024                 m_iterator->seek(other->m_iterator->key());
1025                 ASSERT(m_iterator->isValid());
1026             }
1027         }
1028     }
1029
1030     virtual ~CursorImplCommon() {}
1031
1032     bool isPastBounds() const;
1033     bool haveEnteredRange() const;
1034
1035     LevelDBTransaction* m_transaction;
1036     CursorOptions m_cursorOptions;
1037     OwnPtr<LevelDBIterator> m_iterator;
1038     RefPtr<IDBKey> m_currentKey;
1039 };
1040
1041 bool CursorImplCommon::firstSeek()
1042 {
1043     m_iterator = m_transaction->createIterator();
1044     if (m_cursorOptions.forward)
1045         m_iterator->seek(m_cursorOptions.lowKey);
1046     else
1047         m_iterator->seek(m_cursorOptions.highKey);
1048
1049     return continueFunction(0, Ready);
1050 }
1051
1052 bool CursorImplCommon::advance(unsigned long count)
1053 {
1054     while (count--) {
1055         if (!continueFunction())
1056             return false;
1057     }
1058     return true;
1059 }
1060
1061 bool CursorImplCommon::continueFunction(const IDBKey* key, IteratorState nextState)
1062 {
1063     RefPtr<IDBKey> previousKey = m_currentKey;
1064
1065     // When iterating with PREV_NO_DUPLICATE, spec requires that the
1066     // value we yield for each key is the first duplicate in forwards
1067     // order.
1068     RefPtr<IDBKey> lastDuplicateKey;
1069
1070     bool forward = m_cursorOptions.forward;
1071
1072     for (;;) {
1073         if (nextState == Seek) {
1074             if (forward)
1075                 m_iterator->next();
1076             else
1077                 m_iterator->prev();
1078         } else
1079             nextState = Seek; // for subsequent iterations
1080
1081         if (!m_iterator->isValid()) {
1082             if (!forward && lastDuplicateKey.get()) {
1083                 // We need to walk forward because we hit the end of
1084                 // the data.
1085                 forward = true;
1086                 continue;
1087             }
1088
1089             return false;
1090         }
1091
1092         if (isPastBounds()) {
1093             if (!forward && lastDuplicateKey.get()) {
1094                 // We need to walk forward because now we're beyond the
1095                 // bounds defined by the cursor.
1096                 forward = true;
1097                 continue;
1098             }
1099
1100             return false;
1101         }
1102
1103         if (!haveEnteredRange())
1104             continue;
1105
1106         // The row may not load because there's a stale entry in the
1107         // index. This is not fatal.
1108         if (!loadCurrentRow())
1109             continue;
1110
1111         if (key) {
1112             if (forward) {
1113                 if (m_currentKey->isLessThan(key))
1114                     continue;
1115             } else {
1116                 if (key->isLessThan(m_currentKey.get()))
1117                     continue;
1118             }
1119         }
1120
1121         if (m_cursorOptions.unique) {
1122
1123             if (m_currentKey->isEqual(previousKey.get())) {
1124                 // We should never be able to walk forward all the way
1125                 // to the previous key.
1126                 ASSERT(!lastDuplicateKey.get());
1127                 continue;
1128             }
1129
1130             if (!forward) {
1131                 if (!lastDuplicateKey.get()) {
1132                     lastDuplicateKey = m_currentKey;
1133                     continue;
1134                 }
1135
1136                 // We need to walk forward because we hit the boundary
1137                 // between key ranges.
1138                 if (!lastDuplicateKey->isEqual(m_currentKey.get())) {
1139                     forward = true;
1140                     continue;
1141                 }
1142
1143                 continue;
1144             }
1145         }
1146         break;
1147     }
1148
1149     ASSERT(!lastDuplicateKey.get() || (forward && lastDuplicateKey->isEqual(m_currentKey.get())));
1150     return true;
1151 }
1152
1153 bool CursorImplCommon::haveEnteredRange() const
1154 {
1155     if (m_cursorOptions.forward) {
1156         if (m_cursorOptions.lowOpen)
1157             return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) > 0;
1158
1159         return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) >= 0;
1160     }
1161     if (m_cursorOptions.highOpen)
1162         return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) < 0;
1163
1164     return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) <= 0;
1165 }
1166
1167 bool CursorImplCommon::isPastBounds() const
1168 {
1169     if (m_cursorOptions.forward) {
1170         if (m_cursorOptions.highOpen)
1171             return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) >= 0;
1172         return compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) > 0;
1173     }
1174
1175     if (m_cursorOptions.lowOpen)
1176         return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) <= 0;
1177     return compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) < 0;
1178 }
1179
1180 class ObjectStoreCursorImpl : public CursorImplCommon {
1181 public:
1182     static PassRefPtr<ObjectStoreCursorImpl> create(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1183     {
1184         return adoptRef(new ObjectStoreCursorImpl(transaction, cursorOptions));
1185     }
1186
1187     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1188     {
1189         return adoptRef(new ObjectStoreCursorImpl(this));
1190     }
1191
1192     // CursorImplCommon
1193     virtual String value() { return m_currentValue; }
1194     virtual PassRefPtr<IDBBackingStore::ObjectStoreRecordIdentifier> objectStoreRecordIdentifier() OVERRIDE
1195     {
1196         return m_identifier;
1197     }
1198     virtual int64_t indexDataId() { ASSERT_NOT_REACHED(); return 0; }
1199     virtual bool loadCurrentRow();
1200
1201 private:
1202     ObjectStoreCursorImpl(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1203         : CursorImplCommon(transaction, cursorOptions)
1204     {
1205     }
1206
1207     ObjectStoreCursorImpl(const ObjectStoreCursorImpl* other)
1208         : CursorImplCommon(other)
1209         , m_currentValue(other->m_currentValue)
1210     {
1211     }
1212
1213     String m_currentValue;
1214     RefPtr<LevelDBRecordIdentifier> m_identifier;
1215 };
1216
1217 bool ObjectStoreCursorImpl::loadCurrentRow()
1218 {
1219     const char* p = m_iterator->key().begin();
1220     const char* keyLimit = m_iterator->key().end();
1221
1222     ObjectStoreDataKey objectStoreDataKey;
1223     p = ObjectStoreDataKey::decode(p, keyLimit, &objectStoreDataKey);
1224     ASSERT(p);
1225     if (!p)
1226         return false;
1227
1228     m_currentKey = objectStoreDataKey.userKey();
1229
1230     int64_t version;
1231     const char* q = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), version);
1232     ASSERT(q);
1233     if (!q)
1234         return false;
1235
1236     // FIXME: This re-encodes what was just decoded; try and optimize.
1237     m_identifier = LevelDBRecordIdentifier::create(encodeIDBKey(*m_currentKey), version);
1238
1239     m_currentValue = decodeString(q, m_iterator->value().end());
1240
1241     return true;
1242 }
1243
1244 class IndexKeyCursorImpl : public CursorImplCommon {
1245 public:
1246     static PassRefPtr<IndexKeyCursorImpl> create(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1247     {
1248         return adoptRef(new IndexKeyCursorImpl(transaction, cursorOptions));
1249     }
1250
1251     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1252     {
1253         return adoptRef(new IndexKeyCursorImpl(this));
1254     }
1255
1256     // CursorImplCommon
1257     virtual String value() { ASSERT_NOT_REACHED(); return String(); }
1258     virtual PassRefPtr<IDBKey> primaryKey() { return m_primaryKey; }
1259     virtual PassRefPtr<IDBBackingStore::ObjectStoreRecordIdentifier> objectStoreRecordIdentifier() { ASSERT_NOT_REACHED(); return 0; }
1260     virtual int64_t indexDataId() { ASSERT_NOT_REACHED(); return 0; }
1261     virtual bool loadCurrentRow();
1262
1263 private:
1264     IndexKeyCursorImpl(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1265         : CursorImplCommon(transaction, cursorOptions)
1266     {
1267     }
1268
1269     IndexKeyCursorImpl(const IndexKeyCursorImpl* other)
1270         : CursorImplCommon(other)
1271         , m_primaryKey(other->m_primaryKey)
1272     {
1273     }
1274
1275     RefPtr<IDBKey> m_primaryKey;
1276 };
1277
1278 bool IndexKeyCursorImpl::loadCurrentRow()
1279 {
1280     const char* p = m_iterator->key().begin();
1281     const char* keyLimit = m_iterator->key().end();
1282     IndexDataKey indexDataKey;
1283     p = IndexDataKey::decode(p, keyLimit, &indexDataKey);
1284
1285     m_currentKey = indexDataKey.userKey();
1286
1287     int64_t indexDataVersion;
1288     const char* q = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), indexDataVersion);
1289     ASSERT(q);
1290     if (!q)
1291         return false;
1292
1293     q = decodeIDBKey(q, m_iterator->value().end(), m_primaryKey);
1294     ASSERT(q);
1295     if (!q)
1296         return false;
1297
1298     Vector<char> primaryLevelDBKey = ObjectStoreDataKey::encode(indexDataKey.databaseId(), indexDataKey.objectStoreId(), *m_primaryKey);
1299
1300     Vector<char> result;
1301     if (!m_transaction->get(primaryLevelDBKey, result)) {
1302         m_transaction->remove(m_iterator->key());
1303         return false;
1304     }
1305
1306     int64_t objectStoreDataVersion;
1307     const char* t = decodeVarInt(result.begin(), result.end(), objectStoreDataVersion);
1308     ASSERT(t);
1309     if (!t)
1310         return false;
1311
1312     if (objectStoreDataVersion != indexDataVersion) {
1313         m_transaction->remove(m_iterator->key());
1314         return false;
1315     }
1316
1317     return true;
1318 }
1319
1320 class IndexCursorImpl : public CursorImplCommon {
1321 public:
1322     static PassRefPtr<IndexCursorImpl> create(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1323     {
1324         return adoptRef(new IndexCursorImpl(transaction, cursorOptions));
1325     }
1326
1327     virtual PassRefPtr<IDBBackingStore::Cursor> clone()
1328     {
1329         return adoptRef(new IndexCursorImpl(this));
1330     }
1331
1332     // CursorImplCommon
1333     virtual String value() { return m_value; }
1334     virtual PassRefPtr<IDBKey> primaryKey() { return m_primaryKey; }
1335     virtual PassRefPtr<IDBBackingStore::ObjectStoreRecordIdentifier> objectStoreRecordIdentifier() { ASSERT_NOT_REACHED(); return 0; }
1336     virtual int64_t indexDataId() { ASSERT_NOT_REACHED(); return 0; }
1337     bool loadCurrentRow();
1338
1339 private:
1340     IndexCursorImpl(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1341         : CursorImplCommon(transaction, cursorOptions)
1342     {
1343     }
1344
1345     IndexCursorImpl(const IndexCursorImpl* other)
1346         : CursorImplCommon(other)
1347         , m_primaryKey(other->m_primaryKey)
1348         , m_value(other->m_value)
1349         , m_primaryLevelDBKey(other->m_primaryLevelDBKey)
1350     {
1351     }
1352
1353     RefPtr<IDBKey> m_primaryKey;
1354     String m_value;
1355     Vector<char> m_primaryLevelDBKey;
1356 };
1357
1358 bool IndexCursorImpl::loadCurrentRow()
1359 {
1360     const char *p = m_iterator->key().begin();
1361     const char *limit = m_iterator->key().end();
1362
1363     IndexDataKey indexDataKey;
1364     p = IndexDataKey::decode(p, limit, &indexDataKey);
1365
1366     m_currentKey = indexDataKey.userKey();
1367
1368     const char *q = m_iterator->value().begin();
1369     const char *valueLimit = m_iterator->value().end();
1370
1371     int64_t indexDataVersion;
1372     q = decodeVarInt(q, valueLimit, indexDataVersion);
1373     ASSERT(q);
1374     if (!q)
1375         return false;
1376     q = decodeIDBKey(q, valueLimit, m_primaryKey);
1377     ASSERT(q);
1378     if (!q)
1379         return false;
1380
1381     m_primaryLevelDBKey = ObjectStoreDataKey::encode(indexDataKey.databaseId(), indexDataKey.objectStoreId(), *m_primaryKey);
1382
1383     Vector<char> result;
1384     if (!m_transaction->get(m_primaryLevelDBKey, result)) {
1385         m_transaction->remove(m_iterator->key());
1386         return false;
1387     }
1388
1389     int64_t objectStoreDataVersion;
1390     const char* t = decodeVarInt(result.begin(), result.end(), objectStoreDataVersion);
1391     ASSERT(t);
1392     if (!t)
1393         return false;
1394
1395     if (objectStoreDataVersion != indexDataVersion) {
1396         m_transaction->remove(m_iterator->key());
1397         return false;
1398     }
1399
1400     m_value = decodeString(t, result.end());
1401     return true;
1402 }
1403
1404 }
1405
1406 PassRefPtr<IDBBackingStore::Cursor> IDBLevelDBBackingStore::openObjectStoreCursor(int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IDBCursor::Direction direction)
1407 {
1408     ASSERT(m_currentTransaction);
1409     CursorOptions cursorOptions;
1410
1411     bool lowerBound = range && range->lower();
1412     bool upperBound = range && range->upper();
1413     cursorOptions.forward = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::NEXT);
1414     cursorOptions.unique = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::PREV_NO_DUPLICATE);
1415
1416     if (!lowerBound) {
1417         cursorOptions.lowKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, minIDBKey());
1418         cursorOptions.lowOpen = true; // Not included.
1419     } else {
1420         cursorOptions.lowKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, *range->lower());
1421         cursorOptions.lowOpen = range->lowerOpen();
1422     }
1423
1424     if (!upperBound) {
1425         cursorOptions.highKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, maxIDBKey());
1426
1427         if (cursorOptions.forward)
1428             cursorOptions.highOpen = true; // Not included.
1429         else {
1430             // We need a key that exists.
1431             if (!findGreatestKeyLessThanOrEqual(m_currentTransaction.get(), cursorOptions.highKey, cursorOptions.highKey))
1432                 return 0;
1433             cursorOptions.highOpen = false;
1434         }
1435     } else {
1436         cursorOptions.highKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, *range->upper());
1437         cursorOptions.highOpen = range->upperOpen();
1438
1439         if (!cursorOptions.forward) {
1440             // For reverse cursors, we need a key that exists.
1441             Vector<char> foundHighKey;
1442             if (!findGreatestKeyLessThanOrEqual(m_currentTransaction.get(), cursorOptions.highKey, foundHighKey))
1443                 return 0;
1444
1445             // If the target key should not be included, but we end up with a smaller key, we should include that.
1446             if (cursorOptions.highOpen && compareIndexKeys(foundHighKey, cursorOptions.highKey) < 0)
1447                 cursorOptions.highOpen = false;
1448
1449             cursorOptions.highKey = foundHighKey;
1450         }
1451     }
1452
1453     RefPtr<ObjectStoreCursorImpl> cursor = ObjectStoreCursorImpl::create(m_currentTransaction.get(), cursorOptions);
1454     if (!cursor->firstSeek())
1455         return 0;
1456
1457     return cursor.release();
1458 }
1459
1460 PassRefPtr<IDBBackingStore::Cursor> IDBLevelDBBackingStore::openIndexKeyCursor(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IDBCursor::Direction direction)
1461 {
1462     ASSERT(m_currentTransaction);
1463     CursorOptions cursorOptions;
1464     bool lowerBound = range && range->lower();
1465     bool upperBound = range && range->upper();
1466     cursorOptions.forward = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::NEXT);
1467     cursorOptions.unique = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::PREV_NO_DUPLICATE);
1468
1469     if (!lowerBound) {
1470         cursorOptions.lowKey = IndexDataKey::encodeMinKey(databaseId, objectStoreId, indexId);
1471         cursorOptions.lowOpen = false; // Included.
1472     } else {
1473         cursorOptions.lowKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->lower());
1474         cursorOptions.lowOpen = range->lowerOpen();
1475     }
1476
1477     if (!upperBound) {
1478         cursorOptions.highKey = IndexDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
1479         cursorOptions.highOpen = false; // Included.
1480
1481         if (!cursorOptions.forward) { // We need a key that exists.
1482             if (!findGreatestKeyLessThanOrEqual(m_currentTransaction.get(), cursorOptions.highKey, cursorOptions.highKey))
1483                 return 0;
1484             cursorOptions.highOpen = false;
1485         }
1486     } else {
1487         cursorOptions.highKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->upper());
1488         cursorOptions.highOpen = range->upperOpen();
1489
1490         Vector<char> foundHighKey;
1491         if (!findGreatestKeyLessThanOrEqual(m_currentTransaction.get(), cursorOptions.highKey, foundHighKey)) // Seek to the *last* key in the set of non-unique keys.
1492             return 0;
1493
1494         // If the target key should not be included, but we end up with a smaller key, we should include that.
1495         if (cursorOptions.highOpen && compareIndexKeys(foundHighKey, cursorOptions.highKey) < 0)
1496             cursorOptions.highOpen = false;
1497
1498         cursorOptions.highKey = foundHighKey;
1499     }
1500
1501     RefPtr<IndexKeyCursorImpl> cursor = IndexKeyCursorImpl::create(m_currentTransaction.get(), cursorOptions);
1502     if (!cursor->firstSeek())
1503         return 0;
1504
1505     return cursor.release();
1506 }
1507
1508 PassRefPtr<IDBBackingStore::Cursor> IDBLevelDBBackingStore::openIndexCursor(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IDBCursor::Direction direction)
1509 {
1510     ASSERT(m_currentTransaction);
1511     CursorOptions cursorOptions;
1512     bool lowerBound = range && range->lower();
1513     bool upperBound = range && range->upper();
1514     cursorOptions.forward = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::NEXT);
1515     cursorOptions.unique = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::PREV_NO_DUPLICATE);
1516
1517     if (!lowerBound) {
1518         cursorOptions.lowKey = IndexDataKey::encodeMinKey(databaseId, objectStoreId, indexId);
1519         cursorOptions.lowOpen = false; // Included.
1520     } else {
1521         cursorOptions.lowKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->lower());
1522         cursorOptions.lowOpen = range->lowerOpen();
1523     }
1524
1525     if (!upperBound) {
1526         cursorOptions.highKey = IndexDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
1527         cursorOptions.highOpen = false; // Included.
1528
1529         if (!cursorOptions.forward) { // We need a key that exists.
1530             if (!findGreatestKeyLessThanOrEqual(m_currentTransaction.get(), cursorOptions.highKey, cursorOptions.highKey))
1531                 return 0;
1532             cursorOptions.highOpen = false;
1533         }
1534     } else {
1535         cursorOptions.highKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->upper());
1536         cursorOptions.highOpen = range->upperOpen();
1537
1538         Vector<char> foundHighKey;
1539         if (!findGreatestKeyLessThanOrEqual(m_currentTransaction.get(), cursorOptions.highKey, foundHighKey)) // Seek to the *last* key in the set of non-unique keys.
1540             return 0;
1541
1542         // If the target key should not be included, but we end up with a smaller key, we should include that.
1543         if (cursorOptions.highOpen && compareIndexKeys(foundHighKey, cursorOptions.highKey) < 0)
1544             cursorOptions.highOpen = false;
1545
1546         cursorOptions.highKey = foundHighKey;
1547     }
1548
1549     RefPtr<IndexCursorImpl> cursor = IndexCursorImpl::create(m_currentTransaction.get(), cursorOptions);
1550     if (!cursor->firstSeek())
1551         return 0;
1552
1553     return cursor.release();
1554 }
1555
1556 PassRefPtr<IDBBackingStore::Transaction> IDBLevelDBBackingStore::createTransaction()
1557 {
1558     return Transaction::create(this);
1559 }
1560
1561 PassRefPtr<IDBLevelDBBackingStore::Transaction> IDBLevelDBBackingStore::Transaction::create(IDBLevelDBBackingStore* backingStore)
1562 {
1563     return adoptRef(new Transaction(backingStore));
1564 }
1565
1566 IDBLevelDBBackingStore::Transaction::Transaction(IDBLevelDBBackingStore* backingStore)
1567     : m_backingStore(backingStore)
1568 {
1569 }
1570
1571 void IDBLevelDBBackingStore::Transaction::begin()
1572 {
1573     ASSERT(!m_backingStore->m_currentTransaction);
1574     m_backingStore->m_currentTransaction = LevelDBTransaction::create(m_backingStore->m_db.get());
1575 }
1576
1577 bool IDBLevelDBBackingStore::Transaction::commit()
1578 {
1579     ASSERT(m_backingStore->m_currentTransaction);
1580     bool result = m_backingStore->m_currentTransaction->commit();
1581     m_backingStore->m_currentTransaction.clear();
1582     return result;
1583 }
1584
1585 void IDBLevelDBBackingStore::Transaction::rollback()
1586 {
1587     ASSERT(m_backingStore->m_currentTransaction);
1588     m_backingStore->m_currentTransaction->rollback();
1589     m_backingStore->m_currentTransaction.clear();
1590 }
1591
1592 bool IDBLevelDBBackingStore::backingStoreExists(SecurityOrigin* securityOrigin, const String&, const String& pathBaseArg)
1593 {
1594     String pathBase = pathBaseArg;
1595
1596     if (pathBase.isEmpty())
1597         return false;
1598
1599     // FIXME: We should eventually use the same LevelDB database for all origins.
1600     String path = pathByAppendingComponent(pathBase, securityOrigin->databaseIdentifier() + ".indexeddb.leveldb");
1601
1602     // FIXME: this is checking for presence of the domain, not the database itself
1603     return fileExists(path+"/CURRENT");
1604 }
1605
1606 } // namespace WebCore
1607
1608 #endif // USE(LEVELDB)
1609 #endif // ENABLE(INDEXED_DATABASE)