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