8cff91ba9d1aced459233d93d034e69a5b219ab8
[WebKit-https.git] / Source / WebCore / storage / 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         callback.callback(ri.get(), idbValue);
663     }
664
665     return true;
666 }
667
668 void IDBLevelDBBackingStore::getIndexes(int64_t databaseId, int64_t objectStoreId, Vector<int64_t>& foundIds, Vector<String>& foundNames, Vector<String>& foundKeyPaths, Vector<bool>& foundUniqueFlags)
669 {
670     const Vector<char> startKey = IndexMetaDataKey::encode(databaseId, objectStoreId, 0, 0);
671     const Vector<char> stopKey = IndexMetaDataKey::encode(databaseId, objectStoreId + 1, 0, 0);
672
673     ASSERT(foundIds.isEmpty());
674     ASSERT(foundNames.isEmpty());
675     ASSERT(foundKeyPaths.isEmpty());
676     ASSERT(foundUniqueFlags.isEmpty());
677
678     OwnPtr<LevelDBIterator> it = m_db->createIterator();
679     for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
680         const char* p = it->key().begin();
681         const char* limit = it->key().end();
682
683         IndexMetaDataKey metaDataKey;
684         p = IndexMetaDataKey::decode(p, limit, &metaDataKey);
685         ASSERT(p);
686
687         int64_t indexId = metaDataKey.indexId();
688         ASSERT(!metaDataKey.metaDataType());
689
690         String indexName = decodeString(it->value().begin(), it->value().end());
691         it->next();
692         if (!it->isValid()) {
693             LOG_ERROR("Internal Indexed DB error.");
694             return;
695         }
696
697         bool indexUnique = *it->value().begin();
698         it->next();
699         if (!it->isValid()) {
700             LOG_ERROR("Internal Indexed DB error.");
701             return;
702         }
703
704         String keyPath = decodeString(it->value().begin(), it->value().end());
705
706         foundIds.append(indexId);
707         foundNames.append(indexName);
708         foundKeyPaths.append(keyPath);
709         foundUniqueFlags.append(indexUnique);
710     }
711 }
712
713 static int64_t getNewIndexId(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId)
714 {
715     int64_t maxIndexId = -1;
716     const Vector<char> maxIndexIdKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, 5);
717     if (!getInt(transaction, maxIndexIdKey, maxIndexId))
718         maxIndexId = kMinimumIndexId;
719
720     ASSERT(maxIndexId >= 0);
721
722     int64_t indexId = maxIndexId + 1;
723     if (!putInt(transaction, maxIndexIdKey, indexId))
724         return -1;
725
726     return indexId;
727 }
728
729 bool IDBLevelDBBackingStore::createIndex(int64_t databaseId, int64_t objectStoreId, const String& name, const String& keyPath, bool isUnique, int64_t& indexId)
730 {
731     ASSERT(m_currentTransaction);
732     indexId = getNewIndexId(m_currentTransaction.get(), databaseId, objectStoreId);
733     if (indexId < 0)
734         return false;
735
736     const Vector<char> nameKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, 0);
737     const Vector<char> uniqueKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, 1);
738     const Vector<char> keyPathKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, 2);
739
740     bool ok = putString(m_currentTransaction.get(), nameKey, name);
741     if (!ok) {
742         LOG_ERROR("Internal Indexed DB error.");
743         return false;
744     }
745
746     ok = putInt(m_currentTransaction.get(), uniqueKey, isUnique);
747     if (!ok) {
748         LOG_ERROR("Internal Indexed DB error.");
749         return false;
750     }
751
752     ok = putString(m_currentTransaction.get(), keyPathKey, keyPath);
753     if (!ok) {
754         LOG_ERROR("Internal Indexed DB error.");
755         return false;
756     }
757
758     return true;
759 }
760
761 void IDBLevelDBBackingStore::deleteIndex(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
762 {
763     ASSERT(m_currentTransaction);
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
769     if (!m_currentTransaction->remove(nameKey)) {
770         LOG_ERROR("Internal Indexed DB error.");
771         return;
772     }
773     if (!m_currentTransaction->remove(uniqueKey)) {
774         LOG_ERROR("Internal Indexed DB error.");
775         return;
776     }
777     if (!m_currentTransaction->remove(keyPathKey)) {
778         LOG_ERROR("Internal Indexed DB error.");
779         return;
780     }
781
782     const Vector<char> indexDataStart = IndexDataKey::encode(databaseId, objectStoreId, indexId, minIDBKey(), 0);
783     const Vector<char> indexDataEnd = IndexDataKey::encode(databaseId, objectStoreId, indexId, maxIDBKey(), 0);
784
785     if (!deleteRange(m_currentTransaction.get(), indexDataStart, indexDataEnd)) {
786         LOG_ERROR("Internal Indexed DB error.");
787         return;
788     }
789 }
790
791 bool IDBLevelDBBackingStore::putIndexDataForRecord(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, const ObjectStoreRecordIdentifier* recordIdentifier)
792 {
793     ASSERT(indexId >= kMinimumIndexId);
794     const LevelDBRecordIdentifier* levelDBRecordIdentifier = static_cast<const LevelDBRecordIdentifier*>(recordIdentifier);
795
796     ASSERT(m_currentTransaction);
797     const int64_t globalSequenceNumber = getNewVersionNumber(m_currentTransaction.get(), databaseId, objectStoreId);
798     const Vector<char> indexDataKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, key, globalSequenceNumber);
799
800     Vector<char> data;
801     data.append(encodeVarInt(levelDBRecordIdentifier->version()));
802     data.append(levelDBRecordIdentifier->primaryKey());
803
804     return m_currentTransaction->put(indexDataKey, data);
805 }
806
807 static bool findGreatestKeyLessThan(LevelDBTransaction* transaction, const Vector<char>& target, Vector<char>& foundKey)
808 {
809     OwnPtr<LevelDBIterator> it = transaction->createIterator();
810     it->seek(target);
811
812     if (!it->isValid()) {
813         it->seekToLast();
814         if (!it->isValid())
815             return false;
816     }
817
818     while (compareIndexKeys(it->key(), target) >= 0) {
819         it->prev();
820         if (!it->isValid())
821             return false;
822     }
823
824     foundKey.clear();
825     foundKey.append(it->key().begin(), it->key().end() - it->key().begin());
826     return true;
827 }
828
829 bool IDBLevelDBBackingStore::deleteIndexDataForRecord(int64_t, int64_t, int64_t, const ObjectStoreRecordIdentifier*)
830 {
831     // FIXME: This isn't needed since we invalidate index data via the version number mechanism.
832     return true;
833 }
834
835 String IDBLevelDBBackingStore::getObjectViaIndex(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key)
836 {
837     RefPtr<IDBKey> primaryKey = getPrimaryKeyViaIndex(databaseId, objectStoreId, indexId, key);
838     if (!primaryKey)
839         return String();
840
841     return getObjectStoreRecord(databaseId, objectStoreId, *primaryKey);
842 }
843
844 static bool versionExists(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t version, const Vector<char>& encodedPrimaryKey)
845 {
846     const Vector<char> key = ExistsEntryKey::encode(databaseId, objectStoreId, encodedPrimaryKey);
847     Vector<char> data;
848
849     if (!transaction->get(key, data))
850         return false;
851
852     return decodeInt(data.begin(), data.end()) == version;
853 }
854
855 static bool findKeyInIndex(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, Vector<char>& foundEncodedPrimaryKey)
856 {
857     ASSERT(foundEncodedPrimaryKey.isEmpty());
858
859     const Vector<char> leveldbKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, key, 0);
860     OwnPtr<LevelDBIterator> it = transaction->createIterator();
861     it->seek(leveldbKey);
862
863     for (;;) {
864         if (!it->isValid())
865             return false;
866         if (compareIndexKeys(it->key(), leveldbKey) > 0)
867             return false;
868
869         int64_t version;
870         const char* p = decodeVarInt(it->value().begin(), it->value().end(), version);
871         if (!p)
872             return false;
873         foundEncodedPrimaryKey.append(p, it->value().end() - p);
874
875         if (!versionExists(transaction, databaseId, objectStoreId, version, foundEncodedPrimaryKey)) {
876             // Delete stale index data entry and continue.
877             transaction->remove(it->key());
878             it->next();
879             continue;
880         }
881
882         return true;
883     }
884 }
885
886 PassRefPtr<IDBKey> IDBLevelDBBackingStore::getPrimaryKeyViaIndex(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key)
887 {
888     ASSERT(m_currentTransaction);
889
890     Vector<char> foundEncodedPrimaryKey;
891     if (findKeyInIndex(m_currentTransaction.get(), databaseId, objectStoreId, indexId, key, foundEncodedPrimaryKey)) {
892         RefPtr<IDBKey> primaryKey;
893         decodeIDBKey(foundEncodedPrimaryKey.begin(), foundEncodedPrimaryKey.end(), primaryKey);
894         return primaryKey.release();
895     }
896
897     return 0;
898 }
899
900 bool IDBLevelDBBackingStore::keyExistsInIndex(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& indexKey, RefPtr<IDBKey>& foundPrimaryKey)
901 {
902     ASSERT(m_currentTransaction);
903
904     Vector<char> foundEncodedPrimaryKey;
905     if (!findKeyInIndex(m_currentTransaction.get(), databaseId, objectStoreId, indexId, indexKey, foundEncodedPrimaryKey))
906         return false;
907
908     decodeIDBKey(foundEncodedPrimaryKey.begin(), foundEncodedPrimaryKey.end(), foundPrimaryKey);
909     return true;
910 }
911
912 namespace {
913
914 struct CursorOptions {
915     Vector<char> lowKey;
916     bool lowOpen;
917     Vector<char> highKey;
918     bool highOpen;
919     bool forward;
920     bool unique;
921 };
922
923 class CursorImplCommon : public IDBBackingStore::Cursor {
924 public:
925     // IDBBackingStore::Cursor
926     virtual bool continueFunction(const IDBKey*);
927     virtual PassRefPtr<IDBKey> key() { return m_currentKey; }
928     virtual PassRefPtr<IDBKey> primaryKey() { return m_currentKey; }
929     virtual String value() = 0;
930     virtual PassRefPtr<IDBBackingStore::ObjectStoreRecordIdentifier> objectStoreRecordIdentifier() = 0; // FIXME: I don't think this is actually used, so drop it.
931     virtual int64_t indexDataId() = 0;
932     virtual void close() { }
933
934     virtual bool loadCurrentRow() = 0;
935     bool firstSeek();
936
937 protected:
938     CursorImplCommon(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
939         : m_transaction(transaction)
940         , m_cursorOptions(cursorOptions)
941     {
942     }
943     virtual ~CursorImplCommon() {}
944
945     LevelDBTransaction* m_transaction;
946     CursorOptions m_cursorOptions;
947     OwnPtr<LevelDBIterator> m_iterator;
948     RefPtr<IDBKey> m_currentKey;
949 };
950
951 bool CursorImplCommon::firstSeek()
952 {
953     m_iterator = m_transaction->createIterator();
954
955     if (m_cursorOptions.forward)
956         m_iterator->seek(m_cursorOptions.lowKey);
957     else
958         m_iterator->seek(m_cursorOptions.highKey);
959
960     for (;;) {
961         if (!m_iterator->isValid())
962             return false;
963
964         if (m_cursorOptions.forward && m_cursorOptions.highOpen && compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) >= 0)
965             return false;
966         if (m_cursorOptions.forward && !m_cursorOptions.highOpen && compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) > 0)
967             return false;
968         if (!m_cursorOptions.forward && m_cursorOptions.lowOpen && compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) <= 0)
969             return false;
970         if (!m_cursorOptions.forward && !m_cursorOptions.lowOpen && compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) < 0)
971             return false;
972
973         if (m_cursorOptions.forward && m_cursorOptions.lowOpen) {
974             // lowKey not included in the range.
975             if (compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) <= 0) {
976                 m_iterator->next();
977                 continue;
978             }
979         }
980         if (!m_cursorOptions.forward && m_cursorOptions.highOpen) {
981             // highKey not included in the range.
982             if (compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) >= 0) {
983                 m_iterator->prev();
984                 continue;
985             }
986         }
987
988         if (!loadCurrentRow()) {
989             if (m_cursorOptions.forward)
990                 m_iterator->next();
991             else
992                 m_iterator->prev();
993             continue;
994         }
995
996         return true;
997     }
998 }
999
1000 bool CursorImplCommon::continueFunction(const IDBKey* key)
1001 {
1002     // FIXME: This shares a lot of code with firstSeek.
1003     RefPtr<IDBKey> previousKey = m_currentKey;
1004
1005     for (;;) {
1006         if (m_cursorOptions.forward)
1007             m_iterator->next();
1008         else
1009             m_iterator->prev();
1010
1011         if (!m_iterator->isValid())
1012             return false;
1013
1014         Vector<char> trash;
1015         if (!m_transaction->get(m_iterator->key(), trash))
1016              continue;
1017
1018         if (m_cursorOptions.forward && m_cursorOptions.highOpen && compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) >= 0) // high key not included in range
1019             return false;
1020         if (m_cursorOptions.forward && !m_cursorOptions.highOpen && compareIndexKeys(m_iterator->key(), m_cursorOptions.highKey) > 0)
1021             return false;
1022         if (!m_cursorOptions.forward && m_cursorOptions.lowOpen && compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) <= 0) // low key not included in range
1023             return false;
1024         if (!m_cursorOptions.forward && !m_cursorOptions.lowOpen && compareIndexKeys(m_iterator->key(), m_cursorOptions.lowKey) < 0)
1025             return false;
1026
1027         if (!loadCurrentRow())
1028             continue;
1029
1030         if (key) {
1031             if (m_cursorOptions.forward) {
1032                 if (m_currentKey->isLessThan(key))
1033                     continue;
1034             } else {
1035                 if (key->isLessThan(m_currentKey.get()))
1036                     continue;
1037             }
1038         }
1039
1040         if (m_cursorOptions.unique && m_currentKey->isEqual(previousKey.get()))
1041             continue;
1042
1043         break;
1044     }
1045
1046     return true;
1047 }
1048
1049 class ObjectStoreCursorImpl : public CursorImplCommon {
1050 public:
1051     static PassRefPtr<ObjectStoreCursorImpl> create(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1052     {
1053         return adoptRef(new ObjectStoreCursorImpl(transaction, cursorOptions));
1054     }
1055
1056     // CursorImplCommon
1057     virtual String value() { return m_currentValue; }
1058     virtual PassRefPtr<IDBBackingStore::ObjectStoreRecordIdentifier> objectStoreRecordIdentifier() { ASSERT_NOT_REACHED(); return 0; }
1059     virtual int64_t indexDataId() { ASSERT_NOT_REACHED(); return 0; }
1060     virtual bool loadCurrentRow();
1061
1062 private:
1063     ObjectStoreCursorImpl(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1064         : CursorImplCommon(transaction, cursorOptions)
1065     {
1066     }
1067
1068     String m_currentValue;
1069 };
1070
1071 bool ObjectStoreCursorImpl::loadCurrentRow()
1072 {
1073     const char* p = m_iterator->key().begin();
1074     const char* keyLimit = m_iterator->key().end();
1075
1076     ObjectStoreDataKey objectStoreDataKey;
1077     p = ObjectStoreDataKey::decode(p, keyLimit, &objectStoreDataKey);
1078     ASSERT(p);
1079     if (!p)
1080         return false;
1081
1082     m_currentKey = objectStoreDataKey.userKey();
1083
1084     int64_t version;
1085     const char* q = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), version);
1086     ASSERT(q);
1087     if (!q)
1088         return false;
1089     (void) version;
1090
1091     m_currentValue = decodeString(q, m_iterator->value().end());
1092
1093     return true;
1094 }
1095
1096 class IndexKeyCursorImpl : public CursorImplCommon {
1097 public:
1098     static PassRefPtr<IndexKeyCursorImpl> create(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1099     {
1100         return adoptRef(new IndexKeyCursorImpl(transaction, cursorOptions));
1101     }
1102
1103     // CursorImplCommon
1104     virtual String value() { ASSERT_NOT_REACHED(); return String(); }
1105     virtual PassRefPtr<IDBKey> primaryKey() { return m_primaryKey; }
1106     virtual PassRefPtr<IDBBackingStore::ObjectStoreRecordIdentifier> objectStoreRecordIdentifier() { ASSERT_NOT_REACHED(); return 0; }
1107     virtual int64_t indexDataId() { ASSERT_NOT_REACHED(); return 0; }
1108     virtual bool loadCurrentRow();
1109
1110 private:
1111     IndexKeyCursorImpl(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1112         : CursorImplCommon(transaction, cursorOptions)
1113     {
1114     }
1115
1116     RefPtr<IDBKey> m_primaryKey;
1117 };
1118
1119 bool IndexKeyCursorImpl::loadCurrentRow()
1120 {
1121     const char* p = m_iterator->key().begin();
1122     const char* keyLimit = m_iterator->key().end();
1123     IndexDataKey indexDataKey;
1124     p = IndexDataKey::decode(p, keyLimit, &indexDataKey);
1125
1126     m_currentKey = indexDataKey.userKey();
1127
1128     int64_t indexDataVersion;
1129     const char* q = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), indexDataVersion);
1130     ASSERT(q);
1131     if (!q)
1132         return false;
1133
1134     q = decodeIDBKey(q, m_iterator->value().end(), m_primaryKey);
1135     ASSERT(q);
1136     if (!q)
1137         return false;
1138
1139     Vector<char> primaryLevelDBKey = ObjectStoreDataKey::encode(indexDataKey.databaseId(), indexDataKey.objectStoreId(), *m_primaryKey);
1140
1141     Vector<char> result;
1142     if (!m_transaction->get(primaryLevelDBKey, result))
1143         return false;
1144
1145     int64_t objectStoreDataVersion;
1146     const char* t = decodeVarInt(result.begin(), result.end(), objectStoreDataVersion);
1147     ASSERT(t);
1148     if (!t)
1149         return false;
1150
1151     if (objectStoreDataVersion != indexDataVersion) {
1152         m_transaction->remove(m_iterator->key());
1153         return false;
1154     }
1155
1156     return true;
1157 }
1158
1159 class IndexCursorImpl : public CursorImplCommon {
1160 public:
1161     static PassRefPtr<IndexCursorImpl> create(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1162     {
1163         return adoptRef(new IndexCursorImpl(transaction, cursorOptions));
1164     }
1165
1166     // CursorImplCommon
1167     virtual String value() { return m_value; }
1168     virtual PassRefPtr<IDBKey> primaryKey() { return m_primaryKey; }
1169     virtual PassRefPtr<IDBBackingStore::ObjectStoreRecordIdentifier> objectStoreRecordIdentifier() { ASSERT_NOT_REACHED(); return 0; }
1170     virtual int64_t indexDataId() { ASSERT_NOT_REACHED(); return 0; }
1171     bool loadCurrentRow();
1172
1173 private:
1174     IndexCursorImpl(LevelDBTransaction* transaction, const CursorOptions& cursorOptions)
1175         : CursorImplCommon(transaction, cursorOptions)
1176     {
1177     }
1178
1179     RefPtr<IDBKey> m_primaryKey;
1180     String m_value;
1181     Vector<char> m_primaryLevelDBKey;
1182 };
1183
1184 bool IndexCursorImpl::loadCurrentRow()
1185 {
1186     const char *p = m_iterator->key().begin();
1187     const char *limit = m_iterator->key().end();
1188
1189     IndexDataKey indexDataKey;
1190     p = IndexDataKey::decode(p, limit, &indexDataKey);
1191
1192     m_currentKey = indexDataKey.userKey();
1193
1194     const char *q = m_iterator->value().begin();
1195     const char *valueLimit = m_iterator->value().end();
1196
1197     int64_t indexDataVersion;
1198     q = decodeVarInt(q, valueLimit, indexDataVersion);
1199     ASSERT(q);
1200     if (!q)
1201         return false;
1202     q = decodeIDBKey(q, valueLimit, m_primaryKey);
1203     ASSERT(q);
1204     if (!q)
1205         return false;
1206
1207     m_primaryLevelDBKey = ObjectStoreDataKey::encode(indexDataKey.databaseId(), indexDataKey.objectStoreId(), *m_primaryKey);
1208
1209     Vector<char> result;
1210     if (!m_transaction->get(m_primaryLevelDBKey, result))
1211         return false;
1212
1213     int64_t objectStoreDataVersion;
1214     const char* t = decodeVarInt(result.begin(), result.end(), objectStoreDataVersion);
1215     ASSERT(t);
1216     if (!t)
1217         return false;
1218
1219     if (objectStoreDataVersion != indexDataVersion) {
1220         m_transaction->remove(m_iterator->key());
1221         return false;
1222     }
1223
1224     m_value = decodeString(t, result.end());
1225     return true;
1226 }
1227
1228 }
1229
1230 static bool findLastIndexKeyEqualTo(LevelDBTransaction* transaction, const Vector<char>& target, Vector<char>& foundKey)
1231 {
1232     OwnPtr<LevelDBIterator> it = transaction->createIterator();
1233     it->seek(target);
1234
1235     if (!it->isValid())
1236         return false;
1237
1238     while (it->isValid() && !compareIndexKeys(it->key(), target)) {
1239         foundKey.clear();
1240         foundKey.append(it->key().begin(), it->key().end() - it->key().begin());
1241         it->next();
1242     }
1243
1244     return true;
1245 }
1246
1247 PassRefPtr<IDBBackingStore::Cursor> IDBLevelDBBackingStore::openObjectStoreCursor(int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IDBCursor::Direction direction)
1248 {
1249     ASSERT(m_currentTransaction);
1250     CursorOptions cursorOptions;
1251
1252     bool lowerBound = range && range->lower();
1253     bool upperBound = range && range->upper();
1254     cursorOptions.forward = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::NEXT);
1255     cursorOptions.unique = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::PREV_NO_DUPLICATE);
1256
1257     if (!lowerBound) {
1258         cursorOptions.lowKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, minIDBKey());
1259         cursorOptions.lowOpen = true; // Not included.
1260     } else {
1261         cursorOptions.lowKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, *range->lower());
1262         cursorOptions.lowOpen = range->lowerOpen();
1263     }
1264
1265     if (!upperBound) {
1266         cursorOptions.highKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, maxIDBKey());
1267         cursorOptions.highOpen = true; // Not included.
1268
1269         if (!cursorOptions.forward) { // We need a key that exists.
1270             if (!findGreatestKeyLessThan(m_currentTransaction.get(), cursorOptions.highKey, cursorOptions.highKey))
1271                 return 0;
1272             cursorOptions.highOpen = false;
1273         }
1274     } else {
1275         cursorOptions.highKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, *range->upper());
1276         cursorOptions.highOpen = range->upperOpen();
1277     }
1278
1279     RefPtr<ObjectStoreCursorImpl> cursor = ObjectStoreCursorImpl::create(m_currentTransaction.get(), cursorOptions);
1280     if (!cursor->firstSeek())
1281         return 0;
1282
1283     return cursor.release();
1284 }
1285
1286 PassRefPtr<IDBBackingStore::Cursor> IDBLevelDBBackingStore::openIndexKeyCursor(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IDBCursor::Direction direction)
1287 {
1288     ASSERT(m_currentTransaction);
1289     CursorOptions cursorOptions;
1290     bool lowerBound = range && range->lower();
1291     bool upperBound = range && range->upper();
1292     cursorOptions.forward = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::NEXT);
1293     cursorOptions.unique = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::PREV_NO_DUPLICATE);
1294
1295     if (!lowerBound) {
1296         cursorOptions.lowKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, minIDBKey(), 0);
1297         cursorOptions.lowOpen = false; // Included.
1298     } else {
1299         cursorOptions.lowKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->lower(), 0);
1300         cursorOptions.lowOpen = range->lowerOpen();
1301     }
1302
1303     if (!upperBound) {
1304         cursorOptions.highKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, maxIDBKey(), 0);
1305         cursorOptions.highOpen = false; // Included.
1306
1307         if (!cursorOptions.forward) { // We need a key that exists.
1308             if (!findGreatestKeyLessThan(m_currentTransaction.get(), cursorOptions.highKey, cursorOptions.highKey))
1309                 return 0;
1310             cursorOptions.highOpen = false;
1311         }
1312     } else {
1313         cursorOptions.highKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->upper(), 0);
1314         if (!findLastIndexKeyEqualTo(m_currentTransaction.get(), cursorOptions.highKey, cursorOptions.highKey)) // Seek to the *last* key in the set of non-unique keys.
1315             return 0;
1316         cursorOptions.highOpen = range->upperOpen();
1317     }
1318
1319     RefPtr<IndexKeyCursorImpl> cursor = IndexKeyCursorImpl::create(m_currentTransaction.get(), cursorOptions);
1320     if (!cursor->firstSeek())
1321         return 0;
1322
1323     return cursor.release();
1324 }
1325
1326 PassRefPtr<IDBBackingStore::Cursor> IDBLevelDBBackingStore::openIndexCursor(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IDBCursor::Direction direction)
1327 {
1328     ASSERT(m_currentTransaction);
1329     CursorOptions cursorOptions;
1330     bool lowerBound = range && range->lower();
1331     bool upperBound = range && range->upper();
1332     cursorOptions.forward = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::NEXT);
1333     cursorOptions.unique = (direction == IDBCursor::NEXT_NO_DUPLICATE || direction == IDBCursor::PREV_NO_DUPLICATE);
1334
1335     if (!lowerBound) {
1336         cursorOptions.lowKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, minIDBKey(), 0);
1337         cursorOptions.lowOpen = false; // Included.
1338     } else {
1339         cursorOptions.lowKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->lower(), 0);
1340         cursorOptions.lowOpen = range->lowerOpen();
1341     }
1342
1343     if (!upperBound) {
1344         cursorOptions.highKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, maxIDBKey(), 0);
1345         cursorOptions.highOpen = false; // Included.
1346
1347         if (!cursorOptions.forward) { // We need a key that exists.
1348             if (!findGreatestKeyLessThan(m_currentTransaction.get(), cursorOptions.highKey, cursorOptions.highKey))
1349                 return 0;
1350             cursorOptions.highOpen = false;
1351         }
1352     } else {
1353         cursorOptions.highKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->upper(), 0);
1354         if (!findLastIndexKeyEqualTo(m_currentTransaction.get(), cursorOptions.highKey, cursorOptions.highKey)) // Seek to the *last* key in the set of non-unique keys.
1355             return 0;
1356         cursorOptions.highOpen = range->upperOpen();
1357     }
1358
1359     RefPtr<IndexCursorImpl> cursor = IndexCursorImpl::create(m_currentTransaction.get(), cursorOptions);
1360     if (!cursor->firstSeek())
1361         return 0;
1362
1363     return cursor.release();
1364 }
1365
1366 PassRefPtr<IDBBackingStore::Transaction> IDBLevelDBBackingStore::createTransaction()
1367 {
1368     return Transaction::create(this);
1369 }
1370
1371 PassRefPtr<IDBLevelDBBackingStore::Transaction> IDBLevelDBBackingStore::Transaction::create(IDBLevelDBBackingStore* backingStore)
1372 {
1373     return adoptRef(new Transaction(backingStore));
1374 }
1375
1376 IDBLevelDBBackingStore::Transaction::Transaction(IDBLevelDBBackingStore* backingStore)
1377     : m_backingStore(backingStore)
1378 {
1379 }
1380
1381 void IDBLevelDBBackingStore::Transaction::begin()
1382 {
1383     ASSERT(!m_backingStore->m_currentTransaction);
1384     m_backingStore->m_currentTransaction = LevelDBTransaction::create(m_backingStore->m_db.get());
1385 }
1386
1387 void IDBLevelDBBackingStore::Transaction::commit()
1388 {
1389     ASSERT(m_backingStore->m_currentTransaction);
1390     m_backingStore->m_currentTransaction->commit();
1391     m_backingStore->m_currentTransaction.clear();
1392 }
1393
1394 void IDBLevelDBBackingStore::Transaction::rollback()
1395 {
1396     ASSERT(m_backingStore->m_currentTransaction);
1397     m_backingStore->m_currentTransaction->rollback();
1398     m_backingStore->m_currentTransaction.clear();
1399 }
1400
1401 bool IDBLevelDBBackingStore::backingStoreExists(SecurityOrigin* securityOrigin, const String&, const String& pathBaseArg)
1402 {
1403     String pathBase = pathBaseArg;
1404
1405     if (pathBase.isEmpty())
1406         return false;
1407
1408     // FIXME: We should eventually use the same LevelDB database for all origins.
1409     String path = pathByAppendingComponent(pathBase, securityOrigin->databaseIdentifier() + ".indexeddb.leveldb");
1410
1411     // FIXME: this is checking for presence of the domain, not the database itself
1412     return fileExists(path+"/CURRENT");
1413 }
1414
1415 } // namespace WebCore
1416
1417 #endif // USE(LEVELDB)
1418 #endif // ENABLE(INDEXED_DATABASE)