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