Source/WebCore/Modules/indexeddb/IDBLevelDBBackingStore.cpp

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