Source/WebCore/Modules/indexeddb/leveldb/IDBBackingStoreLevelDB.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 "IDBBackingStoreLevelDB.h"
  28
  29 #if ENABLE(INDEXED_DATABASE) && USE(LEVELDB)
  30
  31 #include "FileSystem.h"
  32 #include "HistogramSupport.h"
  33 #include "IDBBackingStoreCursorLevelDB.h"
  34 #include "IDBBackingStoreTransactionLevelDB.h"
  35 #include "IDBIndexWriter.h"
  36 #include "IDBKey.h"
  37 #include "IDBKeyPath.h"
  38 #include "IDBKeyRange.h"
  39 #include "IDBLevelDBCoding.h"
  40 #include "IDBMetadata.h"
  41 #include "IDBTransactionBackendInterface.h"
  42 #include "LevelDBComparator.h"
  43 #include "LevelDBDatabase.h"
  44 #include "LevelDBIterator.h"
  45 #include "LevelDBSlice.h"
  46 #include "LevelDBTransaction.h"
  47 #include "Logging.h"
  48 #include "SecurityOrigin.h"
  49 #include "SharedBuffer.h"
  50 #include <wtf/Assertions.h>
  51
  52 namespace WebCore {
  53
  54 using namespace IDBLevelDBCoding;
  55
  56 const int64_t KeyGeneratorInitialNumber = 1; // From the IndexedDB specification.
  57
  58 enum IDBBackingStoreLevelDBErrorSource {
  59     // 0 - 2 are no longer used.
  60     FindKeyInIndex = 3,
  61     GetIDBDatabaseMetaData,
  62     GetIndexes,
  63     GetKeyGeneratorCurrentNumber,
  64     GetObjectStores,
  65     GetRecord,
  66     KeyExistsInObjectStore,
  67     LoadCurrentRow,
  68     SetupMetadata,
  69     GetPrimaryKeyViaIndex,
  70     KeyExistsInIndex,
  71     VersionExists,
  72     DeleteObjectStore,
  73     SetMaxObjectStoreId,
  74     SetMaxIndexId,
  75     GetNewDatabaseId,
  76     GetNewVersionNumber,
  77     CreateIDBDatabaseMetaData,
  78     DeleteDatabase,
  79     IDBLevelDBBackingStoreInternalErrorMax,
  80 };
  81
  82 static void recordInternalError(const char* type, IDBBackingStoreLevelDBErrorSource location)
  83 {
  84     String name = String::format("WebCore.IndexedDB.BackingStore.%sError", type);
  85     HistogramSupport::histogramEnumeration(name.utf8().data(), location, IDBLevelDBBackingStoreInternalErrorMax);
  86 }
  87
  88 // Use to signal conditions that usually indicate developer error, but could be caused by data corruption.
  89 // A macro is used instead of an inline function so that the assert and log report the line number.
  90 #define REPORT_ERROR(type, location) \
  91     do { \
  92         LOG_ERROR("IndexedDB %s Error: %s", type, #location); \
  93         ASSERT_NOT_REACHED(); \
  94         recordInternalError(type, location); \
  95     } while (0)
  96
  97 #define INTERNAL_READ_ERROR(location) REPORT_ERROR("Read", location)
  98 #define INTERNAL_CONSISTENCY_ERROR(location) REPORT_ERROR("Consistency", location)
  99 #define INTERNAL_WRITE_ERROR(location) REPORT_ERROR("Write", location)
 100
 101 static void putBool(LevelDBTransaction* transaction, const LevelDBSlice& key, bool value)
 102 {
 103     transaction->put(key, encodeBool(value));
 104 }
 105
 106 template <typename DBOrTransaction>
 107 static bool getInt(DBOrTransaction* db, const LevelDBSlice& key, int64_t& foundInt, bool& found)
 108 {
 109     Vector<char> result;
 110     bool ok = db->safeGet(key, result, found);
 111     if (!ok)
 112         return false;
 113     if (!found)
 114         return true;
 115
 116     foundInt = decodeInt(result.begin(), result.end());
 117     return true;
 118 }
 119
 120 static void putInt(LevelDBTransaction* transaction, const LevelDBSlice& key, int64_t value)
 121 {
 122     ASSERT(value >= 0);
 123     transaction->put(key, encodeInt(value));
 124 }
 125
 126 template <typename DBOrTransaction>
 127 WARN_UNUSED_RETURN static bool getVarInt(DBOrTransaction* db, const LevelDBSlice& key, int64_t& foundInt, bool& found)
 128 {
 129     Vector<char> result;
 130     bool ok = db->safeGet(key, result, found);
 131     if (!ok)
 132         return false;
 133     if (!found)
 134         return true;
 135
 136     found = decodeVarInt(result.begin(), result.end(), foundInt) == result.end();
 137     return true;
 138 }
 139
 140 static void putVarInt(LevelDBTransaction* transaction, const LevelDBSlice& key, int64_t value)
 141 {
 142     transaction->put(key, encodeVarInt(value));
 143 }
 144
 145 template <typename DBOrTransaction>
 146 WARN_UNUSED_RETURN static bool getString(DBOrTransaction* db, const LevelDBSlice& key, String& foundString, bool& found)
 147 {
 148     Vector<char> result;
 149     found = false;
 150     bool ok = db->safeGet(key, result, found);
 151     if (!ok)
 152         return false;
 153     if (!found)
 154         return true;
 155
 156     foundString = decodeString(result.begin(), result.end());
 157     return true;
 158 }
 159
 160 static void putString(LevelDBTransaction* transaction, const LevelDBSlice& key, const String& value)
 161 {
 162     transaction->put(key, encodeString(value));
 163 }
 164
 165 static void putIDBKeyPath(LevelDBTransaction* transaction, const LevelDBSlice& key, const IDBKeyPath& value)
 166 {
 167     transaction->put(key, encodeIDBKeyPath(value));
 168 }
 169
 170 static int compareKeys(const LevelDBSlice& a, const LevelDBSlice& b)
 171 {
 172     return compare(a, b);
 173 }
 174
 175 int IDBBackingStoreLevelDB::compareIndexKeys(const LevelDBSlice& a, const LevelDBSlice& b)
 176 {
 177     return compare(a, b, true);
 178 }
 179
 180 class Comparator : public LevelDBComparator {
 181 public:
 182     virtual int compare(const LevelDBSlice& a, const LevelDBSlice& b) const { return IDBLevelDBCoding::compare(a, b); }
 183     virtual const char* name() const { return "idb_cmp1"; }
 184 };
 185
 186 // 0 - Initial version.
 187 // 1 - Adds UserIntVersion to DatabaseMetaData.
 188 // 2 - Adds DataVersion to to global metadata.
 189 const int64_t latestKnownSchemaVersion = 2;
 190 WARN_UNUSED_RETURN static bool isSchemaKnown(LevelDBDatabase* db, bool& known)
 191 {
 192     int64_t dbSchemaVersion = 0;
 193     bool found = false;
 194     bool ok = getInt(db, SchemaVersionKey::encode(), dbSchemaVersion, found);
 195     if (!ok)
 196         return false;
 197     if (!found) {
 198         known = true;
 199         return true;
 200     }
 201     if (dbSchemaVersion > latestKnownSchemaVersion) {
 202         known = false;
 203         return true;
 204     }
 205
 206     const uint32_t latestKnownDataVersion = SerializedScriptValue::wireFormatVersion();
 207     int64_t dbDataVersion = 0;
 208     ok = getInt(db, DataVersionKey::encode(), dbDataVersion, found);
 209     if (!ok)
 210         return false;
 211     if (!found) {
 212         known = true;
 213         return true;
 214     }
 215
 216     if (dbDataVersion > latestKnownDataVersion) {
 217         known = false;
 218         return true;
 219     }
 220
 221     known = true;
 222     return true;
 223 }
 224
 225 WARN_UNUSED_RETURN static bool setUpMetadata(LevelDBDatabase* db, const String& origin)
 226 {
 227     const uint32_t latestKnownDataVersion = SerializedScriptValue::wireFormatVersion();
 228     const Vector<char> schemaVersionKey = SchemaVersionKey::encode();
 229     const Vector<char> dataVersionKey = DataVersionKey::encode();
 230
 231     RefPtr<LevelDBTransaction> transaction = LevelDBTransaction::create(db);
 232
 233     int64_t dbSchemaVersion = 0;
 234     int64_t dbDataVersion = 0;
 235     bool found = false;
 236     bool ok = getInt(transaction.get(), schemaVersionKey, dbSchemaVersion, found);
 237     if (!ok) {
 238         INTERNAL_READ_ERROR(SetupMetadata);
 239         return false;
 240     }
 241     if (!found) {
 242         // Initialize new backing store.
 243         dbSchemaVersion = latestKnownSchemaVersion;
 244         putInt(transaction.get(), schemaVersionKey, dbSchemaVersion);
 245         dbDataVersion = latestKnownDataVersion;
 246         putInt(transaction.get(), dataVersionKey, dbDataVersion);
 247     } else {
 248         // Upgrade old backing store.
 249         ASSERT(dbSchemaVersion <= latestKnownSchemaVersion);
 250         if (dbSchemaVersion < 1) {
 251             dbSchemaVersion = 1;
 252             putInt(transaction.get(), schemaVersionKey, dbSchemaVersion);
 253             const Vector<char> startKey = DatabaseNameKey::encodeMinKeyForOrigin(origin);
 254             const Vector<char> stopKey = DatabaseNameKey::encodeStopKeyForOrigin(origin);
 255             OwnPtr<LevelDBIterator> it = db->createIterator();
 256             for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
 257                 int64_t databaseId = 0;
 258                 found = false;
 259                 bool ok = getInt(transaction.get(), it->key(), databaseId, found);
 260                 if (!ok) {
 261                     INTERNAL_READ_ERROR(SetupMetadata);
 262                     return false;
 263                 }
 264                 if (!found) {
 265                     INTERNAL_CONSISTENCY_ERROR(SetupMetadata);
 266                     return false;
 267                 }
 268                 Vector<char> intVersionKey = DatabaseMetaDataKey::encode(databaseId, DatabaseMetaDataKey::UserIntVersion);
 269                 putVarInt(transaction.get(), intVersionKey, IDBDatabaseMetadata::DefaultIntVersion);
 270             }
 271         }
 272         if (dbSchemaVersion < 2) {
 273             dbSchemaVersion = 2;
 274             putInt(transaction.get(), schemaVersionKey, dbSchemaVersion);
 275             dbDataVersion = SerializedScriptValue::wireFormatVersion();
 276             putInt(transaction.get(), dataVersionKey, dbDataVersion);
 277         }
 278     }
 279
 280     // All new values will be written using this serialization version.
 281     found = false;
 282     ok = getInt(transaction.get(), dataVersionKey, dbDataVersion, found);
 283     if (!ok) {
 284         INTERNAL_READ_ERROR(SetupMetadata);
 285         return false;
 286     }
 287     if (!found) {
 288         INTERNAL_CONSISTENCY_ERROR(SetupMetadata);
 289         return false;
 290     }
 291     if (dbDataVersion < latestKnownDataVersion) {
 292         dbDataVersion = latestKnownDataVersion;
 293         putInt(transaction.get(), dataVersionKey, dbDataVersion);
 294     }
 295
 296     ASSERT(dbSchemaVersion == latestKnownSchemaVersion);
 297     ASSERT(dbDataVersion == latestKnownDataVersion);
 298
 299     if (!transaction->commit()) {
 300         INTERNAL_WRITE_ERROR(SetupMetadata);
 301         return false;
 302     }
 303     return true;
 304 }
 305
 306 template <typename DBOrTransaction>
 307 WARN_UNUSED_RETURN static bool getMaxObjectStoreId(DBOrTransaction* db, int64_t databaseId, int64_t& maxObjectStoreId)
 308 {
 309     const Vector<char> maxObjectStoreIdKey = DatabaseMetaDataKey::encode(databaseId, DatabaseMetaDataKey::MaxObjectStoreId);
 310     bool ok = getMaxObjectStoreId(db, maxObjectStoreIdKey, maxObjectStoreId);
 311     return ok;
 312 }
 313
 314 template <typename DBOrTransaction>
 315 WARN_UNUSED_RETURN static bool getMaxObjectStoreId(DBOrTransaction* db, const Vector<char>& maxObjectStoreIdKey, int64_t& maxObjectStoreId)
 316 {
 317     maxObjectStoreId = -1;
 318     bool found = false;
 319     bool ok = getInt(db, maxObjectStoreIdKey, maxObjectStoreId, found);
 320     if (!ok)
 321         return false;
 322     if (!found)
 323         maxObjectStoreId = 0;
 324
 325     ASSERT(maxObjectStoreId >= 0);
 326     return true;
 327 }
 328
 329 class DefaultLevelDBFactory : public LevelDBFactory {
 330 public:
 331     virtual PassOwnPtr<LevelDBDatabase> openLevelDB(const String& fileName, const LevelDBComparator* comparator)
 332     {
 333         return LevelDBDatabase::open(fileName, comparator);
 334     }
 335     virtual bool destroyLevelDB(const String& fileName)
 336     {
 337         return LevelDBDatabase::destroy(fileName);
 338     }
 339 };
 340
 341 IDBBackingStoreLevelDB::IDBBackingStoreLevelDB(const String& identifier, PassOwnPtr<LevelDBDatabase> db, PassOwnPtr<LevelDBComparator> comparator)
 342     : m_identifier(identifier)
 343     , m_db(db)
 344     , m_comparator(comparator)
 345     , m_weakFactory(this)
 346 {
 347 }
 348
 349 IDBBackingStoreLevelDB::~IDBBackingStoreLevelDB()
 350 {
 351     // m_db's destructor uses m_comparator. The order of destruction is important.
 352     m_db.clear();
 353     m_comparator.clear();
 354 }
 355
 356 enum IDBLevelDBBackingStoreOpenResult {
 357     IDBLevelDBBackingStoreOpenMemorySuccess,
 358     IDBLevelDBBackingStoreOpenSuccess,
 359     IDBLevelDBBackingStoreOpenFailedDirectory,
 360     IDBLevelDBBackingStoreOpenFailedUnknownSchema,
 361     IDBLevelDBBackingStoreOpenCleanupDestroyFailed,
 362     IDBLevelDBBackingStoreOpenCleanupReopenFailed,
 363     IDBLevelDBBackingStoreOpenCleanupReopenSuccess,
 364     IDBLevelDBBackingStoreOpenFailedIOErrCheckingSchema,
 365     IDBLevelDBBackingStoreOpenFailedUnknownErr,
 366     IDBLevelDBBackingStoreOpenMemoryFailed,
 367     IDBLevelDBBackingStoreOpenAttemptNonASCII,
 368     IDBLevelDBBackingStoreOpenMax,
 369 };
 370
 371 PassRefPtr<IDBBackingStoreLevelDB> IDBBackingStoreLevelDB::open(const SecurityOrigin& securityOrigin, const String& pathBaseArg, const String& fileIdentifier)
 372 {
 373     DefaultLevelDBFactory levelDBFactory;
 374     return IDBBackingStoreLevelDB::open(securityOrigin, pathBaseArg, fileIdentifier, &levelDBFactory);
 375 }
 376
 377 PassRefPtr<IDBBackingStoreLevelDB> IDBBackingStoreLevelDB::open(const SecurityOrigin& securityOrigin, const String& pathBaseArg, const String& fileIdentifier, LevelDBFactory* levelDBFactory)
 378 {
 379     LOG(StorageAPI, "IDBBackingStoreLevelDB::open");
 380     ASSERT(!pathBaseArg.isEmpty());
 381     String pathBase = pathBaseArg;
 382
 383     OwnPtr<LevelDBComparator> comparator = adoptPtr(new Comparator());
 384     OwnPtr<LevelDBDatabase> db;
 385
 386     if (!pathBase.containsOnlyASCII())
 387             HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenAttemptNonASCII, IDBLevelDBBackingStoreOpenMax);
 388     if (!makeAllDirectories(pathBase)) {
 389         LOG_ERROR("Unable to create IndexedDB database path %s", pathBase.utf8().data());
 390         HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenFailedDirectory, IDBLevelDBBackingStoreOpenMax);
 391         return PassRefPtr<IDBBackingStoreLevelDB>();
 392     }
 393
 394     String path = pathByAppendingComponent(pathBase, securityOrigin.databaseIdentifier() + ".indexeddb.leveldb");
 395
 396     db = levelDBFactory->openLevelDB(path, comparator.get());
 397     if (db) {
 398         bool known = false;
 399         bool ok = isSchemaKnown(db.get(), known);
 400         if (!ok) {
 401             LOG_ERROR("IndexedDB had IO error checking schema, treating it as failure to open");
 402             HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenFailedIOErrCheckingSchema, IDBLevelDBBackingStoreOpenMax);
 403             db.clear();
 404         } else if (!known) {
 405             LOG_ERROR("IndexedDB backing store had unknown schema, treating it as failure to open");
 406             HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenFailedUnknownSchema, IDBLevelDBBackingStoreOpenMax);
 407             db.clear();
 408         }
 409     }
 410
 411     if (db)
 412         HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenSuccess, IDBLevelDBBackingStoreOpenMax);
 413     else {
 414         LOG_ERROR("IndexedDB backing store open failed, attempting cleanup");
 415         bool success = levelDBFactory->destroyLevelDB(path);
 416         if (!success) {
 417             LOG_ERROR("IndexedDB backing store cleanup failed");
 418             HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenCleanupDestroyFailed, IDBLevelDBBackingStoreOpenMax);
 419             return PassRefPtr<IDBBackingStoreLevelDB>();
 420         }
 421
 422         LOG_ERROR("IndexedDB backing store cleanup succeeded, reopening");
 423         db = levelDBFactory->openLevelDB(path, comparator.get());
 424         if (!db) {
 425             LOG_ERROR("IndexedDB backing store reopen after recovery failed");
 426             HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenCleanupReopenFailed, IDBLevelDBBackingStoreOpenMax);
 427             return PassRefPtr<IDBBackingStoreLevelDB>();
 428         }
 429         HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenCleanupReopenSuccess, IDBLevelDBBackingStoreOpenMax);
 430     }
 431
 432     if (!db) {
 433         ASSERT_NOT_REACHED();
 434         HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenFailedUnknownErr, IDBLevelDBBackingStoreOpenMax);
 435         return PassRefPtr<IDBBackingStoreLevelDB>();
 436     }
 437
 438     return create(fileIdentifier, db.release(), comparator.release());
 439 }
 440
 441 PassRefPtr<IDBBackingStoreLevelDB> IDBBackingStoreLevelDB::openInMemory(const String& identifier)
 442 {
 443     DefaultLevelDBFactory levelDBFactory;
 444     return IDBBackingStoreLevelDB::openInMemory(identifier, &levelDBFactory);
 445 }
 446
 447 PassRefPtr<IDBBackingStoreLevelDB> IDBBackingStoreLevelDB::openInMemory(const String& identifier, LevelDBFactory*)
 448 {
 449     LOG(StorageAPI, "IDBBackingStoreLevelDB::openInMemory");
 450
 451     OwnPtr<LevelDBComparator> comparator = adoptPtr(new Comparator());
 452     OwnPtr<LevelDBDatabase> db = LevelDBDatabase::openInMemory(comparator.get());
 453     if (!db) {
 454         LOG_ERROR("LevelDBDatabase::openInMemory failed.");
 455         HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenMemoryFailed, IDBLevelDBBackingStoreOpenMax);
 456         return PassRefPtr<IDBBackingStoreLevelDB>();
 457     }
 458     HistogramSupport::histogramEnumeration("WebCore.IndexedDB.BackingStore.OpenStatus", IDBLevelDBBackingStoreOpenMemorySuccess, IDBLevelDBBackingStoreOpenMax);
 459
 460     return create(identifier, db.release(), comparator.release());
 461 }
 462
 463 PassRefPtr<IDBBackingStoreLevelDB> IDBBackingStoreLevelDB::create(const String& identifier, PassOwnPtr<LevelDBDatabase> db, PassOwnPtr<LevelDBComparator> comparator)
 464 {
 465     // FIXME: Handle comparator name changes.
 466     RefPtr<IDBBackingStoreLevelDB> backingStore(adoptRef(new IDBBackingStoreLevelDB(identifier, db, comparator)));
 467
 468     if (!setUpMetadata(backingStore->m_db.get(), identifier))
 469         return PassRefPtr<IDBBackingStoreLevelDB>();
 470
 471     return backingStore.release();
 472 }
 473
 474 Vector<String> IDBBackingStoreLevelDB::getDatabaseNames()
 475 {
 476     Vector<String> foundNames;
 477     const Vector<char> startKey = DatabaseNameKey::encodeMinKeyForOrigin(m_identifier);
 478     const Vector<char> stopKey = DatabaseNameKey::encodeStopKeyForOrigin(m_identifier);
 479
 480     ASSERT(foundNames.isEmpty());
 481
 482     OwnPtr<LevelDBIterator> it = m_db->createIterator();
 483     for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
 484         const char* p = it->key().begin();
 485         const char* limit = it->key().end();
 486
 487         DatabaseNameKey databaseNameKey;
 488         p = DatabaseNameKey::decode(p, limit, &databaseNameKey);
 489         ASSERT(p);
 490
 491         foundNames.append(databaseNameKey.databaseName());
 492     }
 493     return foundNames;
 494 }
 495
 496 bool IDBBackingStoreLevelDB::getIDBDatabaseMetaData(const String& name, IDBDatabaseMetadata* metadata, bool& found)
 497 {
 498     const Vector<char> key = DatabaseNameKey::encode(m_identifier, name);
 499     found = false;
 500
 501     bool ok = getInt(m_db.get(), key, metadata->id, found);
 502     if (!ok) {
 503         INTERNAL_READ_ERROR(GetIDBDatabaseMetaData);
 504         return false;
 505     }
 506     if (!found)
 507         return true;
 508
 509     // FIXME: The string version is no longer supported, so the levelDB ports should consider refactoring off of it.
 510     String stringVersion;
 511     ok = getString(m_db.get(), DatabaseMetaDataKey::encode(metadata->id, DatabaseMetaDataKey::UserVersion), stringVersion, found);
 512     if (!ok) {
 513         INTERNAL_READ_ERROR(GetIDBDatabaseMetaData);
 514         return false;
 515     }
 516     if (!found) {
 517         INTERNAL_CONSISTENCY_ERROR(GetIDBDatabaseMetaData);
 518         return false;
 519     }
 520
 521     int64_t version;
 522     ok = getVarInt(m_db.get(), DatabaseMetaDataKey::encode(metadata->id, DatabaseMetaDataKey::UserIntVersion), version, found);
 523     if (!ok) {
 524         INTERNAL_READ_ERROR(GetIDBDatabaseMetaData);
 525         return false;
 526     }
 527     if (!found) {
 528         INTERNAL_CONSISTENCY_ERROR(GetIDBDatabaseMetaData);
 529         return false;
 530     }
 531
 532     // FIXME: The versioning semantics have changed since this original code was written, and what was once a negative number
 533     // stored in the database is no longer a valid version.
 534     if (version < 0)
 535         version = 0;
 536     metadata->version = version;
 537
 538     ok = getMaxObjectStoreId(m_db.get(), metadata->id, metadata->maxObjectStoreId);
 539     if (!ok) {
 540         INTERNAL_READ_ERROR(GetIDBDatabaseMetaData);
 541         return false;
 542     }
 543
 544     return true;
 545 }
 546
 547 void IDBBackingStoreLevelDB::getOrEstablishIDBDatabaseMetadata(const String& name, GetIDBDatabaseMetadataFunction metadataFunction)
 548 {
 549     const Vector<char> key = DatabaseNameKey::encode(m_identifier, name);
 550     bool found = false;
 551
 552     IDBDatabaseMetadata resultMetadata;
 553
 554     bool ok = getInt(m_db.get(), key, resultMetadata.id, found);
 555     if (!ok) {
 556         INTERNAL_READ_ERROR(GetIDBDatabaseMetaData);
 557         metadataFunction(resultMetadata, false);
 558         return;
 559     }
 560
 561     if (!found) {
 562         resultMetadata.name = name;
 563         resultMetadata.version = IDBDatabaseMetadata::DefaultIntVersion;
 564
 565         metadataFunction(resultMetadata, createIDBDatabaseMetaData(resultMetadata));
 566         return;
 567     }
 568
 569     int64_t version;
 570     ok = getVarInt(m_db.get(), DatabaseMetaDataKey::encode(resultMetadata.id, DatabaseMetaDataKey::UserIntVersion), version, found);
 571     if (!ok) {
 572         INTERNAL_READ_ERROR(GetIDBDatabaseMetaData);
 573         metadataFunction(resultMetadata, false);
 574         return;
 575     }
 576     if (!found) {
 577         INTERNAL_CONSISTENCY_ERROR(GetIDBDatabaseMetaData);
 578         metadataFunction(resultMetadata, false);
 579         return;
 580     }
 581
 582     // FIXME: The versioning semantics have changed since this original code was written, and what was once a negative number
 583     // stored in the database is no longer a valid version.
 584     if (version < 0)
 585         version = 0;
 586     resultMetadata.version = version;
 587
 588     ok = getMaxObjectStoreId(m_db.get(), resultMetadata.id, resultMetadata.maxObjectStoreId);
 589     if (!ok) {
 590         INTERNAL_READ_ERROR(GetIDBDatabaseMetaData);
 591         metadataFunction(resultMetadata, false);
 592         return;
 593     }
 594
 595     ok = getObjectStores(resultMetadata.id, &resultMetadata.objectStores);
 596     if (!ok) {
 597         INTERNAL_READ_ERROR(GetIDBDatabaseMetaData);
 598         metadataFunction(resultMetadata, false);
 599         return;
 600     }
 601
 602     metadataFunction(resultMetadata, true);
 603 }
 604
 605 WARN_UNUSED_RETURN static bool getNewDatabaseId(LevelDBDatabase* db, int64_t& newId)
 606 {
 607     RefPtr<LevelDBTransaction> transaction = LevelDBTransaction::create(db);
 608
 609     newId = -1;
 610     int64_t maxDatabaseId = -1;
 611     bool found = false;
 612     bool ok = getInt(transaction.get(), MaxDatabaseIdKey::encode(), maxDatabaseId, found);
 613     if (!ok) {
 614         INTERNAL_READ_ERROR(GetNewDatabaseId);
 615         return false;
 616     }
 617     if (!found)
 618         maxDatabaseId = 0;
 619
 620     ASSERT(maxDatabaseId >= 0);
 621
 622     int64_t databaseId = maxDatabaseId + 1;
 623     putInt(transaction.get(), MaxDatabaseIdKey::encode(), databaseId);
 624     if (!transaction->commit()) {
 625         INTERNAL_WRITE_ERROR(GetNewDatabaseId);
 626         return false;
 627     }
 628     newId = databaseId;
 629     return true;
 630 }
 631
 632 // FIXME: LevelDB needs to support uint64_t as the version type.
 633 bool IDBBackingStoreLevelDB::createIDBDatabaseMetaData(IDBDatabaseMetadata& metadata)
 634 {
 635     bool ok = getNewDatabaseId(m_db.get(), metadata.id);
 636     if (!ok)
 637         return false;
 638     ASSERT(metadata.id >= 0);
 639
 640     RefPtr<LevelDBTransaction> transaction = LevelDBTransaction::create(m_db.get());
 641     putInt(transaction.get(), DatabaseNameKey::encode(m_identifier, metadata.name), metadata.id);
 642     putVarInt(transaction.get(), DatabaseMetaDataKey::encode(metadata.id, DatabaseMetaDataKey::UserIntVersion), metadata.version);
 643     if (!transaction->commit()) {
 644         INTERNAL_WRITE_ERROR(CreateIDBDatabaseMetaData);
 645         return false;
 646     }
 647     return true;
 648 }
 649
 650 bool IDBBackingStoreLevelDB::updateIDBDatabaseVersion(IDBBackingStoreTransactionInterface& transaction, int64_t rowId, uint64_t version)
 651 {
 652     if (version == IDBDatabaseMetadata::NoIntVersion)
 653         version = IDBDatabaseMetadata::DefaultIntVersion;
 654     putVarInt(IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction), DatabaseMetaDataKey::encode(rowId, DatabaseMetaDataKey::UserIntVersion), version);
 655     return true;
 656 }
 657
 658 static void deleteRange(LevelDBTransaction* transaction, const Vector<char>& begin, const Vector<char>& end)
 659 {
 660     OwnPtr<LevelDBIterator> it = transaction->createIterator();
 661     for (it->seek(begin); it->isValid() && compareKeys(it->key(), end) < 0; it->next())
 662         transaction->remove(it->key());
 663 }
 664
 665 void IDBBackingStoreLevelDB::deleteDatabase(const String& name, BoolCallbackFunction boolCallbackFunction)
 666 {
 667     LOG(StorageAPI, "IDBBackingStoreLevelDB::deleteDatabase");
 668     OwnPtr<LevelDBWriteOnlyTransaction> transaction = LevelDBWriteOnlyTransaction::create(m_db.get());
 669
 670     IDBDatabaseMetadata metadata;
 671     bool success = false;
 672     bool ok = getIDBDatabaseMetaData(name, &metadata, success);
 673     if (!ok) {
 674         boolCallbackFunction(false);
 675         return;
 676     }
 677
 678     if (!success) {
 679         boolCallbackFunction(true);
 680         return;
 681     }
 682
 683     const Vector<char> startKey = DatabaseMetaDataKey::encode(metadata.id, DatabaseMetaDataKey::OriginName);
 684     const Vector<char> stopKey = DatabaseMetaDataKey::encode(metadata.id + 1, DatabaseMetaDataKey::OriginName);
 685     OwnPtr<LevelDBIterator> it = m_db->createIterator();
 686     for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next())
 687         transaction->remove(it->key());
 688
 689     const Vector<char> key = DatabaseNameKey::encode(m_identifier, name);
 690     transaction->remove(key);
 691
 692     if (!transaction->commit()) {
 693         INTERNAL_WRITE_ERROR(DeleteDatabase);
 694         boolCallbackFunction(false);
 695         return;
 696     }
 697     boolCallbackFunction(true);
 698 }
 699
 700 static bool checkObjectStoreAndMetaDataType(const LevelDBIterator* it, const Vector<char>& stopKey, int64_t objectStoreId, int64_t metaDataType)
 701 {
 702     if (!it->isValid() || compareKeys(it->key(), stopKey) >= 0)
 703         return false;
 704
 705     ObjectStoreMetaDataKey metaDataKey;
 706     const char* p = ObjectStoreMetaDataKey::decode(it->key().begin(), it->key().end(), &metaDataKey);
 707     ASSERT_UNUSED(p, p);
 708     if (metaDataKey.objectStoreId() != objectStoreId)
 709         return false;
 710     if (metaDataKey.metaDataType() != metaDataType)
 711         return false;
 712     return true;
 713 }
 714
 715 // FIXME: This should do some error handling rather than plowing ahead when bad data is encountered.
 716 bool IDBBackingStoreLevelDB::getObjectStores(int64_t databaseId, IDBDatabaseMetadata::ObjectStoreMap* objectStores)
 717 {
 718     LOG(StorageAPI, "IDBBackingStoreLevelDB::getObjectStores");
 719     if (!KeyPrefix::isValidDatabaseId(databaseId))
 720         return false;
 721     const Vector<char> startKey = ObjectStoreMetaDataKey::encode(databaseId, 1, 0);
 722     const Vector<char> stopKey = ObjectStoreMetaDataKey::encodeMaxKey(databaseId);
 723
 724     ASSERT(objectStores->isEmpty());
 725
 726     OwnPtr<LevelDBIterator> it = m_db->createIterator();
 727     it->seek(startKey);
 728     while (it->isValid() && compareKeys(it->key(), stopKey) < 0) {
 729         const char* p = it->key().begin();
 730         const char* limit = it->key().end();
 731
 732         ObjectStoreMetaDataKey metaDataKey;
 733         p = ObjectStoreMetaDataKey::decode(p, limit, &metaDataKey);
 734         ASSERT(p);
 735         if (metaDataKey.metaDataType() != ObjectStoreMetaDataKey::Name) {
 736             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
 737             // Possible stale metadata, but don't fail the load.
 738             it->next();
 739             continue;
 740         }
 741
 742         int64_t objectStoreId = metaDataKey.objectStoreId();
 743
 744         // FIXME: Do this by direct key lookup rather than iteration, to simplify.
 745         String objectStoreName = decodeString(it->value().begin(), it->value().end());
 746
 747         it->next();
 748         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::KeyPath)) {
 749             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
 750             break;
 751         }
 752         IDBKeyPath keyPath = decodeIDBKeyPath(it->value().begin(), it->value().end());
 753
 754         it->next();
 755         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::AutoIncrement)) {
 756             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
 757             break;
 758         }
 759         bool autoIncrement = decodeBool(it->value().begin(), it->value().end());
 760
 761         it->next(); // Is evicatble.
 762         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::Evictable)) {
 763             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
 764             break;
 765         }
 766
 767         it->next(); // Last version.
 768         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::LastVersion)) {
 769             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
 770             break;
 771         }
 772
 773         it->next(); // Maximum index id allocated.
 774         if (!checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::MaxIndexId)) {
 775             INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
 776             break;
 777         }
 778         int64_t maxIndexId = decodeInt(it->value().begin(), it->value().end());
 779
 780         it->next(); // [optional] has key path (is not null)
 781         if (checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::HasKeyPath)) {
 782             bool hasKeyPath = decodeBool(it->value().begin(), it->value().end());
 783             // This check accounts for two layers of legacy coding:
 784             // (1) Initially, hasKeyPath was added to distinguish null vs. string.
 785             // (2) Later, null vs. string vs. array was stored in the keyPath itself.
 786             // So this check is only relevant for string-type keyPaths.
 787             if (!hasKeyPath && (keyPath.type() == IDBKeyPath::StringType && !keyPath.string().isEmpty())) {
 788                 INTERNAL_CONSISTENCY_ERROR(GetObjectStores);
 789                 break;
 790             }
 791             if (!hasKeyPath)
 792                 keyPath = IDBKeyPath();
 793             it->next();
 794         }
 795
 796         int64_t keyGeneratorCurrentNumber = -1;
 797         if (checkObjectStoreAndMetaDataType(it.get(), stopKey, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber)) {
 798             keyGeneratorCurrentNumber = decodeInt(it->value().begin(), it->value().end());
 799             // FIXME: Return keyGeneratorCurrentNumber, cache in object store, and write lazily to backing store.
 800             // For now, just assert that if it was written it was valid.
 801             ASSERT_UNUSED(keyGeneratorCurrentNumber, keyGeneratorCurrentNumber >= KeyGeneratorInitialNumber);
 802             it->next();
 803         }
 804
 805         IDBObjectStoreMetadata metadata(objectStoreName, objectStoreId, keyPath, autoIncrement, maxIndexId);
 806         if (!getIndexes(databaseId, objectStoreId, &metadata.indexes))
 807             return false;
 808         objectStores->set(objectStoreId, metadata);
 809     }
 810     return true;
 811 }
 812
 813 WARN_UNUSED_RETURN static bool setMaxObjectStoreId(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId)
 814 {
 815     const Vector<char> maxObjectStoreIdKey = DatabaseMetaDataKey::encode(databaseId, DatabaseMetaDataKey::MaxObjectStoreId);
 816     int64_t maxObjectStoreId = -1;
 817     bool ok = getMaxObjectStoreId(transaction, maxObjectStoreIdKey, maxObjectStoreId);
 818     if (!ok) {
 819         INTERNAL_READ_ERROR(SetMaxObjectStoreId);
 820         return false;
 821     }
 822
 823     if (objectStoreId <= maxObjectStoreId) {
 824         INTERNAL_CONSISTENCY_ERROR(SetMaxObjectStoreId);
 825         return false;
 826     }
 827     putInt(transaction, maxObjectStoreIdKey, objectStoreId);
 828     return true;
 829 }
 830
 831 bool IDBBackingStoreLevelDB::createObjectStore(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, const String& name, const IDBKeyPath& keyPath, bool autoIncrement)
 832 {
 833     LOG(StorageAPI, "IDBBackingStoreLevelDB::createObjectStore");
 834     if (!KeyPrefix::validIds(databaseId, objectStoreId))
 835         return false;
 836     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
 837     if (!setMaxObjectStoreId(levelDBTransaction, databaseId, objectStoreId))
 838         return false;
 839
 840     const Vector<char> nameKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::Name);
 841     const Vector<char> keyPathKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyPath);
 842     const Vector<char> autoIncrementKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::AutoIncrement);
 843     const Vector<char> evictableKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::Evictable);
 844     const Vector<char> lastVersionKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::LastVersion);
 845     const Vector<char> maxIndexIdKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::MaxIndexId);
 846     const Vector<char> hasKeyPathKey  = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::HasKeyPath);
 847     const Vector<char> keyGeneratorCurrentNumberKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber);
 848     const Vector<char> namesKey = ObjectStoreNamesKey::encode(databaseId, name);
 849
 850     putString(levelDBTransaction, nameKey, name);
 851     putIDBKeyPath(levelDBTransaction, keyPathKey, keyPath);
 852     putInt(levelDBTransaction, autoIncrementKey, autoIncrement);
 853     putInt(levelDBTransaction, evictableKey, false);
 854     putInt(levelDBTransaction, lastVersionKey, 1);
 855     putInt(levelDBTransaction, maxIndexIdKey, MinimumIndexId);
 856     putBool(levelDBTransaction, hasKeyPathKey, !keyPath.isNull());
 857     putInt(levelDBTransaction, keyGeneratorCurrentNumberKey, KeyGeneratorInitialNumber);
 858     putInt(levelDBTransaction, namesKey, objectStoreId);
 859     return true;
 860 }
 861
 862 bool IDBBackingStoreLevelDB::deleteObjectStore(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId)
 863 {
 864     LOG(StorageAPI, "IDBBackingStoreLevelDB::deleteObjectStore");
 865     if (!KeyPrefix::validIds(databaseId, objectStoreId))
 866         return false;
 867     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
 868
 869     String objectStoreName;
 870     bool found = false;
 871     bool ok = getString(levelDBTransaction, ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::Name), objectStoreName, found);
 872     if (!ok) {
 873         INTERNAL_READ_ERROR(DeleteObjectStore);
 874         return false;
 875     }
 876     if (!found) {
 877         INTERNAL_CONSISTENCY_ERROR(DeleteObjectStore);
 878         return false;
 879     }
 880
 881     deleteRange(levelDBTransaction, ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, 0), ObjectStoreMetaDataKey::encodeMaxKey(databaseId, objectStoreId));
 882
 883     levelDBTransaction->remove(ObjectStoreNamesKey::encode(databaseId, objectStoreName));
 884
 885     deleteRange(levelDBTransaction, IndexFreeListKey::encode(databaseId, objectStoreId, 0), IndexFreeListKey::encodeMaxKey(databaseId, objectStoreId));
 886     deleteRange(levelDBTransaction, IndexMetaDataKey::encode(databaseId, objectStoreId, 0, 0), IndexMetaDataKey::encodeMaxKey(databaseId, objectStoreId));
 887
 888     return clearObjectStore(transaction, databaseId, objectStoreId);
 889 }
 890
 891 bool IDBBackingStoreLevelDB::getRecord(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, const IDBKey& key, Vector<char>& record)
 892 {
 893     LOG(StorageAPI, "IDBBackingStoreLevelDB::getRecord");
 894     if (!KeyPrefix::validIds(databaseId, objectStoreId))
 895         return false;
 896     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
 897
 898     const Vector<char> leveldbKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
 899     Vector<char> data;
 900
 901     record.clear();
 902
 903     bool found = false;
 904     bool ok = levelDBTransaction->safeGet(leveldbKey, data, found);
 905     if (!ok) {
 906         INTERNAL_READ_ERROR(GetRecord);
 907         return false;
 908     }
 909     if (!found)
 910         return true;
 911
 912     int64_t version;
 913     const char* p = decodeVarInt(data.begin(), data.end(), version);
 914     if (!p) {
 915         INTERNAL_READ_ERROR(GetRecord);
 916         return false;
 917     }
 918
 919     record.appendRange(p, static_cast<const char*>(data.end()));
 920     return true;
 921 }
 922
 923 WARN_UNUSED_RETURN static bool getNewVersionNumber(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t& newVersionNumber)
 924 {
 925     const Vector<char> lastVersionKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::LastVersion);
 926
 927     newVersionNumber = -1;
 928     int64_t lastVersion = -1;
 929     bool found = false;
 930     bool ok = getInt(transaction, lastVersionKey, lastVersion, found);
 931     if (!ok) {
 932         INTERNAL_READ_ERROR(GetNewVersionNumber);
 933         return false;
 934     }
 935     if (!found)
 936         lastVersion = 0;
 937
 938     ASSERT(lastVersion >= 0);
 939
 940     int64_t version = lastVersion + 1;
 941     putInt(transaction, lastVersionKey, version);
 942
 943     ASSERT(version > lastVersion); // FIXME: Think about how we want to handle the overflow scenario.
 944
 945     newVersionNumber = version;
 946     return true;
 947 }
 948
 949 bool IDBBackingStoreLevelDB::putRecord(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, const IDBKey& key, PassRefPtr<SharedBuffer> prpValue, IDBRecordIdentifier* recordIdentifier)
 950 {
 951     LOG(StorageAPI, "IDBBackingStoreLevelDB::putRecord");
 952     if (!KeyPrefix::validIds(databaseId, objectStoreId))
 953         return false;
 954     ASSERT(key.isValid());
 955
 956     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
 957     int64_t version = -1;
 958     bool ok = getNewVersionNumber(levelDBTransaction, databaseId, objectStoreId, version);
 959     if (!ok)
 960         return false;
 961     ASSERT(version >= 0);
 962     const Vector<char> objectStoredataKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
 963
 964     Vector<char> v;
 965     v.appendVector(encodeVarInt(version));
 966     RefPtr<SharedBuffer> value = prpValue;
 967     ASSERT(value);
 968     v.append(value->data(), value->size());
 969
 970     levelDBTransaction->put(objectStoredataKey, v);
 971
 972     const Vector<char> existsEntryKey = ExistsEntryKey::encode(databaseId, objectStoreId, key);
 973     levelDBTransaction->put(existsEntryKey, encodeInt(version));
 974
 975     recordIdentifier->reset(encodeIDBKey(key), version);
 976     return true;
 977 }
 978
 979 bool IDBBackingStoreLevelDB::clearObjectStore(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId)
 980 {
 981     LOG(StorageAPI, "IDBBackingStoreLevelDB::clearObjectStore");
 982     if (!KeyPrefix::validIds(databaseId, objectStoreId))
 983         return false;
 984     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
 985     const Vector<char> startKey = KeyPrefix(databaseId, objectStoreId).encode();
 986     const Vector<char> stopKey = KeyPrefix(databaseId, objectStoreId + 1).encode();
 987
 988     deleteRange(levelDBTransaction, startKey, stopKey);
 989     return true;
 990 }
 991
 992 bool IDBBackingStoreLevelDB::deleteRecord(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, const IDBRecordIdentifier& recordIdentifier)
 993 {
 994     LOG(StorageAPI, "IDBBackingStoreLevelDB::deleteRecord");
 995
 996     if (!KeyPrefix::validIds(databaseId, objectStoreId))
 997         return false;
 998     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
 999
1000     const Vector<char> objectStoreDataKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, recordIdentifier.encodedPrimaryKey());
1001     levelDBTransaction->remove(objectStoreDataKey);
1002
1003     const Vector<char> existsEntryKey = ExistsEntryKey::encode(databaseId, objectStoreId, recordIdentifier.encodedPrimaryKey());
1004     levelDBTransaction->remove(existsEntryKey);
1005     return true;
1006 }
1007
1008
1009 bool IDBBackingStoreLevelDB::getKeyGeneratorCurrentNumber(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, int64_t& keyGeneratorCurrentNumber)
1010 {
1011     if (!KeyPrefix::validIds(databaseId, objectStoreId))
1012         return false;
1013     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1014
1015     const Vector<char> keyGeneratorCurrentNumberKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber);
1016
1017     keyGeneratorCurrentNumber = -1;
1018     Vector<char> data;
1019
1020     bool found = false;
1021     bool ok = levelDBTransaction->safeGet(keyGeneratorCurrentNumberKey, data, found);
1022     if (!ok) {
1023         INTERNAL_READ_ERROR(GetKeyGeneratorCurrentNumber);
1024         return false;
1025     }
1026     if (found)
1027         keyGeneratorCurrentNumber = decodeInt(data.begin(), data.end());
1028     else {
1029         // Previously, the key generator state was not stored explicitly but derived from the
1030         // maximum numeric key present in existing data. This violates the spec as the data may
1031         // be cleared but the key generator state must be preserved.
1032         const Vector<char> startKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, minIDBKey());
1033         const Vector<char> stopKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, maxIDBKey());
1034
1035         OwnPtr<LevelDBIterator> it = levelDBTransaction->createIterator();
1036         int64_t maxNumericKey = 0;
1037
1038         for (it->seek(startKey); it->isValid() && compareKeys(it->key(), stopKey) < 0; it->next()) {
1039             const char* p = it->key().begin();
1040             const char* limit = it->key().end();
1041
1042             ObjectStoreDataKey dataKey;
1043             p = ObjectStoreDataKey::decode(p, limit, &dataKey);
1044             ASSERT(p);
1045
1046             if (dataKey.userKey()->type() == IDBKey::NumberType) {
1047                 int64_t n = static_cast<int64_t>(dataKey.userKey()->number());
1048                 if (n > maxNumericKey)
1049                     maxNumericKey = n;
1050             }
1051         }
1052
1053         keyGeneratorCurrentNumber = maxNumericKey + 1;
1054     }
1055
1056     return keyGeneratorCurrentNumber;
1057 }
1058
1059 bool IDBBackingStoreLevelDB::maybeUpdateKeyGeneratorCurrentNumber(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, int64_t newNumber, bool checkCurrent)
1060 {
1061     if (!KeyPrefix::validIds(databaseId, objectStoreId))
1062         return false;
1063     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1064
1065     if (checkCurrent) {
1066         int64_t currentNumber;
1067         bool ok = getKeyGeneratorCurrentNumber(transaction, databaseId, objectStoreId, currentNumber);
1068         if (!ok)
1069             return false;
1070         if (newNumber <= currentNumber)
1071             return true;
1072     }
1073
1074     const Vector<char> keyGeneratorCurrentNumberKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::KeyGeneratorCurrentNumber);
1075     putInt(levelDBTransaction, keyGeneratorCurrentNumberKey, newNumber);
1076     return true;
1077 }
1078
1079 bool IDBBackingStoreLevelDB::keyExistsInObjectStore(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, const IDBKey& key, RefPtr<IDBRecordIdentifier>& foundIDBRecordIdentifier)
1080 {
1081     LOG(StorageAPI, "IDBBackingStoreLevelDB::keyExistsInObjectStore");
1082     if (!KeyPrefix::validIds(databaseId, objectStoreId))
1083         return false;
1084     bool found = false;
1085     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1086     const Vector<char> leveldbKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, key);
1087     Vector<char> data;
1088
1089     bool ok = levelDBTransaction->safeGet(leveldbKey, data, found);
1090     if (!ok) {
1091         INTERNAL_READ_ERROR(KeyExistsInObjectStore);
1092         return false;
1093     }
1094     if (!found)
1095         return true;
1096
1097     int64_t version;
1098     if (!decodeVarInt(data.begin(), data.end(), version))
1099         return false;
1100
1101     foundIDBRecordIdentifier = IDBRecordIdentifier::create(encodeIDBKey(key), version);
1102     return true;
1103 }
1104
1105 static bool checkIndexAndMetaDataKey(const LevelDBIterator* it, const Vector<char>& stopKey, int64_t indexId, unsigned char metaDataType)
1106 {
1107     if (!it->isValid() || compareKeys(it->key(), stopKey) >= 0)
1108         return false;
1109
1110     IndexMetaDataKey metaDataKey;
1111     const char* p = IndexMetaDataKey::decode(it->key().begin(), it->key().end(), &metaDataKey);
1112     ASSERT_UNUSED(p, p);
1113     if (metaDataKey.indexId() != indexId)
1114         return false;
1115     if (metaDataKey.metaDataType() != metaDataType)
1116         return false;
1117     return true;
1118 }
1119
1120
1121 // FIXME: This should do some error handling rather than plowing ahead when bad data is encountered.
1122 bool IDBBackingStoreLevelDB::getIndexes(int64_t databaseId, int64_t objectStoreId, IDBObjectStoreMetadata::IndexMap* indexes)
1123 {
1124     LOG(StorageAPI, "IDBBackingStoreLevelDB::getIndexes");
1125     if (!KeyPrefix::validIds(databaseId, objectStoreId))
1126         return false;
1127     const Vector<char> startKey = IndexMetaDataKey::encode(databaseId, objectStoreId, 0, 0);
1128     const Vector<char> stopKey = IndexMetaDataKey::encode(databaseId, objectStoreId + 1, 0, 0);
1129
1130     ASSERT(indexes->isEmpty());
1131
1132     OwnPtr<LevelDBIterator> it = m_db->createIterator();
1133     it->seek(startKey);
1134     while (it->isValid() && compareKeys(it->key(), stopKey) < 0) {
1135         const char* p = it->key().begin();
1136         const char* limit = it->key().end();
1137
1138         IndexMetaDataKey metaDataKey;
1139         p = IndexMetaDataKey::decode(p, limit, &metaDataKey);
1140         ASSERT(p);
1141         if (metaDataKey.metaDataType() != IndexMetaDataKey::Name) {
1142             INTERNAL_CONSISTENCY_ERROR(GetIndexes);
1143             // Possible stale metadata due to http://webkit.org/b/85557 but don't fail the load.
1144             it->next();
1145             continue;
1146         }
1147
1148         // FIXME: Do this by direct key lookup rather than iteration, to simplify.
1149         int64_t indexId = metaDataKey.indexId();
1150         String indexName = decodeString(it->value().begin(), it->value().end());
1151
1152         it->next(); // unique flag
1153         if (!checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::Unique)) {
1154             INTERNAL_CONSISTENCY_ERROR(GetIndexes);
1155             break;
1156         }
1157         bool indexUnique = decodeBool(it->value().begin(), it->value().end());
1158
1159         it->next(); // keyPath
1160         if (!checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::KeyPath)) {
1161             INTERNAL_CONSISTENCY_ERROR(GetIndexes);
1162             break;
1163         }
1164         IDBKeyPath keyPath = decodeIDBKeyPath(it->value().begin(), it->value().end());
1165
1166         it->next(); // [optional] multiEntry flag
1167         bool indexMultiEntry = false;
1168         if (checkIndexAndMetaDataKey(it.get(), stopKey, indexId, IndexMetaDataKey::MultiEntry)) {
1169             indexMultiEntry = decodeBool(it->value().begin(), it->value().end());
1170             it->next();
1171         }
1172
1173         indexes->set(indexId, IDBIndexMetadata(indexName, indexId, keyPath, indexUnique, indexMultiEntry));
1174     }
1175     return true;
1176 }
1177
1178 WARN_UNUSED_RETURN static bool setMaxIndexId(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1179 {
1180     int64_t maxIndexId = -1;
1181     const Vector<char> maxIndexIdKey = ObjectStoreMetaDataKey::encode(databaseId, objectStoreId, ObjectStoreMetaDataKey::MaxIndexId);
1182     bool found = false;
1183     bool ok = getInt(transaction, maxIndexIdKey, maxIndexId, found);
1184     if (!ok) {
1185         INTERNAL_READ_ERROR(SetMaxIndexId);
1186         return false;
1187     }
1188     if (!found)
1189         maxIndexId = MinimumIndexId;
1190
1191     if (indexId <= maxIndexId) {
1192         INTERNAL_CONSISTENCY_ERROR(SetMaxIndexId);
1193         return false;
1194     }
1195
1196     putInt(transaction, maxIndexIdKey, indexId);
1197     return true;
1198 }
1199
1200 bool IDBBackingStoreLevelDB::createIndex(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const String& name, const IDBKeyPath& keyPath, bool isUnique, bool isMultiEntry)
1201 {
1202     LOG(StorageAPI, "IDBBackingStoreLevelDB::createIndex");
1203     if (!KeyPrefix::validIds(databaseId, objectStoreId, indexId))
1204         return false;
1205     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1206     if (!setMaxIndexId(levelDBTransaction, databaseId, objectStoreId, indexId))
1207         return false;
1208
1209     const Vector<char> nameKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::Name);
1210     const Vector<char> uniqueKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::Unique);
1211     const Vector<char> keyPathKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::KeyPath);
1212     const Vector<char> multiEntryKey = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, IndexMetaDataKey::MultiEntry);
1213
1214     putString(levelDBTransaction, nameKey, name);
1215     putBool(levelDBTransaction, uniqueKey, isUnique);
1216     putIDBKeyPath(levelDBTransaction, keyPathKey, keyPath);
1217     putBool(levelDBTransaction, multiEntryKey, isMultiEntry);
1218     return true;
1219 }
1220
1221 bool IDBBackingStoreLevelDB::deleteIndex(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1222 {
1223     LOG(StorageAPI, "IDBBackingStoreLevelDB::deleteIndex");
1224     if (!KeyPrefix::validIds(databaseId, objectStoreId, indexId))
1225         return false;
1226     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1227
1228     const Vector<char> indexMetaDataStart = IndexMetaDataKey::encode(databaseId, objectStoreId, indexId, 0);
1229     const Vector<char> indexMetaDataEnd = IndexMetaDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
1230     deleteRange(levelDBTransaction, indexMetaDataStart, indexMetaDataEnd);
1231
1232     const Vector<char> indexDataStart = IndexDataKey::encodeMinKey(databaseId, objectStoreId, indexId);
1233     const Vector<char> indexDataEnd = IndexDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
1234     deleteRange(levelDBTransaction, indexDataStart, indexDataEnd);
1235     return true;
1236 }
1237
1238 bool IDBBackingStoreLevelDB::putIndexDataForRecord(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, const IDBRecordIdentifier* recordIdentifier)
1239 {
1240     LOG(StorageAPI, "IDBBackingStoreLevelDB::putIndexDataForRecord");
1241     ASSERT(key.isValid());
1242     ASSERT(recordIdentifier);
1243     if (!KeyPrefix::validIds(databaseId, objectStoreId, indexId))
1244         return false;
1245
1246     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1247     const Vector<char> indexDataKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, encodeIDBKey(key), recordIdentifier->encodedPrimaryKey());
1248
1249     Vector<char> data;
1250     data.appendVector(encodeVarInt(recordIdentifier->version()));
1251     data.appendVector(recordIdentifier->encodedPrimaryKey());
1252
1253     levelDBTransaction->put(indexDataKey, data);
1254     return true;
1255 }
1256
1257 static bool findGreatestKeyLessThanOrEqual(LevelDBTransaction* transaction, const Vector<char>& target, Vector<char>& foundKey)
1258 {
1259     OwnPtr<LevelDBIterator> it = transaction->createIterator();
1260     it->seek(target);
1261
1262     if (!it->isValid()) {
1263         it->seekToLast();
1264         if (!it->isValid())
1265             return false;
1266     }
1267
1268     while (IDBBackingStoreLevelDB::compareIndexKeys(it->key(), target) > 0) {
1269         it->prev();
1270         if (!it->isValid())
1271             return false;
1272     }
1273
1274     do {
1275         foundKey.clear();
1276         foundKey.append(it->key().begin(), it->key().end() - it->key().begin());
1277
1278         // There can be several index keys that compare equal. We want the last one.
1279         it->next();
1280     } while (it->isValid() && !IDBBackingStoreLevelDB::compareIndexKeys(it->key(), target));
1281
1282     return true;
1283 }
1284
1285 static bool versionExists(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t version, const Vector<char>& encodedPrimaryKey, bool& exists)
1286 {
1287     const Vector<char> key = ExistsEntryKey::encode(databaseId, objectStoreId, encodedPrimaryKey);
1288     Vector<char> data;
1289
1290     bool ok = transaction->safeGet(key, data, exists);
1291     if (!ok) {
1292         INTERNAL_READ_ERROR(VersionExists);
1293         return false;
1294     }
1295     if (!exists)
1296         return true;
1297
1298     exists = (decodeInt(data.begin(), data.end()) == version);
1299     return true;
1300 }
1301
1302 bool IDBBackingStoreLevelDB::findKeyInIndex(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, Vector<char>& foundEncodedPrimaryKey, bool& found)
1303 {
1304     LOG(StorageAPI, "IDBBackingStoreLevelDB::findKeyInIndex");
1305     ASSERT(KeyPrefix::validIds(databaseId, objectStoreId, indexId));
1306
1307     ASSERT(foundEncodedPrimaryKey.isEmpty());
1308     found = false;
1309
1310     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1311     const Vector<char> leveldbKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, key);
1312     OwnPtr<LevelDBIterator> it = levelDBTransaction->createIterator();
1313     it->seek(leveldbKey);
1314
1315     for (;;) {
1316         if (!it->isValid())
1317             return true;
1318         if (compareIndexKeys(it->key(), leveldbKey) > 0)
1319             return true;
1320
1321         int64_t version;
1322         const char* p = decodeVarInt(it->value().begin(), it->value().end(), version);
1323         if (!p) {
1324             INTERNAL_READ_ERROR(FindKeyInIndex);
1325             return false;
1326         }
1327         foundEncodedPrimaryKey.append(p, it->value().end() - p);
1328
1329         bool exists = false;
1330         bool ok = versionExists(levelDBTransaction, databaseId, objectStoreId, version, foundEncodedPrimaryKey, exists);
1331         if (!ok)
1332             return false;
1333         if (!exists) {
1334             // Delete stale index data entry and continue.
1335             levelDBTransaction->remove(it->key());
1336             it->next();
1337             continue;
1338         }
1339         found = true;
1340         return true;
1341     }
1342 }
1343
1344 bool IDBBackingStoreLevelDB::getPrimaryKeyViaIndex(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& key, RefPtr<IDBKey>& primaryKey)
1345 {
1346     LOG(StorageAPI, "IDBBackingStoreLevelDB::getPrimaryKeyViaIndex");
1347     if (!KeyPrefix::validIds(databaseId, objectStoreId, indexId))
1348         return false;
1349
1350     bool found = false;
1351     Vector<char> foundEncodedPrimaryKey;
1352     bool ok = findKeyInIndex(transaction, databaseId, objectStoreId, indexId, key, foundEncodedPrimaryKey, found);
1353     if (!ok) {
1354         INTERNAL_READ_ERROR(GetPrimaryKeyViaIndex);
1355         return false;
1356     }
1357     if (found) {
1358         decodeIDBKey(foundEncodedPrimaryKey.begin(), foundEncodedPrimaryKey.end(), primaryKey);
1359         return true;
1360     }
1361
1362     return true;
1363 }
1364
1365 bool IDBBackingStoreLevelDB::keyExistsInIndex(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& indexKey, RefPtr<IDBKey>& foundPrimaryKey, bool& exists)
1366 {
1367     LOG(StorageAPI, "IDBBackingStoreLevelDB::keyExistsInIndex");
1368     if (!KeyPrefix::validIds(databaseId, objectStoreId, indexId))
1369         return false;
1370
1371     exists = false;
1372     Vector<char> foundEncodedPrimaryKey;
1373     bool ok = findKeyInIndex(transaction, databaseId, objectStoreId, indexId, indexKey, foundEncodedPrimaryKey, exists);
1374     if (!ok) {
1375         INTERNAL_READ_ERROR(KeyExistsInIndex);
1376         return false;
1377     }
1378     if (!exists)
1379         return true;
1380
1381     decodeIDBKey(foundEncodedPrimaryKey.begin(), foundEncodedPrimaryKey.end(), foundPrimaryKey);
1382     return true;
1383 }
1384
1385
1386 bool IDBBackingStoreLevelDB::makeIndexWriters(IDBTransactionBackendInterface& transaction, int64_t databaseId, const IDBObjectStoreMetadata& objectStore, IDBKey& primaryKey, bool keyWasGenerated, const Vector<int64_t>& indexIds, const Vector<IndexKeys>& indexKeys, Vector<RefPtr<IDBIndexWriter>>& indexWriters, String* errorMessage, bool& completed)
1387 {
1388     ASSERT(indexIds.size() == indexKeys.size());
1389     completed = false;
1390
1391     HashMap<int64_t, IndexKeys> indexKeyMap;
1392     for (size_t i = 0; i < indexIds.size(); ++i)
1393         indexKeyMap.add(indexIds[i], indexKeys[i]);
1394
1395     for (IDBObjectStoreMetadata::IndexMap::const_iterator it = objectStore.indexes.begin(); it != objectStore.indexes.end(); ++it) {
1396         const IDBIndexMetadata& index = it->value;
1397
1398         IndexKeys keys = indexKeyMap.get(it->key);
1399         // If the objectStore is using autoIncrement, then any indexes with an identical keyPath need to also use the primary (generated) key as a key.
1400         if (keyWasGenerated && (index.keyPath == objectStore.keyPath))
1401             keys.append(&primaryKey);
1402
1403         RefPtr<IDBIndexWriter> indexWriter = IDBIndexWriter::create(index, keys);
1404         bool canAddKeys = false;
1405         bool backingStoreSuccess = indexWriter->verifyIndexKeys(*this, transaction.backingStoreTransaction(), databaseId, objectStore.id, index.id, canAddKeys, &primaryKey, errorMessage);
1406         if (!backingStoreSuccess)
1407             return false;
1408         if (!canAddKeys)
1409             return true;
1410
1411         indexWriters.append(indexWriter.release());
1412     }
1413
1414     completed = true;
1415     return true;
1416 }
1417
1418 PassRefPtr<IDBKey> IDBBackingStoreLevelDB::generateKey(IDBTransactionBackendInterface& transaction, int64_t databaseId, int64_t objectStoreId)
1419 {
1420     const int64_t maxGeneratorValue = 9007199254740992LL; // Maximum integer storable as ECMAScript number.
1421     int64_t currentNumber;
1422     bool ok = getKeyGeneratorCurrentNumber(transaction.backingStoreTransaction(), databaseId, objectStoreId, currentNumber);
1423     if (!ok) {
1424         LOG_ERROR("Failed to getKeyGeneratorCurrentNumber");
1425         return IDBKey::createInvalid();
1426     }
1427     if (currentNumber < 0 || currentNumber > maxGeneratorValue)
1428         return IDBKey::createInvalid();
1429
1430     return IDBKey::createNumber(currentNumber);
1431 }
1432
1433
1434 bool IDBBackingStoreLevelDB::updateKeyGenerator(IDBTransactionBackendInterface& transaction, int64_t databaseId, int64_t objectStoreId, const IDBKey& key, bool checkCurrent)
1435 {
1436     ASSERT(key.type() == IDBKey::NumberType);
1437     return maybeUpdateKeyGeneratorCurrentNumber(transaction.backingStoreTransaction(), databaseId, objectStoreId, static_cast<int64_t>(floor(key.number())) + 1, checkCurrent);
1438 }
1439
1440 class ObjectStoreKeyCursorImpl : public IDBBackingStoreCursorLevelDB {
1441 public:
1442     static PassRefPtr<ObjectStoreKeyCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStoreCursorLevelDB::CursorOptions& cursorOptions)
1443     {
1444         return adoptRef(new ObjectStoreKeyCursorImpl(transaction, cursorOptions));
1445     }
1446
1447     virtual PassRefPtr<IDBBackingStoreCursorInterface> clone()
1448     {
1449         return adoptRef(new ObjectStoreKeyCursorImpl(this));
1450     }
1451
1452     // IDBBackingStoreCursorLevelDB
1453     virtual PassRefPtr<SharedBuffer> value() const OVERRIDE { ASSERT_NOT_REACHED(); return 0; }
1454     virtual bool loadCurrentRow() OVERRIDE;
1455
1456 protected:
1457     virtual Vector<char> encodeKey(const IDBKey &key)
1458     {
1459         return ObjectStoreDataKey::encode(m_cursorOptions.databaseId, m_cursorOptions.objectStoreId, key);
1460     }
1461
1462 private:
1463     ObjectStoreKeyCursorImpl(LevelDBTransaction* transaction, const IDBBackingStoreCursorLevelDB::CursorOptions& cursorOptions)
1464         : IDBBackingStoreCursorLevelDB(transaction, cursorOptions)
1465     {
1466     }
1467
1468     ObjectStoreKeyCursorImpl(const ObjectStoreKeyCursorImpl* other)
1469         : IDBBackingStoreCursorLevelDB(other)
1470     {
1471     }
1472 };
1473
1474 bool ObjectStoreKeyCursorImpl::loadCurrentRow()
1475 {
1476     const char* keyPosition = m_iterator->key().begin();
1477     const char* keyLimit = m_iterator->key().end();
1478
1479     ObjectStoreDataKey objectStoreDataKey;
1480     keyPosition = ObjectStoreDataKey::decode(keyPosition, keyLimit, &objectStoreDataKey);
1481     if (!keyPosition) {
1482         INTERNAL_READ_ERROR(LoadCurrentRow);
1483         return false;
1484     }
1485
1486     m_currentKey = objectStoreDataKey.userKey();
1487
1488     int64_t version;
1489     const char* valuePosition = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), version);
1490     if (!valuePosition) {
1491         INTERNAL_READ_ERROR(LoadCurrentRow);
1492         return false;
1493     }
1494
1495     // FIXME: This re-encodes what was just decoded; try and optimize.
1496     m_recordIdentifier->reset(encodeIDBKey(*m_currentKey), version);
1497
1498     return true;
1499 }
1500
1501 class ObjectStoreCursorImpl : public IDBBackingStoreCursorLevelDB {
1502 public:
1503     static PassRefPtr<ObjectStoreCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStoreCursorLevelDB::CursorOptions& cursorOptions)
1504     {
1505         return adoptRef(new ObjectStoreCursorImpl(transaction, cursorOptions));
1506     }
1507
1508     virtual PassRefPtr<IDBBackingStoreCursorInterface> clone()
1509     {
1510         return adoptRef(new ObjectStoreCursorImpl(this));
1511     }
1512
1513     // IDBBackingStoreCursorLevelDB
1514     virtual PassRefPtr<SharedBuffer> value() const OVERRIDE { return m_currentValue; }
1515     virtual bool loadCurrentRow() OVERRIDE;
1516
1517 protected:
1518     virtual Vector<char> encodeKey(const IDBKey &key)
1519     {
1520         return ObjectStoreDataKey::encode(m_cursorOptions.databaseId, m_cursorOptions.objectStoreId, key);
1521     }
1522
1523 private:
1524     ObjectStoreCursorImpl(LevelDBTransaction* transaction, const IDBBackingStoreCursorLevelDB::CursorOptions& cursorOptions)
1525         : IDBBackingStoreCursorLevelDB(transaction, cursorOptions)
1526     {
1527     }
1528
1529     ObjectStoreCursorImpl(const ObjectStoreCursorImpl* other)
1530         : IDBBackingStoreCursorLevelDB(other)
1531         , m_currentValue(other->m_currentValue)
1532     {
1533     }
1534
1535     RefPtr<SharedBuffer> m_currentValue;
1536 };
1537
1538 bool ObjectStoreCursorImpl::loadCurrentRow()
1539 {
1540     const char* keyPosition = m_iterator->key().begin();
1541     const char* keyLimit = m_iterator->key().end();
1542
1543     ObjectStoreDataKey objectStoreDataKey;
1544     keyPosition = ObjectStoreDataKey::decode(keyPosition, keyLimit, &objectStoreDataKey);
1545     if (!keyPosition) {
1546         INTERNAL_READ_ERROR(LoadCurrentRow);
1547         return false;
1548     }
1549
1550     m_currentKey = objectStoreDataKey.userKey();
1551
1552     int64_t version;
1553     const char* valuePosition = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), version);
1554     if (!valuePosition) {
1555         INTERNAL_READ_ERROR(LoadCurrentRow);
1556         return false;
1557     }
1558
1559     // FIXME: This re-encodes what was just decoded; try and optimize.
1560     m_recordIdentifier->reset(encodeIDBKey(*m_currentKey), version);
1561
1562     Vector<char> value;
1563     value.append(valuePosition, m_iterator->value().end() - valuePosition);
1564     m_currentValue = SharedBuffer::adoptVector(value);
1565     return true;
1566 }
1567
1568 class IndexKeyCursorImpl FINAL : public IDBBackingStoreCursorLevelDB {
1569 public:
1570     static PassRefPtr<IndexKeyCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStoreCursorLevelDB::CursorOptions& cursorOptions)
1571     {
1572         return adoptRef(new IndexKeyCursorImpl(transaction, cursorOptions));
1573     }
1574
1575     virtual PassRefPtr<IDBBackingStoreCursorInterface> clone()
1576     {
1577         return adoptRef(new IndexKeyCursorImpl(this));
1578     }
1579
1580     // IDBBackingStoreCursorLevelDB
1581     virtual PassRefPtr<SharedBuffer> value() const OVERRIDE { ASSERT_NOT_REACHED(); return 0; }
1582     virtual PassRefPtr<IDBKey> primaryKey() const OVERRIDE { return m_primaryKey; }
1583     virtual const IDBRecordIdentifier& recordIdentifier() const OVERRIDE { ASSERT_NOT_REACHED(); return *m_recordIdentifier; }
1584     virtual bool loadCurrentRow() OVERRIDE;
1585
1586 protected:
1587     virtual Vector<char> encodeKey(const IDBKey &key)
1588     {
1589         return IndexDataKey::encode(m_cursorOptions.databaseId, m_cursorOptions.objectStoreId, m_cursorOptions.indexId, key);
1590     }
1591
1592 private:
1593     IndexKeyCursorImpl(LevelDBTransaction* transaction, const IDBBackingStoreCursorLevelDB::CursorOptions& cursorOptions)
1594         : IDBBackingStoreCursorLevelDB(transaction, cursorOptions)
1595     {
1596     }
1597
1598     IndexKeyCursorImpl(const IndexKeyCursorImpl* other)
1599         : IDBBackingStoreCursorLevelDB(other)
1600         , m_primaryKey(other->m_primaryKey)
1601     {
1602     }
1603
1604     RefPtr<IDBKey> m_primaryKey;
1605 };
1606
1607 bool IndexKeyCursorImpl::loadCurrentRow()
1608 {
1609     const char* keyPosition = m_iterator->key().begin();
1610     const char* keyLimit = m_iterator->key().end();
1611
1612     IndexDataKey indexDataKey;
1613     keyPosition = IndexDataKey::decode(keyPosition, keyLimit, &indexDataKey);
1614
1615     m_currentKey = indexDataKey.userKey();
1616
1617     int64_t indexDataVersion;
1618     const char* valuePosition = decodeVarInt(m_iterator->value().begin(), m_iterator->value().end(), indexDataVersion);
1619     if (!valuePosition) {
1620         INTERNAL_READ_ERROR(LoadCurrentRow);
1621         return false;
1622     }
1623
1624     valuePosition = decodeIDBKey(valuePosition, m_iterator->value().end(), m_primaryKey);
1625     if (!valuePosition) {
1626         INTERNAL_READ_ERROR(LoadCurrentRow);
1627         return false;
1628     }
1629
1630     Vector<char> primaryLevelDBKey = ObjectStoreDataKey::encode(indexDataKey.databaseId(), indexDataKey.objectStoreId(), *m_primaryKey);
1631
1632     Vector<char> result;
1633     bool found = false;
1634     bool ok = m_transaction->safeGet(primaryLevelDBKey, result, found);
1635     if (!ok) {
1636         INTERNAL_READ_ERROR(LoadCurrentRow);
1637         return false;
1638     }
1639     if (!found) {
1640         m_transaction->remove(m_iterator->key());
1641         return false;
1642     }
1643
1644     int64_t objectStoreDataVersion;
1645     const char* t = decodeVarInt(result.begin(), result.end(), objectStoreDataVersion);
1646     if (!t) {
1647         INTERNAL_READ_ERROR(LoadCurrentRow);
1648         return false;
1649     }
1650
1651     if (objectStoreDataVersion != indexDataVersion) {
1652         m_transaction->remove(m_iterator->key());
1653         return false;
1654     }
1655
1656     return true;
1657 }
1658
1659 class IndexCursorImpl FINAL : public IDBBackingStoreCursorLevelDB {
1660 public:
1661     static PassRefPtr<IndexCursorImpl> create(LevelDBTransaction* transaction, const IDBBackingStoreCursorLevelDB::CursorOptions& cursorOptions)
1662     {
1663         return adoptRef(new IndexCursorImpl(transaction, cursorOptions));
1664     }
1665
1666     virtual PassRefPtr<IDBBackingStoreCursorInterface> clone()
1667     {
1668         return adoptRef(new IndexCursorImpl(this));
1669     }
1670
1671     // IDBBackingStoreCursorLevelDB
1672     virtual PassRefPtr<SharedBuffer> value() const OVERRIDE { return m_currentValue; }
1673     virtual PassRefPtr<IDBKey> primaryKey() const OVERRIDE { return m_primaryKey; }
1674     virtual const IDBRecordIdentifier& recordIdentifier() const OVERRIDE { ASSERT_NOT_REACHED(); return *m_recordIdentifier; }
1675     virtual bool loadCurrentRow() OVERRIDE;
1676
1677 protected:
1678     virtual Vector<char> encodeKey(const IDBKey &key)
1679     {
1680         return IndexDataKey::encode(m_cursorOptions.databaseId, m_cursorOptions.objectStoreId, m_cursorOptions.indexId, key);
1681     }
1682
1683 private:
1684     IndexCursorImpl(LevelDBTransaction* transaction, const IDBBackingStoreCursorLevelDB::CursorOptions& cursorOptions)
1685         : IDBBackingStoreCursorLevelDB(transaction, cursorOptions)
1686     {
1687     }
1688
1689     IndexCursorImpl(const IndexCursorImpl* other)
1690         : IDBBackingStoreCursorLevelDB(other)
1691         , m_primaryKey(other->m_primaryKey)
1692         , m_currentValue(other->m_currentValue)
1693         , m_primaryLevelDBKey(other->m_primaryLevelDBKey)
1694     {
1695     }
1696
1697     RefPtr<IDBKey> m_primaryKey;
1698     RefPtr<SharedBuffer> m_currentValue;
1699     Vector<char> m_primaryLevelDBKey;
1700 };
1701
1702 bool IndexCursorImpl::loadCurrentRow()
1703 {
1704     const char* keyPosition = m_iterator->key().begin();
1705     const char* keyLimit = m_iterator->key().end();
1706
1707     IndexDataKey indexDataKey;
1708     keyPosition = IndexDataKey::decode(keyPosition, keyLimit, &indexDataKey);
1709
1710     m_currentKey = indexDataKey.userKey();
1711
1712     const char* valuePosition = m_iterator->value().begin();
1713     const char* valueLimit = m_iterator->value().end();
1714
1715     int64_t indexDataVersion;
1716     valuePosition = decodeVarInt(valuePosition, valueLimit, indexDataVersion);
1717     if (!valuePosition) {
1718         INTERNAL_READ_ERROR(LoadCurrentRow);
1719         return false;
1720     }
1721     valuePosition = decodeIDBKey(valuePosition, valueLimit, m_primaryKey);
1722     if (!valuePosition) {
1723         INTERNAL_READ_ERROR(LoadCurrentRow);
1724         return false;
1725     }
1726
1727     m_primaryLevelDBKey = ObjectStoreDataKey::encode(indexDataKey.databaseId(), indexDataKey.objectStoreId(), *m_primaryKey);
1728
1729     Vector<char> result;
1730     bool found = false;
1731     bool ok = m_transaction->safeGet(m_primaryLevelDBKey, result, found);
1732     if (!ok) {
1733         INTERNAL_READ_ERROR(LoadCurrentRow);
1734         return false;
1735     }
1736     if (!found) {
1737         m_transaction->remove(m_iterator->key());
1738         return false;
1739     }
1740
1741     int64_t objectStoreDataVersion;
1742     valuePosition = decodeVarInt(result.begin(), result.end(), objectStoreDataVersion);
1743     if (!valuePosition) {
1744         INTERNAL_READ_ERROR(LoadCurrentRow);
1745         return false;
1746     }
1747
1748     if (objectStoreDataVersion != indexDataVersion) {
1749         m_transaction->remove(m_iterator->key());
1750         return false;
1751     }
1752
1753     Vector<char> value;
1754     value.append(valuePosition, result.end() - valuePosition);
1755     m_currentValue = SharedBuffer::adoptVector(value);
1756     return true;
1757 }
1758
1759 static bool objectStoreCursorOptions(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IndexedDB::CursorDirection direction, IDBBackingStoreCursorLevelDB::CursorOptions& cursorOptions)
1760 {
1761     cursorOptions.databaseId = databaseId;
1762     cursorOptions.objectStoreId = objectStoreId;
1763
1764     bool lowerBound = range && range->lower();
1765     bool upperBound = range && range->upper();
1766     cursorOptions.forward = (direction == IndexedDB::CursorNextNoDuplicate || direction == IndexedDB::CursorNext);
1767     cursorOptions.unique = (direction == IndexedDB::CursorNextNoDuplicate || direction == IndexedDB::CursorPrevNoDuplicate);
1768
1769     if (!lowerBound) {
1770         cursorOptions.lowKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, minIDBKey());
1771         cursorOptions.lowOpen = true; // Not included.
1772     } else {
1773         cursorOptions.lowKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, *range->lower());
1774         cursorOptions.lowOpen = range->lowerOpen();
1775     }
1776
1777     if (!upperBound) {
1778         cursorOptions.highKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, maxIDBKey());
1779
1780         if (cursorOptions.forward)
1781             cursorOptions.highOpen = true; // Not included.
1782         else {
1783             // We need a key that exists.
1784             if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, cursorOptions.highKey))
1785                 return false;
1786             cursorOptions.highOpen = false;
1787         }
1788     } else {
1789         cursorOptions.highKey = ObjectStoreDataKey::encode(databaseId, objectStoreId, *range->upper());
1790         cursorOptions.highOpen = range->upperOpen();
1791
1792         if (!cursorOptions.forward) {
1793             // For reverse cursors, we need a key that exists.
1794             Vector<char> foundHighKey;
1795             if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, foundHighKey))
1796                 return false;
1797
1798             // If the target key should not be included, but we end up with a smaller key, we should include that.
1799             if (cursorOptions.highOpen && IDBBackingStoreLevelDB::compareIndexKeys(foundHighKey, cursorOptions.highKey) < 0)
1800                 cursorOptions.highOpen = false;
1801
1802             cursorOptions.highKey = foundHighKey;
1803         }
1804     }
1805
1806     return true;
1807 }
1808
1809 static bool indexCursorOptions(LevelDBTransaction* transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IndexedDB::CursorDirection direction, IDBBackingStoreCursorLevelDB::CursorOptions& cursorOptions)
1810 {
1811     ASSERT(transaction);
1812     if (!KeyPrefix::validIds(databaseId, objectStoreId, indexId))
1813         return false;
1814
1815     cursorOptions.databaseId = databaseId;
1816     cursorOptions.objectStoreId = objectStoreId;
1817     cursorOptions.indexId = indexId;
1818
1819     bool lowerBound = range && range->lower();
1820     bool upperBound = range && range->upper();
1821     cursorOptions.forward = (direction == IndexedDB::CursorNextNoDuplicate || direction == IndexedDB::CursorNext);
1822     cursorOptions.unique = (direction == IndexedDB::CursorNextNoDuplicate || direction == IndexedDB::CursorPrevNoDuplicate);
1823
1824     if (!lowerBound) {
1825         cursorOptions.lowKey = IndexDataKey::encodeMinKey(databaseId, objectStoreId, indexId);
1826         cursorOptions.lowOpen = false; // Included.
1827     } else {
1828         cursorOptions.lowKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->lower());
1829         cursorOptions.lowOpen = range->lowerOpen();
1830     }
1831
1832     if (!upperBound) {
1833         cursorOptions.highKey = IndexDataKey::encodeMaxKey(databaseId, objectStoreId, indexId);
1834         cursorOptions.highOpen = false; // Included.
1835
1836         if (!cursorOptions.forward) { // We need a key that exists.
1837             if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, cursorOptions.highKey))
1838                 return false;
1839             cursorOptions.highOpen = false;
1840         }
1841     } else {
1842         cursorOptions.highKey = IndexDataKey::encode(databaseId, objectStoreId, indexId, *range->upper());
1843         cursorOptions.highOpen = range->upperOpen();
1844
1845         Vector<char> foundHighKey;
1846         if (!findGreatestKeyLessThanOrEqual(transaction, cursorOptions.highKey, foundHighKey)) // Seek to the *last* key in the set of non-unique keys.
1847             return false;
1848
1849         // If the target key should not be included, but we end up with a smaller key, we should include that.
1850         if (cursorOptions.highOpen && IDBBackingStoreLevelDB::compareIndexKeys(foundHighKey, cursorOptions.highKey) < 0)
1851             cursorOptions.highOpen = false;
1852
1853         cursorOptions.highKey = foundHighKey;
1854     }
1855
1856     return true;
1857 }
1858 PassRefPtr<IDBBackingStoreCursorInterface> IDBBackingStoreLevelDB::openObjectStoreCursor(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IndexedDB::CursorDirection direction)
1859
1860 {
1861     LOG(StorageAPI, "IDBBackingStoreLevelDB::openObjectStoreCursor");
1862     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1863     IDBBackingStoreCursorLevelDB::CursorOptions cursorOptions;
1864     if (!objectStoreCursorOptions(levelDBTransaction, databaseId, objectStoreId, range, direction, cursorOptions))
1865         return 0;
1866     RefPtr<ObjectStoreCursorImpl> cursor = ObjectStoreCursorImpl::create(levelDBTransaction, cursorOptions);
1867     if (!cursor->firstSeek())
1868         return 0;
1869
1870     return cursor.release();
1871 }
1872
1873 PassRefPtr<IDBBackingStoreCursorInterface> IDBBackingStoreLevelDB::openObjectStoreKeyCursor(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, const IDBKeyRange* range, IndexedDB::CursorDirection direction)
1874 {
1875     LOG(StorageAPI, "IDBBackingStoreLevelDB::openObjectStoreKeyCursor");
1876     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1877     IDBBackingStoreCursorLevelDB::CursorOptions cursorOptions;
1878     if (!objectStoreCursorOptions(levelDBTransaction, databaseId, objectStoreId, range, direction, cursorOptions))
1879         return 0;
1880     RefPtr<ObjectStoreKeyCursorImpl> cursor = ObjectStoreKeyCursorImpl::create(levelDBTransaction, cursorOptions);
1881     if (!cursor->firstSeek())
1882         return 0;
1883
1884     return cursor.release();
1885 }
1886
1887 PassRefPtr<IDBBackingStoreCursorInterface> IDBBackingStoreLevelDB::openIndexKeyCursor(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IndexedDB::CursorDirection direction)
1888 {
1889     LOG(StorageAPI, "IDBBackingStoreLevelDB::openIndexKeyCursor");
1890     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1891     IDBBackingStoreCursorLevelDB::CursorOptions cursorOptions;
1892     if (!indexCursorOptions(levelDBTransaction, databaseId, objectStoreId, indexId, range, direction, cursorOptions))
1893         return 0;
1894     RefPtr<IndexKeyCursorImpl> cursor = IndexKeyCursorImpl::create(levelDBTransaction, cursorOptions);
1895     if (!cursor->firstSeek())
1896         return 0;
1897
1898     return cursor.release();
1899 }
1900
1901 PassRefPtr<IDBBackingStoreCursorInterface> IDBBackingStoreLevelDB::openIndexCursor(IDBBackingStoreTransactionInterface& transaction, int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKeyRange* range, IndexedDB::CursorDirection direction)
1902 {
1903     LOG(StorageAPI, "IDBBackingStoreLevelDB::openIndexCursor");
1904     LevelDBTransaction* levelDBTransaction = IDBBackingStoreTransactionLevelDB::levelDBTransactionFrom(transaction);
1905     IDBBackingStoreCursorLevelDB::CursorOptions cursorOptions;
1906     if (!indexCursorOptions(levelDBTransaction, databaseId, objectStoreId, indexId, range, direction, cursorOptions))
1907         return 0;
1908     RefPtr<IndexCursorImpl> cursor = IndexCursorImpl::create(levelDBTransaction, cursorOptions);
1909     if (!cursor->firstSeek())
1910         return 0;
1911
1912     return cursor.release();
1913 }
1914
1915 std::unique_ptr<IDBBackingStoreTransactionInterface> IDBBackingStoreLevelDB::createBackingStoreTransaction()
1916 {
1917     return std::unique_ptr<IDBBackingStoreTransactionInterface>(new IDBBackingStoreTransactionLevelDB(this));
1918 }
1919
1920 } // namespace WebCore
1921
1922 #endif // ENABLE(INDEXED_DATABASE) && USE(LEVELDB)