src/content/browser/indexed_db/indexed_db_backing_store.cc

   1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "content/browser/indexed_db/indexed_db_backing_store.h"
   6
   7 #include "base/file_util.h"
   8 #include "base/logging.h"
   9 #include "base/metrics/histogram.h"
  10 #include "base/strings/string_piece.h"
  11 #include "base/strings/string_util.h"
  12 #include "base/strings/utf_string_conversions.h"
  13 #include "content/browser/indexed_db/indexed_db_leveldb_coding.h"
  14 #include "content/browser/indexed_db/indexed_db_metadata.h"
  15 #include "content/browser/indexed_db/indexed_db_tracing.h"
  16 #include "content/browser/indexed_db/leveldb/leveldb_comparator.h"
  17 #include "content/browser/indexed_db/leveldb/leveldb_database.h"
  18 #include "content/browser/indexed_db/leveldb/leveldb_iterator.h"
  19 #include "content/browser/indexed_db/leveldb/leveldb_transaction.h"
  20 #include "content/common/indexed_db/indexed_db_key.h"
  21 #include "content/common/indexed_db/indexed_db_key_path.h"
  22 #include "content/common/indexed_db/indexed_db_key_range.h"
  23 #include "third_party/WebKit/public/platform/WebIDBTypes.h"
  24 #include "third_party/WebKit/public/web/WebSerializedScriptValueVersion.h"
  25 #include "third_party/leveldatabase/env_chromium.h"
  26 #include "webkit/common/database/database_identifier.h"
  27
  28 using base::StringPiece;
  29
  30 namespace content {
  31
  32 namespace {
  33
  34 static std::string ComputeOriginIdentifier(const GURL& origin_url) {
  35   return webkit_database::GetIdentifierFromOrigin(origin_url) + "@1";
  36 }
  37
  38 static base::FilePath ComputeFileName(const GURL& origin_url) {
  39   return base::FilePath()
  40       .AppendASCII(webkit_database::GetIdentifierFromOrigin(origin_url))
  41       .AddExtension(FILE_PATH_LITERAL(".indexeddb.leveldb"));
  42 }
  43
  44 }  // namespace
  45
  46 static const int64 kKeyGeneratorInitialNumber =
  47     1;  // From the IndexedDB specification.
  48
  49 enum IndexedDBBackingStoreErrorSource {
  50   // 0 - 2 are no longer used.
  51   FIND_KEY_IN_INDEX = 3,
  52   GET_IDBDATABASE_METADATA,
  53   GET_INDEXES,
  54   GET_KEY_GENERATOR_CURRENT_NUMBER,
  55   GET_OBJECT_STORES,
  56   GET_RECORD,
  57   KEY_EXISTS_IN_OBJECT_STORE,
  58   LOAD_CURRENT_ROW,
  59   SET_UP_METADATA,
  60   GET_PRIMARY_KEY_VIA_INDEX,
  61   KEY_EXISTS_IN_INDEX,
  62   VERSION_EXISTS,
  63   DELETE_OBJECT_STORE,
  64   SET_MAX_OBJECT_STORE_ID,
  65   SET_MAX_INDEX_ID,
  66   GET_NEW_DATABASE_ID,
  67   GET_NEW_VERSION_NUMBER,
  68   CREATE_IDBDATABASE_METADATA,
  69   DELETE_DATABASE,
  70   TRANSACTION_COMMIT_METHOD,  // TRANSACTION_COMMIT is a WinNT.h macro
  71   GET_DATABASE_NAMES,
  72   INTERNAL_ERROR_MAX,
  73 };
  74
  75 static void RecordInternalError(const char* type,
  76                                 IndexedDBBackingStoreErrorSource location) {
  77   std::string name;
  78   name.append("WebCore.IndexedDB.BackingStore.").append(type).append("Error");
  79   base::Histogram::FactoryGet(name,
  80                               1,
  81                               INTERNAL_ERROR_MAX,
  82                               INTERNAL_ERROR_MAX + 1,
  83                               base::HistogramBase::kUmaTargetedHistogramFlag)
  84       ->Add(location);
  85 }
  86
  87 // Use to signal conditions that usually indicate developer error, but
  88 // could be caused by data corruption.  A macro is used instead of an
  89 // inline function so that the assert and log report the line number.
  90 #define REPORT_ERROR(type, location)                      \
  91   do {                                                    \
  92     LOG(ERROR) << "IndexedDB " type " Error: " #location; \
  93     NOTREACHED();                                         \
  94     RecordInternalError(type, location);                  \
  95   } while (0)
  96
  97 #define INTERNAL_READ_ERROR(location) REPORT_ERROR("Read", location)
  98 #define INTERNAL_CONSISTENCY_ERROR(location) \
  99   REPORT_ERROR("Consistency", location)
 100 #define INTERNAL_WRITE_ERROR(location) REPORT_ERROR("Write", location)
 101
 102 static void PutBool(LevelDBTransaction* transaction,
 103                     const StringPiece& key,
 104                     bool value) {
 105   std::string buffer;
 106   EncodeBool(value, &buffer);
 107   transaction->Put(key, &buffer);
 108 }
 109
 110 template <typename DBOrTransaction>
 111 static bool GetInt(DBOrTransaction* db,
 112                    const StringPiece& key,
 113                    int64* found_int,
 114                    bool* found) {
 115   std::string result;
 116   bool ok = db->Get(key, &result, found);
 117   if (!ok)
 118     return false;
 119   if (!*found)
 120     return true;
 121   StringPiece slice(result);
 122   return DecodeInt(&slice, found_int) && slice.empty();
 123 }
 124
 125 static void PutInt(LevelDBTransaction* transaction,
 126                    const StringPiece& key,
 127                    int64 value) {
 128   DCHECK_GE(value, 0);
 129   std::string buffer;
 130   EncodeInt(value, &buffer);
 131   transaction->Put(key, &buffer);
 132 }
 133
 134 template <typename DBOrTransaction>
 135 WARN_UNUSED_RESULT static bool GetVarInt(DBOrTransaction* db,
 136                                          const StringPiece& key,
 137                                          int64* found_int,
 138                                          bool* found) {
 139   std::string result;
 140   bool ok = db->Get(key, &result, found);
 141   if (!ok)
 142     return false;
 143   if (!*found)
 144     return true;
 145   StringPiece slice(result);
 146   return DecodeVarInt(&slice, found_int) && slice.empty();
 147 }
 148
 149 static void PutVarInt(LevelDBTransaction* transaction,
 150                       const StringPiece& key,
 151                       int64 value) {
 152   std::string buffer;
 153   EncodeVarInt(value, &buffer);
 154   transaction->Put(key, &buffer);
 155 }
 156
 157 template <typename DBOrTransaction>
 158 WARN_UNUSED_RESULT static bool GetString(DBOrTransaction* db,
 159                                          const StringPiece& key,
 160                                          string16* found_string,
 161                                          bool* found) {
 162   std::string result;
 163   *found = false;
 164   bool ok = db->Get(key, &result, found);
 165   if (!ok)
 166     return false;
 167   if (!*found)
 168     return true;
 169   StringPiece slice(result);
 170   return DecodeString(&slice, found_string) && slice.empty();
 171 }
 172
 173 static void PutString(LevelDBTransaction* transaction,
 174                       const StringPiece& key,
 175                       const string16& value) {
 176   std::string buffer;
 177   EncodeString(value, &buffer);
 178   transaction->Put(key, &buffer);
 179 }
 180
 181 static void PutIDBKeyPath(LevelDBTransaction* transaction,
 182                           const StringPiece& key,
 183                           const IndexedDBKeyPath& value) {
 184   std::string buffer;
 185   EncodeIDBKeyPath(value, &buffer);
 186   transaction->Put(key, &buffer);
 187 }
 188
 189 static int CompareKeys(const StringPiece& a, const StringPiece& b) {
 190   return Compare(a, b, false /*index_keys*/);
 191 }
 192
 193 static int CompareIndexKeys(const StringPiece& a, const StringPiece& b) {
 194   return Compare(a, b, true /*index_keys*/);
 195 }
 196
 197 class Comparator : public LevelDBComparator {
 198  public:
 199   virtual int Compare(const StringPiece& a, const StringPiece& b) const
 200       OVERRIDE {
 201     return content::Compare(a, b, false /*index_keys*/);
 202   }
 203   virtual const char* Name() const OVERRIDE { return "idb_cmp1"; }
 204 };
 205
 206 // 0 - Initial version.
 207 // 1 - Adds UserIntVersion to DatabaseMetaData.
 208 // 2 - Adds DataVersion to to global metadata.
 209 static const int64 kLatestKnownSchemaVersion = 2;
 210 WARN_UNUSED_RESULT static bool IsSchemaKnown(LevelDBDatabase* db, bool* known) {
 211   int64 db_schema_version = 0;
 212   bool found = false;
 213   bool ok = GetInt(db, SchemaVersionKey::Encode(), &db_schema_version, &found);
 214   if (!ok)
 215     return false;
 216   if (!found) {
 217     *known = true;
 218     return true;
 219   }
 220   if (db_schema_version > kLatestKnownSchemaVersion) {
 221     *known = false;
 222     return true;
 223   }
 224
 225   const uint32 latest_known_data_version =
 226       WebKit::kSerializedScriptValueVersion;
 227   int64 db_data_version = 0;
 228   ok = GetInt(db, DataVersionKey::Encode(), &db_data_version, &found);
 229   if (!ok)
 230     return false;
 231   if (!found) {
 232     *known = true;
 233     return true;
 234   }
 235
 236   if (db_data_version > latest_known_data_version) {
 237     *known = false;
 238     return true;
 239   }
 240
 241   *known = true;
 242   return true;
 243 }
 244
 245 WARN_UNUSED_RESULT static bool SetUpMetadata(
 246     LevelDBDatabase* db,
 247     const std::string& origin_identifier) {
 248   const uint32 latest_known_data_version =
 249       WebKit::kSerializedScriptValueVersion;
 250   const std::string schema_version_key = SchemaVersionKey::Encode();
 251   const std::string data_version_key = DataVersionKey::Encode();
 252
 253   scoped_refptr<LevelDBTransaction> transaction = new LevelDBTransaction(db);
 254
 255   int64 db_schema_version = 0;
 256   int64 db_data_version = 0;
 257   bool found = false;
 258   bool ok =
 259       GetInt(transaction.get(), schema_version_key, &db_schema_version, &found);
 260   if (!ok) {
 261     INTERNAL_READ_ERROR(SET_UP_METADATA);
 262     return false;
 263   }
 264   if (!found) {
 265     // Initialize new backing store.
 266     db_schema_version = kLatestKnownSchemaVersion;
 267     PutInt(transaction.get(), schema_version_key, db_schema_version);
 268     db_data_version = latest_known_data_version;
 269     PutInt(transaction.get(), data_version_key, db_data_version);
 270   } else {
 271     // Upgrade old backing store.
 272     DCHECK_LE(db_schema_version, kLatestKnownSchemaVersion);
 273     if (db_schema_version < 1) {
 274       db_schema_version = 1;
 275       PutInt(transaction.get(), schema_version_key, db_schema_version);
 276       const std::string start_key =
 277           DatabaseNameKey::EncodeMinKeyForOrigin(origin_identifier);
 278       const std::string stop_key =
 279           DatabaseNameKey::EncodeStopKeyForOrigin(origin_identifier);
 280       scoped_ptr<LevelDBIterator> it = db->CreateIterator();
 281       for (it->Seek(start_key);
 282            it->IsValid() && CompareKeys(it->Key(), stop_key) < 0;
 283            it->Next()) {
 284         int64 database_id = 0;
 285         found = false;
 286         bool ok = GetInt(transaction.get(), it->Key(), &database_id, &found);
 287         if (!ok) {
 288           INTERNAL_READ_ERROR(SET_UP_METADATA);
 289           return false;
 290         }
 291         if (!found) {
 292           INTERNAL_CONSISTENCY_ERROR(SET_UP_METADATA);
 293           return false;
 294         }
 295         std::string int_version_key = DatabaseMetaDataKey::Encode(
 296             database_id, DatabaseMetaDataKey::USER_INT_VERSION);
 297         PutVarInt(transaction.get(),
 298                   int_version_key,
 299                   IndexedDBDatabaseMetadata::DEFAULT_INT_VERSION);
 300       }
 301     }
 302     if (db_schema_version < 2) {
 303       db_schema_version = 2;
 304       PutInt(transaction.get(), schema_version_key, db_schema_version);
 305       db_data_version = WebKit::kSerializedScriptValueVersion;
 306       PutInt(transaction.get(), data_version_key, db_data_version);
 307     }
 308   }
 309
 310   // All new values will be written using this serialization version.
 311   found = false;
 312   ok = GetInt(transaction.get(), data_version_key, &db_data_version, &found);
 313   if (!ok) {
 314     INTERNAL_READ_ERROR(SET_UP_METADATA);
 315     return false;
 316   }
 317   if (!found) {
 318     INTERNAL_CONSISTENCY_ERROR(SET_UP_METADATA);
 319     return false;
 320   }
 321   if (db_data_version < latest_known_data_version) {
 322     db_data_version = latest_known_data_version;
 323     PutInt(transaction.get(), data_version_key, db_data_version);
 324   }
 325
 326   DCHECK_EQ(db_schema_version, kLatestKnownSchemaVersion);
 327   DCHECK_EQ(db_data_version, latest_known_data_version);
 328
 329   if (!transaction->Commit()) {
 330     INTERNAL_WRITE_ERROR(SET_UP_METADATA);
 331     return false;
 332   }
 333   return true;
 334 }
 335
 336 template <typename DBOrTransaction>
 337 WARN_UNUSED_RESULT static bool GetMaxObjectStoreId(DBOrTransaction* db,
 338                                                    int64 database_id,
 339                                                    int64* max_object_store_id) {
 340   const std::string max_object_store_id_key = DatabaseMetaDataKey::Encode(
 341       database_id, DatabaseMetaDataKey::MAX_OBJECT_STORE_ID);
 342   bool ok =
 343       GetMaxObjectStoreId(db, max_object_store_id_key, max_object_store_id);
 344   return ok;
 345 }
 346
 347 template <typename DBOrTransaction>
 348 WARN_UNUSED_RESULT static bool GetMaxObjectStoreId(
 349     DBOrTransaction* db,
 350     const std::string& max_object_store_id_key,
 351     int64* max_object_store_id) {
 352   *max_object_store_id = -1;
 353   bool found = false;
 354   bool ok = GetInt(db, max_object_store_id_key, max_object_store_id, &found);
 355   if (!ok)
 356     return false;
 357   if (!found)
 358     *max_object_store_id = 0;
 359
 360   DCHECK_GE(*max_object_store_id, 0);
 361   return true;
 362 }
 363
 364 class DefaultLevelDBFactory : public LevelDBFactory {
 365  public:
 366   virtual leveldb::Status OpenLevelDB(const base::FilePath& file_name,
 367                                       const LevelDBComparator* comparator,
 368                                       scoped_ptr<LevelDBDatabase>* db,
 369                                       bool* is_disk_full) OVERRIDE {
 370     return LevelDBDatabase::Open(file_name, comparator, db, is_disk_full);
 371   }
 372   virtual bool DestroyLevelDB(const base::FilePath& file_name) OVERRIDE {
 373     return LevelDBDatabase::Destroy(file_name);
 374   }
 375 };
 376
 377 IndexedDBBackingStore::IndexedDBBackingStore(
 378     const GURL& origin_url,
 379     scoped_ptr<LevelDBDatabase> db,
 380     scoped_ptr<LevelDBComparator> comparator)
 381     : origin_url_(origin_url),
 382       origin_identifier_(ComputeOriginIdentifier(origin_url)),
 383       db_(db.Pass()),
 384       comparator_(comparator.Pass()) {}
 385
 386 IndexedDBBackingStore::~IndexedDBBackingStore() {
 387   // db_'s destructor uses comparator_. The order of destruction is important.
 388   db_.reset();
 389   comparator_.reset();
 390 }
 391
 392 IndexedDBBackingStore::RecordIdentifier::RecordIdentifier(
 393     const std::string& primary_key,
 394     int64 version)
 395     : primary_key_(primary_key), version_(version) {
 396   DCHECK(!primary_key.empty());
 397 }
 398 IndexedDBBackingStore::RecordIdentifier::RecordIdentifier()
 399     : primary_key_(), version_(-1) {}
 400 IndexedDBBackingStore::RecordIdentifier::~RecordIdentifier() {}
 401
 402 IndexedDBBackingStore::Cursor::CursorOptions::CursorOptions() {}
 403 IndexedDBBackingStore::Cursor::CursorOptions::~CursorOptions() {}
 404
 405 enum IndexedDBBackingStoreOpenResult {
 406   INDEXED_DB_BACKING_STORE_OPEN_MEMORY_SUCCESS,
 407   INDEXED_DB_BACKING_STORE_OPEN_SUCCESS,
 408   INDEXED_DB_BACKING_STORE_OPEN_FAILED_DIRECTORY,
 409   INDEXED_DB_BACKING_STORE_OPEN_FAILED_UNKNOWN_SCHEMA,
 410   INDEXED_DB_BACKING_STORE_OPEN_CLEANUP_DESTROY_FAILED,
 411   INDEXED_DB_BACKING_STORE_OPEN_CLEANUP_REOPEN_FAILED,
 412   INDEXED_DB_BACKING_STORE_OPEN_CLEANUP_REOPEN_SUCCESS,
 413   INDEXED_DB_BACKING_STORE_OPEN_FAILED_IO_ERROR_CHECKING_SCHEMA,
 414   INDEXED_DB_BACKING_STORE_OPEN_FAILED_UNKNOWN_ERR,
 415   INDEXED_DB_BACKING_STORE_OPEN_MEMORY_FAILED,
 416   INDEXED_DB_BACKING_STORE_OPEN_ATTEMPT_NON_ASCII,
 417   INDEXED_DB_BACKING_STORE_OPEN_DISK_FULL_DEPRECATED,
 418   INDEXED_DB_BACKING_STORE_OPEN_ORIGIN_TOO_LONG,
 419   INDEXED_DB_BACKING_STORE_OPEN_NO_RECOVERY,
 420   INDEXED_DB_BACKING_STORE_OPEN_MAX,
 421 };
 422
 423 // static
 424 scoped_refptr<IndexedDBBackingStore> IndexedDBBackingStore::Open(
 425     const GURL& origin_url,
 426     const base::FilePath& path_base,
 427     WebKit::WebIDBCallbacks::DataLoss* data_loss,
 428     std::string* data_loss_message,
 429     bool* disk_full) {
 430   *data_loss = WebKit::WebIDBCallbacks::DataLossNone;
 431   DefaultLevelDBFactory leveldb_factory;
 432   return IndexedDBBackingStore::Open(origin_url,
 433                                      path_base,
 434                                      data_loss,
 435                                      data_loss_message,
 436                                      disk_full,
 437                                      &leveldb_factory);
 438 }
 439
 440 static void HistogramOpenStatus(IndexedDBBackingStoreOpenResult result) {
 441   UMA_HISTOGRAM_ENUMERATION("WebCore.IndexedDB.BackingStore.OpenStatus",
 442                             result,
 443                             INDEXED_DB_BACKING_STORE_OPEN_MAX);
 444 }
 445
 446 static bool IsPathTooLong(const base::FilePath& leveldb_dir) {
 447   int limit = file_util::GetMaximumPathComponentLength(leveldb_dir.DirName());
 448   if (limit == -1) {
 449     DLOG(WARNING) << "GetMaximumPathComponentLength returned -1";
 450     // In limited testing, ChromeOS returns 143, other OSes 255.
 451 #if defined(OS_CHROMEOS)
 452     limit = 143;
 453 #else
 454     limit = 255;
 455 #endif
 456   }
 457   size_t component_length = leveldb_dir.BaseName().value().length();
 458   if (component_length > static_cast<uint32_t>(limit)) {
 459     DLOG(WARNING) << "Path component length (" << component_length
 460                   << ") exceeds maximum (" << limit
 461                   << ") allowed by this filesystem.";
 462     const int min = 140;
 463     const int max = 300;
 464     const int num_buckets = 12;
 465     UMA_HISTOGRAM_CUSTOM_COUNTS(
 466         "WebCore.IndexedDB.BackingStore.OverlyLargeOriginLength",
 467         component_length,
 468         min,
 469         max,
 470         num_buckets);
 471     return true;
 472   }
 473   return false;
 474 }
 475
 476 // static
 477 scoped_refptr<IndexedDBBackingStore> IndexedDBBackingStore::Open(
 478     const GURL& origin_url,
 479     const base::FilePath& path_base,
 480     WebKit::WebIDBCallbacks::DataLoss* data_loss,
 481     std::string* data_loss_message,
 482     bool* is_disk_full,
 483     LevelDBFactory* leveldb_factory) {
 484   IDB_TRACE("IndexedDBBackingStore::Open");
 485   DCHECK(!path_base.empty());
 486   *data_loss = WebKit::WebIDBCallbacks::DataLossNone;
 487   *data_loss_message = "";
 488   *is_disk_full = false;
 489
 490   scoped_ptr<LevelDBComparator> comparator(new Comparator());
 491
 492   if (!IsStringASCII(path_base.AsUTF8Unsafe())) {
 493     HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_ATTEMPT_NON_ASCII);
 494   }
 495   if (!file_util::CreateDirectory(path_base)) {
 496     LOG(ERROR) << "Unable to create IndexedDB database path "
 497                << path_base.AsUTF8Unsafe();
 498     HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_FAILED_DIRECTORY);
 499     return scoped_refptr<IndexedDBBackingStore>();
 500   }
 501
 502   const base::FilePath file_path =
 503       path_base.Append(ComputeFileName(origin_url));
 504
 505   if (IsPathTooLong(file_path)) {
 506     HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_ORIGIN_TOO_LONG);
 507     return scoped_refptr<IndexedDBBackingStore>();
 508   }
 509
 510   scoped_ptr<LevelDBDatabase> db;
 511   leveldb::Status status = leveldb_factory->OpenLevelDB(
 512       file_path, comparator.get(), &db, is_disk_full);
 513
 514   DCHECK(!db == !status.ok());
 515   if (!status.ok()) {
 516     if (leveldb_env::IndicatesDiskFull(status)) {
 517       *is_disk_full = true;
 518     } else if (leveldb_env::IsCorruption(status)) {
 519       *data_loss = WebKit::WebIDBCallbacks::DataLossTotal;
 520       *data_loss_message = leveldb_env::GetCorruptionMessage(status);
 521     }
 522   }
 523
 524   bool is_schema_known = false;
 525   if (db) {
 526     bool ok = IsSchemaKnown(db.get(), &is_schema_known);
 527     if (!ok) {
 528       LOG(ERROR) << "IndexedDB had IO error checking schema, treating it as "
 529                     "failure to open";
 530       HistogramOpenStatus(
 531           INDEXED_DB_BACKING_STORE_OPEN_FAILED_IO_ERROR_CHECKING_SCHEMA);
 532       db.reset();
 533       *data_loss = WebKit::WebIDBCallbacks::DataLossTotal;
 534       *data_loss_message = "I/O error checking schema";
 535     } else if (!is_schema_known) {
 536       LOG(ERROR) << "IndexedDB backing store had unknown schema, treating it "
 537                     "as failure to open";
 538       HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_FAILED_UNKNOWN_SCHEMA);
 539       db.reset();
 540       *data_loss = WebKit::WebIDBCallbacks::DataLossTotal;
 541       *data_loss_message = "Unknown schema";
 542     }
 543   }
 544
 545   DCHECK(status.ok() || !is_schema_known || leveldb_env::IsIOError(status) ||
 546          leveldb_env::IsCorruption(status));
 547
 548   if (db) {
 549     HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_SUCCESS);
 550   } else if (leveldb_env::IsIOError(status)) {
 551     LOG(ERROR) << "Unable to open backing store, not trying to recover - "
 552                << status.ToString();
 553     HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_NO_RECOVERY);
 554     return scoped_refptr<IndexedDBBackingStore>();
 555   } else {
 556     DCHECK(!is_schema_known || leveldb_env::IsCorruption(status));
 557     LOG(ERROR) << "IndexedDB backing store open failed, attempting cleanup";
 558     bool success = leveldb_factory->DestroyLevelDB(file_path);
 559     if (!success) {
 560       LOG(ERROR) << "IndexedDB backing store cleanup failed";
 561       HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_CLEANUP_DESTROY_FAILED);
 562       return scoped_refptr<IndexedDBBackingStore>();
 563     }
 564
 565     LOG(ERROR) << "IndexedDB backing store cleanup succeeded, reopening";
 566     leveldb_factory->OpenLevelDB(file_path, comparator.get(), &db, NULL);
 567     if (!db) {
 568       LOG(ERROR) << "IndexedDB backing store reopen after recovery failed";
 569       HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_CLEANUP_REOPEN_FAILED);
 570       return scoped_refptr<IndexedDBBackingStore>();
 571     }
 572     HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_CLEANUP_REOPEN_SUCCESS);
 573   }
 574
 575   if (!db) {
 576     NOTREACHED();
 577     HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_FAILED_UNKNOWN_ERR);
 578     return scoped_refptr<IndexedDBBackingStore>();
 579   }
 580
 581   return Create(origin_url, db.Pass(), comparator.Pass());
 582 }
 583
 584 // static
 585 scoped_refptr<IndexedDBBackingStore> IndexedDBBackingStore::OpenInMemory(
 586     const GURL& origin_url) {
 587   DefaultLevelDBFactory leveldb_factory;
 588   return IndexedDBBackingStore::OpenInMemory(origin_url, &leveldb_factory);
 589 }
 590
 591 // static
 592 scoped_refptr<IndexedDBBackingStore> IndexedDBBackingStore::OpenInMemory(
 593     const GURL& origin_url,
 594     LevelDBFactory* leveldb_factory) {
 595   IDB_TRACE("IndexedDBBackingStore::OpenInMemory");
 596
 597   scoped_ptr<LevelDBComparator> comparator(new Comparator());
 598   scoped_ptr<LevelDBDatabase> db =
 599       LevelDBDatabase::OpenInMemory(comparator.get());
 600   if (!db) {
 601     LOG(ERROR) << "LevelDBDatabase::OpenInMemory failed.";
 602     HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_MEMORY_FAILED);
 603     return scoped_refptr<IndexedDBBackingStore>();
 604   }
 605   HistogramOpenStatus(INDEXED_DB_BACKING_STORE_OPEN_MEMORY_SUCCESS);
 606
 607   return Create(origin_url, db.Pass(), comparator.Pass());
 608 }
 609
 610 // static
 611 scoped_refptr<IndexedDBBackingStore> IndexedDBBackingStore::Create(
 612     const GURL& origin_url,
 613     scoped_ptr<LevelDBDatabase> db,
 614     scoped_ptr<LevelDBComparator> comparator) {
 615   // TODO(jsbell): Handle comparator name changes.
 616
 617   scoped_refptr<IndexedDBBackingStore> backing_store(
 618       new IndexedDBBackingStore(origin_url, db.Pass(), comparator.Pass()));
 619   if (!SetUpMetadata(backing_store->db_.get(),
 620                      backing_store->origin_identifier_))
 621     return scoped_refptr<IndexedDBBackingStore>();
 622
 623   return backing_store;
 624 }
 625
 626 std::vector<string16> IndexedDBBackingStore::GetDatabaseNames() {
 627   std::vector<string16> found_names;
 628   const std::string start_key =
 629       DatabaseNameKey::EncodeMinKeyForOrigin(origin_identifier_);
 630   const std::string stop_key =
 631       DatabaseNameKey::EncodeStopKeyForOrigin(origin_identifier_);
 632
 633   DCHECK(found_names.empty());
 634
 635   scoped_ptr<LevelDBIterator> it = db_->CreateIterator();
 636   for (it->Seek(start_key);
 637        it->IsValid() && CompareKeys(it->Key(), stop_key) < 0;
 638        it->Next()) {
 639     StringPiece slice(it->Key());
 640     DatabaseNameKey database_name_key;
 641     if (!DatabaseNameKey::Decode(&slice, &database_name_key)) {
 642       INTERNAL_CONSISTENCY_ERROR(GET_DATABASE_NAMES);
 643       continue;
 644     }
 645     found_names.push_back(database_name_key.database_name());
 646   }
 647   return found_names;
 648 }
 649
 650 bool IndexedDBBackingStore::GetIDBDatabaseMetaData(
 651     const string16& name,
 652     IndexedDBDatabaseMetadata* metadata,
 653     bool* found) {
 654   const std::string key = DatabaseNameKey::Encode(origin_identifier_, name);
 655   *found = false;
 656
 657   bool ok = GetInt(db_.get(), key, &metadata->id, found);
 658   if (!ok) {
 659     INTERNAL_READ_ERROR(GET_IDBDATABASE_METADATA);
 660     return false;
 661   }
 662   if (!*found)
 663     return true;
 664
 665   ok = GetString(db_.get(),
 666                  DatabaseMetaDataKey::Encode(metadata->id,
 667                                              DatabaseMetaDataKey::USER_VERSION),
 668                  &metadata->version,
 669                  found);
 670   if (!ok) {
 671     INTERNAL_READ_ERROR(GET_IDBDATABASE_METADATA);
 672     return false;
 673   }
 674   if (!*found) {
 675     INTERNAL_CONSISTENCY_ERROR(GET_IDBDATABASE_METADATA);
 676     return false;
 677   }
 678
 679   ok = GetVarInt(db_.get(),
 680                  DatabaseMetaDataKey::Encode(
 681                      metadata->id, DatabaseMetaDataKey::USER_INT_VERSION),
 682                  &metadata->int_version,
 683                  found);
 684   if (!ok) {
 685     INTERNAL_READ_ERROR(GET_IDBDATABASE_METADATA);
 686     return false;
 687   }
 688   if (!*found) {
 689     INTERNAL_CONSISTENCY_ERROR(GET_IDBDATABASE_METADATA);
 690     return false;
 691   }
 692
 693   if (metadata->int_version == IndexedDBDatabaseMetadata::DEFAULT_INT_VERSION)
 694     metadata->int_version = IndexedDBDatabaseMetadata::NO_INT_VERSION;
 695
 696   ok = GetMaxObjectStoreId(
 697       db_.get(), metadata->id, &metadata->max_object_store_id);
 698   if (!ok) {
 699     INTERNAL_READ_ERROR(GET_IDBDATABASE_METADATA);
 700     return false;
 701   }
 702
 703   return true;
 704 }
 705
 706 WARN_UNUSED_RESULT static bool GetNewDatabaseId(LevelDBTransaction* transaction,
 707                                                 int64* new_id) {
 708   *new_id = -1;
 709   int64 max_database_id = -1;
 710   bool found = false;
 711   bool ok =
 712       GetInt(transaction, MaxDatabaseIdKey::Encode(), &max_database_id, &found);
 713   if (!ok) {
 714     INTERNAL_READ_ERROR(GET_NEW_DATABASE_ID);
 715     return false;
 716   }
 717   if (!found)
 718     max_database_id = 0;
 719
 720   DCHECK_GE(max_database_id, 0);
 721
 722   int64 database_id = max_database_id + 1;
 723   PutInt(transaction, MaxDatabaseIdKey::Encode(), database_id);
 724   *new_id = database_id;
 725   return true;
 726 }
 727
 728 bool IndexedDBBackingStore::CreateIDBDatabaseMetaData(const string16& name,
 729                                                       const string16& version,
 730                                                       int64 int_version,
 731                                                       int64* row_id) {
 732   scoped_refptr<LevelDBTransaction> transaction =
 733       new LevelDBTransaction(db_.get());
 734
 735   bool ok = GetNewDatabaseId(transaction.get(), row_id);
 736   if (!ok)
 737     return false;
 738   DCHECK_GE(*row_id, 0);
 739
 740   if (int_version == IndexedDBDatabaseMetadata::NO_INT_VERSION)
 741     int_version = IndexedDBDatabaseMetadata::DEFAULT_INT_VERSION;
 742
 743   PutInt(transaction.get(),
 744          DatabaseNameKey::Encode(origin_identifier_, name),
 745          *row_id);
 746   PutString(
 747       transaction.get(),
 748       DatabaseMetaDataKey::Encode(*row_id, DatabaseMetaDataKey::USER_VERSION),
 749       version);
 750   PutVarInt(transaction.get(),
 751             DatabaseMetaDataKey::Encode(*row_id,
 752                                         DatabaseMetaDataKey::USER_INT_VERSION),
 753             int_version);
 754   if (!transaction->Commit()) {
 755     INTERNAL_WRITE_ERROR(CREATE_IDBDATABASE_METADATA);
 756     return false;
 757   }
 758   return true;
 759 }
 760
 761 bool IndexedDBBackingStore::UpdateIDBDatabaseIntVersion(
 762     IndexedDBBackingStore::Transaction* transaction,
 763     int64 row_id,
 764     int64 int_version) {
 765   if (int_version == IndexedDBDatabaseMetadata::NO_INT_VERSION)
 766     int_version = IndexedDBDatabaseMetadata::DEFAULT_INT_VERSION;
 767   DCHECK_GE(int_version, 0) << "int_version was " << int_version;
 768   PutVarInt(transaction->transaction(),
 769             DatabaseMetaDataKey::Encode(row_id,
 770                                         DatabaseMetaDataKey::USER_INT_VERSION),
 771             int_version);
 772   return true;
 773 }
 774
 775 bool IndexedDBBackingStore::UpdateIDBDatabaseMetaData(
 776     IndexedDBBackingStore::Transaction* transaction,
 777     int64 row_id,
 778     const string16& version) {
 779   PutString(
 780       transaction->transaction(),
 781       DatabaseMetaDataKey::Encode(row_id, DatabaseMetaDataKey::USER_VERSION),
 782       version);
 783   return true;
 784 }
 785
 786 static void DeleteRange(LevelDBTransaction* transaction,
 787                         const std::string& begin,
 788                         const std::string& end) {
 789   scoped_ptr<LevelDBIterator> it = transaction->CreateIterator();
 790   for (it->Seek(begin); it->IsValid() && CompareKeys(it->Key(), end) < 0;
 791        it->Next())
 792     transaction->Remove(it->Key());
 793 }
 794
 795 bool IndexedDBBackingStore::DeleteDatabase(const string16& name) {
 796   IDB_TRACE("IndexedDBBackingStore::DeleteDatabase");
 797   scoped_ptr<LevelDBWriteOnlyTransaction> transaction =
 798       LevelDBWriteOnlyTransaction::Create(db_.get());
 799
 800   IndexedDBDatabaseMetadata metadata;
 801   bool success = false;
 802   bool ok = GetIDBDatabaseMetaData(name, &metadata, &success);
 803   if (!ok)
 804     return false;
 805   if (!success)
 806     return true;
 807
 808   const std::string start_key = DatabaseMetaDataKey::Encode(
 809       metadata.id, DatabaseMetaDataKey::ORIGIN_NAME);
 810   const std::string stop_key = DatabaseMetaDataKey::Encode(
 811       metadata.id + 1, DatabaseMetaDataKey::ORIGIN_NAME);
 812   scoped_ptr<LevelDBIterator> it = db_->CreateIterator();
 813   for (it->Seek(start_key);
 814        it->IsValid() && CompareKeys(it->Key(), stop_key) < 0;
 815        it->Next())
 816     transaction->Remove(it->Key());
 817
 818   const std::string key = DatabaseNameKey::Encode(origin_identifier_, name);
 819   transaction->Remove(key);
 820
 821   if (!transaction->Commit()) {
 822     INTERNAL_WRITE_ERROR(DELETE_DATABASE);
 823     return false;
 824   }
 825   return true;
 826 }
 827
 828 static bool CheckObjectStoreAndMetaDataType(const LevelDBIterator* it,
 829                                             const std::string& stop_key,
 830                                             int64 object_store_id,
 831                                             int64 meta_data_type) {
 832   if (!it->IsValid() || CompareKeys(it->Key(), stop_key) >= 0)
 833     return false;
 834
 835   StringPiece slice(it->Key());
 836   ObjectStoreMetaDataKey meta_data_key;
 837   bool ok = ObjectStoreMetaDataKey::Decode(&slice, &meta_data_key);
 838   DCHECK(ok);
 839   if (meta_data_key.ObjectStoreId() != object_store_id)
 840     return false;
 841   if (meta_data_key.MetaDataType() != meta_data_type)
 842     return false;
 843   return true;
 844 }
 845
 846 // TODO(jsbell): This should do some error handling rather than
 847 // plowing ahead when bad data is encountered.
 848 bool IndexedDBBackingStore::GetObjectStores(
 849     int64 database_id,
 850     IndexedDBDatabaseMetadata::ObjectStoreMap* object_stores) {
 851   IDB_TRACE("IndexedDBBackingStore::GetObjectStores");
 852   if (!KeyPrefix::IsValidDatabaseId(database_id))
 853     return false;
 854   const std::string start_key =
 855       ObjectStoreMetaDataKey::Encode(database_id, 1, 0);
 856   const std::string stop_key =
 857       ObjectStoreMetaDataKey::EncodeMaxKey(database_id);
 858
 859   DCHECK(object_stores->empty());
 860
 861   scoped_ptr<LevelDBIterator> it = db_->CreateIterator();
 862   it->Seek(start_key);
 863   while (it->IsValid() && CompareKeys(it->Key(), stop_key) < 0) {
 864     StringPiece slice(it->Key());
 865     ObjectStoreMetaDataKey meta_data_key;
 866     bool ok = ObjectStoreMetaDataKey::Decode(&slice, &meta_data_key);
 867     DCHECK(ok);
 868     if (meta_data_key.MetaDataType() != ObjectStoreMetaDataKey::NAME) {
 869       INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 870       // Possible stale metadata, but don't fail the load.
 871       it->Next();
 872       continue;
 873     }
 874
 875     int64 object_store_id = meta_data_key.ObjectStoreId();
 876
 877     // TODO(jsbell): Do this by direct key lookup rather than iteration, to
 878     // simplify.
 879     string16 object_store_name;
 880     {
 881       StringPiece slice(it->Value());
 882       if (!DecodeString(&slice, &object_store_name) || !slice.empty())
 883         INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 884     }
 885
 886     it->Next();
 887     if (!CheckObjectStoreAndMetaDataType(it.get(),
 888                                          stop_key,
 889                                          object_store_id,
 890                                          ObjectStoreMetaDataKey::KEY_PATH)) {
 891       INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 892       break;
 893     }
 894     IndexedDBKeyPath key_path;
 895     {
 896       StringPiece slice(it->Value());
 897       if (!DecodeIDBKeyPath(&slice, &key_path) || !slice.empty())
 898         INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 899     }
 900
 901     it->Next();
 902     if (!CheckObjectStoreAndMetaDataType(
 903              it.get(),
 904              stop_key,
 905              object_store_id,
 906              ObjectStoreMetaDataKey::AUTO_INCREMENT)) {
 907       INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 908       break;
 909     }
 910     bool auto_increment;
 911     {
 912       StringPiece slice(it->Value());
 913       if (!DecodeBool(&slice, &auto_increment) || !slice.empty())
 914         INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 915     }
 916
 917     it->Next();  // Is evicatble.
 918     if (!CheckObjectStoreAndMetaDataType(it.get(),
 919                                          stop_key,
 920                                          object_store_id,
 921                                          ObjectStoreMetaDataKey::EVICTABLE)) {
 922       INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 923       break;
 924     }
 925
 926     it->Next();  // Last version.
 927     if (!CheckObjectStoreAndMetaDataType(
 928              it.get(),
 929              stop_key,
 930              object_store_id,
 931              ObjectStoreMetaDataKey::LAST_VERSION)) {
 932       INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 933       break;
 934     }
 935
 936     it->Next();  // Maximum index id allocated.
 937     if (!CheckObjectStoreAndMetaDataType(
 938              it.get(),
 939              stop_key,
 940              object_store_id,
 941              ObjectStoreMetaDataKey::MAX_INDEX_ID)) {
 942       INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 943       break;
 944     }
 945     int64 max_index_id;
 946     {
 947       StringPiece slice(it->Value());
 948       if (!DecodeInt(&slice, &max_index_id) || !slice.empty())
 949         INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 950     }
 951
 952     it->Next();  // [optional] has key path (is not null)
 953     if (CheckObjectStoreAndMetaDataType(it.get(),
 954                                         stop_key,
 955                                         object_store_id,
 956                                         ObjectStoreMetaDataKey::HAS_KEY_PATH)) {
 957       bool has_key_path;
 958       {
 959         StringPiece slice(it->Value());
 960         if (!DecodeBool(&slice, &has_key_path))
 961           INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 962       }
 963       // This check accounts for two layers of legacy coding:
 964       // (1) Initially, has_key_path was added to distinguish null vs. string.
 965       // (2) Later, null vs. string vs. array was stored in the key_path itself.
 966       // So this check is only relevant for string-type key_paths.
 967       if (!has_key_path &&
 968           (key_path.type() == WebKit::WebIDBKeyPathTypeString &&
 969            !key_path.string().empty())) {
 970         INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 971         break;
 972       }
 973       if (!has_key_path)
 974         key_path = IndexedDBKeyPath();
 975       it->Next();
 976     }
 977
 978     int64 key_generator_current_number = -1;
 979     if (CheckObjectStoreAndMetaDataType(
 980             it.get(),
 981             stop_key,
 982             object_store_id,
 983             ObjectStoreMetaDataKey::KEY_GENERATOR_CURRENT_NUMBER)) {
 984       StringPiece slice(it->Value());
 985       if (!DecodeInt(&slice, &key_generator_current_number) || !slice.empty())
 986         INTERNAL_CONSISTENCY_ERROR(GET_OBJECT_STORES);
 987
 988       // TODO(jsbell): Return key_generator_current_number, cache in
 989       // object store, and write lazily to backing store.  For now,
 990       // just assert that if it was written it was valid.
 991       DCHECK_GE(key_generator_current_number, kKeyGeneratorInitialNumber);
 992       it->Next();
 993     }
 994
 995     IndexedDBObjectStoreMetadata metadata(object_store_name,
 996                                           object_store_id,
 997                                           key_path,
 998                                           auto_increment,
 999                                           max_index_id);
1000     if (!GetIndexes(database_id, object_store_id, &metadata.indexes))
1001       return false;
1002     (*object_stores)[object_store_id] = metadata;
1003   }
1004   return true;
1005 }
1006
1007 WARN_UNUSED_RESULT static bool SetMaxObjectStoreId(
1008     LevelDBTransaction* transaction,
1009     int64 database_id,
1010     int64 object_store_id) {
1011   const std::string max_object_store_id_key = DatabaseMetaDataKey::Encode(
1012       database_id, DatabaseMetaDataKey::MAX_OBJECT_STORE_ID);
1013   int64 max_object_store_id = -1;
1014   bool ok = GetMaxObjectStoreId(
1015       transaction, max_object_store_id_key, &max_object_store_id);
1016   if (!ok) {
1017     INTERNAL_READ_ERROR(SET_MAX_OBJECT_STORE_ID);
1018     return false;
1019   }
1020
1021   if (object_store_id <= max_object_store_id) {
1022     INTERNAL_CONSISTENCY_ERROR(SET_MAX_OBJECT_STORE_ID);
1023     return false;
1024   }
1025   PutInt(transaction, max_object_store_id_key, object_store_id);
1026   return true;
1027 }
1028
1029 bool IndexedDBBackingStore::CreateObjectStore(
1030     IndexedDBBackingStore::Transaction* transaction,
1031     int64 database_id,
1032     int64 object_store_id,
1033     const string16& name,
1034     const IndexedDBKeyPath& key_path,
1035     bool auto_increment) {
1036   IDB_TRACE("IndexedDBBackingStore::CreateObjectStore");
1037   if (!KeyPrefix::ValidIds(database_id, object_store_id))
1038     return false;
1039   LevelDBTransaction* leveldb_transaction = transaction->transaction();
1040   if (!SetMaxObjectStoreId(leveldb_transaction, database_id, object_store_id))
1041     return false;
1042
1043   const std::string name_key = ObjectStoreMetaDataKey::Encode(
1044       database_id, object_store_id, ObjectStoreMetaDataKey::NAME);
1045   const std::string key_path_key = ObjectStoreMetaDataKey::Encode(
1046       database_id, object_store_id, ObjectStoreMetaDataKey::KEY_PATH);
1047   const std::string auto_increment_key = ObjectStoreMetaDataKey::Encode(
1048       database_id, object_store_id, ObjectStoreMetaDataKey::AUTO_INCREMENT);
1049   const std::string evictable_key = ObjectStoreMetaDataKey::Encode(
1050       database_id, object_store_id, ObjectStoreMetaDataKey::EVICTABLE);
1051   const std::string last_version_key = ObjectStoreMetaDataKey::Encode(
1052       database_id, object_store_id, ObjectStoreMetaDataKey::LAST_VERSION);
1053   const std::string max_index_id_key = ObjectStoreMetaDataKey::Encode(
1054       database_id, object_store_id, ObjectStoreMetaDataKey::MAX_INDEX_ID);
1055   const std::string has_key_path_key = ObjectStoreMetaDataKey::Encode(
1056       database_id, object_store_id, ObjectStoreMetaDataKey::HAS_KEY_PATH);
1057   const std::string key_generator_current_number_key =
1058       ObjectStoreMetaDataKey::Encode(
1059           database_id,
1060           object_store_id,
1061           ObjectStoreMetaDataKey::KEY_GENERATOR_CURRENT_NUMBER);
1062   const std::string names_key = ObjectStoreNamesKey::Encode(database_id, name);
1063
1064   PutString(leveldb_transaction, name_key, name);
1065   PutIDBKeyPath(leveldb_transaction, key_path_key, key_path);
1066   PutInt(leveldb_transaction, auto_increment_key, auto_increment);
1067   PutInt(leveldb_transaction, evictable_key, false);
1068   PutInt(leveldb_transaction, last_version_key, 1);
1069   PutInt(leveldb_transaction, max_index_id_key, kMinimumIndexId);
1070   PutBool(leveldb_transaction, has_key_path_key, !key_path.IsNull());
1071   PutInt(leveldb_transaction,
1072          key_generator_current_number_key,
1073          kKeyGeneratorInitialNumber);
1074   PutInt(leveldb_transaction, names_key, object_store_id);
1075   return true;
1076 }
1077
1078 bool IndexedDBBackingStore::DeleteObjectStore(
1079     IndexedDBBackingStore::Transaction* transaction,
1080     int64 database_id,
1081     int64 object_store_id) {
1082   IDB_TRACE("IndexedDBBackingStore::DeleteObjectStore");
1083   if (!KeyPrefix::ValidIds(database_id, object_store_id))
1084     return false;
1085   LevelDBTransaction* leveldb_transaction = transaction->transaction();
1086
1087   string16 object_store_name;
1088   bool found = false;
1089   bool ok = GetString(
1090       leveldb_transaction,
1091       ObjectStoreMetaDataKey::Encode(
1092           database_id, object_store_id, ObjectStoreMetaDataKey::NAME),
1093       &object_store_name,
1094       &found);
1095   if (!ok) {
1096     INTERNAL_READ_ERROR(DELETE_OBJECT_STORE);
1097     return false;
1098   }
1099   if (!found) {
1100     INTERNAL_CONSISTENCY_ERROR(DELETE_OBJECT_STORE);
1101     return false;
1102   }
1103
1104   DeleteRange(
1105       leveldb_transaction,
1106       ObjectStoreMetaDataKey::Encode(database_id, object_store_id, 0),
1107       ObjectStoreMetaDataKey::EncodeMaxKey(database_id, object_store_id));
1108
1109   leveldb_transaction->Remove(
1110       ObjectStoreNamesKey::Encode(database_id, object_store_name));
1111
1112   DeleteRange(leveldb_transaction,
1113               IndexFreeListKey::Encode(database_id, object_store_id, 0),
1114               IndexFreeListKey::EncodeMaxKey(database_id, object_store_id));
1115   DeleteRange(leveldb_transaction,
1116               IndexMetaDataKey::Encode(database_id, object_store_id, 0, 0),
1117               IndexMetaDataKey::EncodeMaxKey(database_id, object_store_id));
1118
1119   return ClearObjectStore(transaction, database_id, object_store_id);
1120 }
1121
1122 bool IndexedDBBackingStore::GetRecord(
1123     IndexedDBBackingStore::Transaction* transaction,
1124     int64 database_id,
1125     int64 object_store_id,
1126     const IndexedDBKey& key,
1127     std::string* record) {
1128   IDB_TRACE("IndexedDBBackingStore::GetRecord");
1129   if (!KeyPrefix::ValidIds(database_id, object_store_id))
1130     return false;
1131   LevelDBTransaction* leveldb_transaction = transaction->transaction();
1132
1133   const std::string leveldb_key =
1134       ObjectStoreDataKey::Encode(database_id, object_store_id, key);
1135   std::string data;
1136
1137   record->clear();
1138
1139   bool found = false;
1140   bool ok = leveldb_transaction->Get(leveldb_key, &data, &found);
1141   if (!ok) {
1142     INTERNAL_READ_ERROR(GET_RECORD);
1143     return false;
1144   }
1145   if (!found)
1146     return true;
1147   if (data.empty()) {
1148     INTERNAL_READ_ERROR(GET_RECORD);
1149     return false;
1150   }
1151
1152   int64 version;
1153   StringPiece slice(data);
1154   if (!DecodeVarInt(&slice, &version)) {
1155     INTERNAL_READ_ERROR(GET_RECORD);
1156     return false;
1157   }
1158
1159   *record = slice.as_string();
1160   return true;
1161 }
1162
1163 WARN_UNUSED_RESULT static bool GetNewVersionNumber(
1164     LevelDBTransaction* transaction,
1165     int64 database_id,
1166     int64 object_store_id,
1167     int64* new_version_number) {
1168   const std::string last_version_key = ObjectStoreMetaDataKey::Encode(
1169       database_id, object_store_id, ObjectStoreMetaDataKey::LAST_VERSION);
1170
1171   *new_version_number = -1;
1172   int64 last_version = -1;
1173   bool found = false;
1174   bool ok = GetInt(transaction, last_version_key, &last_version, &found);
1175   if (!ok) {
1176     INTERNAL_READ_ERROR(GET_NEW_VERSION_NUMBER);
1177     return false;
1178   }
1179   if (!found)
1180     last_version = 0;
1181
1182   DCHECK_GE(last_version, 0);
1183
1184   int64 version = last_version + 1;
1185   PutInt(transaction, last_version_key, version);
1186
1187   // TODO(jsbell): Think about how we want to handle the overflow scenario.
1188   DCHECK(version > last_version);
1189
1190   *new_version_number = version;
1191   return true;
1192 }
1193
1194 bool IndexedDBBackingStore::PutRecord(
1195     IndexedDBBackingStore::Transaction* transaction,
1196     int64 database_id,
1197     int64 object_store_id,
1198     const IndexedDBKey& key,
1199     const std::string& value,
1200     RecordIdentifier* record_identifier) {
1201   IDB_TRACE("IndexedDBBackingStore::PutRecord");
1202   if (!KeyPrefix::ValidIds(database_id, object_store_id))
1203     return false;
1204   DCHECK(key.IsValid());
1205
1206   LevelDBTransaction* leveldb_transaction = transaction->transaction();
1207   int64 version = -1;
1208   bool ok = GetNewVersionNumber(
1209       leveldb_transaction, database_id, object_store_id, &version);
1210   if (!ok)
1211     return false;
1212   DCHECK_GE(version, 0);
1213   const std::string object_storedata_key =
1214       ObjectStoreDataKey::Encode(database_id, object_store_id, key);
1215
1216   std::string v;
1217   EncodeVarInt(version, &v);
1218   v.append(value);
1219
1220   leveldb_transaction->Put(object_storedata_key, &v);
1221
1222   const std::string exists_entry_key =
1223       ExistsEntryKey::Encode(database_id, object_store_id, key);
1224   std::string version_encoded;
1225   EncodeInt(version, &version_encoded);
1226   leveldb_transaction->Put(exists_entry_key, &version_encoded);
1227
1228   std::string key_encoded;
1229   EncodeIDBKey(key, &key_encoded);
1230   record_identifier->Reset(key_encoded, version);
1231   return true;
1232 }
1233
1234 bool IndexedDBBackingStore::ClearObjectStore(
1235     IndexedDBBackingStore::Transaction* transaction,
1236     int64 database_id,
1237     int64 object_store_id) {
1238   IDB_TRACE("IndexedDBBackingStore::ClearObjectStore");
1239   if (!KeyPrefix::ValidIds(database_id, object_store_id))
1240     return false;
1241   const std::string start_key =
1242       KeyPrefix(database_id, object_store_id).Encode();
1243   const std::string stop_key =
1244       KeyPrefix(database_id, object_store_id + 1).Encode();
1245
1246   DeleteRange(transaction->transaction(), start_key, stop_key);
1247   return true;
1248 }
1249
1250 bool IndexedDBBackingStore::DeleteRecord(
1251     IndexedDBBackingStore::Transaction* transaction,
1252     int64 database_id,
1253     int64 object_store_id,
1254     const RecordIdentifier& record_identifier) {
1255   IDB_TRACE("IndexedDBBackingStore::DeleteRecord");
1256   if (!KeyPrefix::ValidIds(database_id, object_store_id))
1257     return false;
1258   LevelDBTransaction* leveldb_transaction = transaction->transaction();
1259
1260   const std::string object_store_data_key = ObjectStoreDataKey::Encode(
1261       database_id, object_store_id, record_identifier.primary_key());
1262   leveldb_transaction->Remove(object_store_data_key);
1263
1264   const std::string exists_entry_key = ExistsEntryKey::Encode(
1265       database_id, object_store_id, record_identifier.primary_key());
1266   leveldb_transaction->Remove(exists_entry_key);
1267   return true;
1268 }
1269
1270 bool IndexedDBBackingStore::GetKeyGeneratorCurrentNumber(
1271     IndexedDBBackingStore::Transaction* transaction,
1272     int64 database_id,
1273     int64 object_store_id,
1274     int64* key_generator_current_number) {
1275   if (!KeyPrefix::ValidIds(database_id, object_store_id))
1276     return false;
1277   LevelDBTransaction* leveldb_transaction = transaction->transaction();
1278
1279   const std::string key_generator_current_number_key =
1280       ObjectStoreMetaDataKey::Encode(
1281           database_id,
1282           object_store_id,
1283           ObjectStoreMetaDataKey::KEY_GENERATOR_CURRENT_NUMBER);
1284
1285   *key_generator_current_number = -1;
1286   std::string data;
1287
1288   bool found = false;
1289   bool ok =
1290       leveldb_transaction->Get(key_generator_current_number_key, &data, &found);
1291   if (!ok) {
1292     INTERNAL_READ_ERROR(GET_KEY_GENERATOR_CURRENT_NUMBER);
1293     return false;
1294   }
1295   if (found && !data.empty()) {
1296     StringPiece slice(data);
1297     if (!DecodeInt(&slice, key_generator_current_number) || !slice.empty()) {
1298       INTERNAL_READ_ERROR(GET_KEY_GENERATOR_CURRENT_NUMBER);
1299       return false;
1300     }
1301     return true;
1302   }
1303
1304   // Previously, the key generator state was not stored explicitly
1305   // but derived from the maximum numeric key present in existing
1306   // data. This violates the spec as the data may be cleared but the
1307   // key generator state must be preserved.
1308   // TODO(jsbell): Fix this for all stores on database open?
1309   const std::string start_key =
1310       ObjectStoreDataKey::Encode(database_id, object_store_id, MinIDBKey());
1311   const std::string stop_key =
1312       ObjectStoreDataKey::Encode(database_id, object_store_id, MaxIDBKey());
1313
1314   scoped_ptr<LevelDBIterator> it = leveldb_transaction->CreateIterator();
1315   int64 max_numeric_key = 0;
1316
1317   for (it->Seek(start_key);
1318        it->IsValid() && CompareKeys(it->Key(), stop_key) < 0;
1319        it->Next()) {
1320     StringPiece slice(it->Key());
1321     ObjectStoreDataKey data_key;
1322     if (!ObjectStoreDataKey::Decode(&slice, &data_key)) {
1323       INTERNAL_READ_ERROR(GET_KEY_GENERATOR_CURRENT_NUMBER);
1324       return false;
1325     }
1326     scoped_ptr<IndexedDBKey> user_key = data_key.user_key();
1327     if (user_key->type() == WebKit::WebIDBKeyTypeNumber) {
1328       int64 n = static_cast<int64>(user_key->number());
1329       if (n > max_numeric_key)
1330         max_numeric_key = n;
1331     }
1332   }
1333
1334   *key_generator_current_number = max_numeric_key + 1;
1335   return true;
1336 }
1337
1338 bool IndexedDBBackingStore::MaybeUpdateKeyGeneratorCurrentNumber(
1339     IndexedDBBackingStore::Transaction* transaction,
1340     int64 database_id,
1341     int64 object_store_id,
1342     int64 new_number,
1343     bool check_current) {
1344   if (!KeyPrefix::ValidIds(database_id, object_store_id))
1345     return false;
1346
1347   if (check_current) {
1348     int64 current_number;
1349     bool ok = GetKeyGeneratorCurrentNumber(
1350         transaction, database_id, object_store_id, &current_number);
1351     if (!ok)
1352       return false;
1353     if (new_number <= current_number)
1354       return true;
1355   }
1356
1357   const std::string key_generator_current_number_key =
1358       ObjectStoreMetaDataKey::Encode(
1359           database_id,
1360           object_store_id,
1361           ObjectStoreMetaDataKey::KEY_GENERATOR_CURRENT_NUMBER);
1362   PutInt(
1363       transaction->transaction(), key_generator_current_number_key, new_number);
1364   return true;
1365 }
1366
1367 bool IndexedDBBackingStore::KeyExistsInObjectStore(
1368     IndexedDBBackingStore::Transaction* transaction,
1369     int64 database_id,
1370     int64 object_store_id,
1371     const IndexedDBKey& key,
1372     RecordIdentifier* found_record_identifier,
1373     bool* found) {
1374   IDB_TRACE("IndexedDBBackingStore::KeyExistsInObjectStore");
1375   if (!KeyPrefix::ValidIds(database_id, object_store_id))
1376     return false;
1377   *found = false;
1378   const std::string leveldb_key =
1379       ObjectStoreDataKey::Encode(database_id, object_store_id, key);
1380   std::string data;
1381
1382   bool ok = transaction->transaction()->Get(leveldb_key, &data, found);
1383   if (!ok) {
1384     INTERNAL_READ_ERROR(KEY_EXISTS_IN_OBJECT_STORE);
1385     return false;
1386   }
1387   if (!*found)
1388     return true;
1389   if (!data.size()) {
1390     INTERNAL_READ_ERROR(KEY_EXISTS_IN_OBJECT_STORE);
1391     return false;
1392   }
1393
1394   int64 version;
1395   StringPiece slice(data);
1396   if (!DecodeVarInt(&slice, &version))
1397     return false;
1398
1399   std::string encoded_key;
1400   EncodeIDBKey(key, &encoded_key);
1401   found_record_identifier->Reset(encoded_key, version);
1402   return true;
1403 }
1404
1405 static bool CheckIndexAndMetaDataKey(const LevelDBIterator* it,
1406                                      const std::string& stop_key,
1407                                      int64 index_id,
1408                                      unsigned char meta_data_type) {
1409   if (!it->IsValid() || CompareKeys(it->Key(), stop_key) >= 0)
1410     return false;
1411
1412   StringPiece slice(it->Key());
1413   IndexMetaDataKey meta_data_key;
1414   bool ok = IndexMetaDataKey::Decode(&slice, &meta_data_key);
1415   DCHECK(ok);
1416   if (meta_data_key.IndexId() != index_id)
1417     return false;
1418   if (meta_data_key.meta_data_type() != meta_data_type)
1419     return false;
1420   return true;
1421 }
1422
1423 // TODO(jsbell): This should do some error handling rather than plowing ahead
1424 // when bad data is encountered.
1425 bool IndexedDBBackingStore::GetIndexes(
1426     int64 database_id,
1427     int64 object_store_id,
1428     IndexedDBObjectStoreMetadata::IndexMap* indexes) {
1429   IDB_TRACE("IndexedDBBackingStore::GetIndexes");
1430   if (!KeyPrefix::ValidIds(database_id, object_store_id))
1431     return false;
1432   const std::string start_key =
1433       IndexMetaDataKey::Encode(database_id, object_store_id, 0, 0);
1434   const std::string stop_key =
1435       IndexMetaDataKey::Encode(database_id, object_store_id + 1, 0, 0);
1436
1437   DCHECK(indexes->empty());
1438
1439   scoped_ptr<LevelDBIterator> it = db_->CreateIterator();
1440   it->Seek(start_key);
1441   while (it->IsValid() && CompareKeys(it->Key(), stop_key) < 0) {
1442     StringPiece slice(it->Key());
1443     IndexMetaDataKey meta_data_key;
1444     bool ok = IndexMetaDataKey::Decode(&slice, &meta_data_key);
1445     DCHECK(ok);
1446     if (meta_data_key.meta_data_type() != IndexMetaDataKey::NAME) {
1447       INTERNAL_CONSISTENCY_ERROR(GET_INDEXES);
1448       // Possible stale metadata due to http://webkit.org/b/85557 but don't fail
1449       // the load.
1450       it->Next();
1451       continue;
1452     }
1453
1454     // TODO(jsbell): Do this by direct key lookup rather than iteration, to
1455     // simplify.
1456     int64 index_id = meta_data_key.IndexId();
1457     string16 index_name;
1458     {
1459       StringPiece slice(it->Value());
1460       if (!DecodeString(&slice, &index_name) || !slice.empty())
1461         INTERNAL_CONSISTENCY_ERROR(GET_INDEXES);
1462     }
1463
1464     it->Next();  // unique flag
1465     if (!CheckIndexAndMetaDataKey(
1466              it.get(), stop_key, index_id, IndexMetaDataKey::UNIQUE)) {
1467       INTERNAL_CONSISTENCY_ERROR(GET_INDEXES);
1468       break;
1469     }
1470     bool index_unique;
1471     {
1472       StringPiece slice(it->Value());
1473       if (!DecodeBool(&slice, &index_unique) || !slice.empty())
1474         INTERNAL_CONSISTENCY_ERROR(GET_INDEXES);
1475     }
1476
1477     it->Next();  // key_path
1478     if (!CheckIndexAndMetaDataKey(
1479              it.get(), stop_key, index_id, IndexMetaDataKey::KEY_PATH)) {
1480       INTERNAL_CONSISTENCY_ERROR(GET_INDEXES);
1481       break;
1482     }
1483     IndexedDBKeyPath key_path;
1484     {
1485       StringPiece slice(it->Value());
1486       if (!DecodeIDBKeyPath(&slice, &key_path) || !slice.empty())
1487         INTERNAL_CONSISTENCY_ERROR(GET_INDEXES);
1488     }
1489
1490     it->Next();  // [optional] multi_entry flag
1491     bool index_multi_entry = false;
1492     if (CheckIndexAndMetaDataKey(
1493             it.get(), stop_key, index_id, IndexMetaDataKey::MULTI_ENTRY)) {
1494       StringPiece slice(it->Value());
1495       if (!DecodeBool(&slice, &index_multi_entry) || !slice.empty())
1496         INTERNAL_CONSISTENCY_ERROR(GET_INDEXES);
1497
1498       it->Next();
1499     }
1500
1501     (*indexes)[index_id] = IndexedDBIndexMetadata(
1502         index_name, index_id, key_path, index_unique, index_multi_entry);
1503   }
1504   return true;
1505 }
1506
1507 WARN_UNUSED_RESULT static bool SetMaxIndexId(LevelDBTransaction* transaction,
1508                                              int64 database_id,
1509                                              int64 object_store_id,
1510                                              int64 index_id) {
1511   int64 max_index_id = -1;
1512   const std::string max_index_id_key = ObjectStoreMetaDataKey::Encode(
1513       database_id, object_store_id, ObjectStoreMetaDataKey::MAX_INDEX_ID);
1514   bool found = false;
1515   bool ok = GetInt(transaction, max_index_id_key, &max_index_id, &found);
1516   if (!ok) {
1517     INTERNAL_READ_ERROR(SET_MAX_INDEX_ID);
1518     return false;
1519   }
1520   if (!found)
1521     max_index_id = kMinimumIndexId;
1522
1523   if (index_id <= max_index_id) {
1524     INTERNAL_CONSISTENCY_ERROR(SET_MAX_INDEX_ID);
1525     return false;
1526   }
1527
1528   PutInt(transaction, max_index_id_key, index_id);
1529   return true;
1530 }
1531
1532 bool IndexedDBBackingStore::CreateIndex(
1533     IndexedDBBackingStore::Transaction* transaction,
1534     int64 database_id,
1535     int64 object_store_id,
1536     int64 index_id,
1537     const string16& name,
1538     const IndexedDBKeyPath& key_path,
1539     bool is_unique,
1540     bool is_multi_entry) {
1541   IDB_TRACE("IndexedDBBackingStore::CreateIndex");
1542   if (!KeyPrefix::ValidIds(database_id, object_store_id, index_id))
1543     return false;
1544   LevelDBTransaction* leveldb_transaction = transaction->transaction();
1545   if (!SetMaxIndexId(
1546            leveldb_transaction, database_id, object_store_id, index_id))
1547     return false;
1548
1549   const std::string name_key = IndexMetaDataKey::Encode(
1550       database_id, object_store_id, index_id, IndexMetaDataKey::NAME);
1551   const std::string unique_key = IndexMetaDataKey::Encode(
1552       database_id, object_store_id, index_id, IndexMetaDataKey::UNIQUE);
1553   const std::string key_path_key = IndexMetaDataKey::Encode(
1554       database_id, object_store_id, index_id, IndexMetaDataKey::KEY_PATH);
1555   const std::string multi_entry_key = IndexMetaDataKey::Encode(
1556       database_id, object_store_id, index_id, IndexMetaDataKey::MULTI_ENTRY);
1557
1558   PutString(leveldb_transaction, name_key, name);
1559   PutBool(leveldb_transaction, unique_key, is_unique);
1560   PutIDBKeyPath(leveldb_transaction, key_path_key, key_path);
1561   PutBool(leveldb_transaction, multi_entry_key, is_multi_entry);
1562   return true;
1563 }
1564
1565 bool IndexedDBBackingStore::DeleteIndex(
1566     IndexedDBBackingStore::Transaction* transaction,
1567     int64 database_id,
1568     int64 object_store_id,
1569     int64 index_id) {
1570   IDB_TRACE("IndexedDBBackingStore::DeleteIndex");
1571   if (!KeyPrefix::ValidIds(database_id, object_store_id, index_id))
1572     return false;
1573   LevelDBTransaction* leveldb_transaction = transaction->transaction();
1574
1575   const std::string index_meta_data_start =
1576       IndexMetaDataKey::Encode(database_id, object_store_id, index_id, 0);
1577   const std::string index_meta_data_end =
1578       IndexMetaDataKey::EncodeMaxKey(database_id, object_store_id, index_id);
1579   DeleteRange(leveldb_transaction, index_meta_data_start, index_meta_data_end);
1580
1581   const std::string index_data_start =
1582       IndexDataKey::EncodeMinKey(database_id, object_store_id, index_id);
1583   const std::string index_data_end =
1584       IndexDataKey::EncodeMaxKey(database_id, object_store_id, index_id);
1585   DeleteRange(leveldb_transaction, index_data_start, index_data_end);
1586   return true;
1587 }
1588
1589 bool IndexedDBBackingStore::PutIndexDataForRecord(
1590     IndexedDBBackingStore::Transaction* transaction,
1591     int64 database_id,
1592     int64 object_store_id,
1593     int64 index_id,
1594     const IndexedDBKey& key,
1595     const RecordIdentifier& record_identifier) {
1596   IDB_TRACE("IndexedDBBackingStore::PutIndexDataForRecord");
1597   DCHECK(key.IsValid());
1598   if (!KeyPrefix::ValidIds(database_id, object_store_id, index_id))
1599     return false;
1600
1601   std::string encoded_key;
1602   EncodeIDBKey(key, &encoded_key);
1603
1604   const std::string index_data_key =
1605       IndexDataKey::Encode(database_id,
1606                            object_store_id,
1607                            index_id,
1608                            encoded_key,
1609                            record_identifier.primary_key(),
1610                            0);
1611
1612   std::string data;
1613   EncodeVarInt(record_identifier.version(), &data);
1614   data.append(record_identifier.primary_key());
1615
1616   transaction->transaction()->Put(index_data_key, &data);
1617   return true;
1618 }
1619
1620 static bool FindGreatestKeyLessThanOrEqual(LevelDBTransaction* transaction,
1621                                            const std::string& target,
1622                                            std::string* found_key) {
1623   scoped_ptr<LevelDBIterator> it = transaction->CreateIterator();
1624   it->Seek(target);
1625
1626   if (!it->IsValid()) {
1627     it->SeekToLast();
1628     if (!it->IsValid())
1629       return false;
1630   }
1631
1632   while (CompareIndexKeys(it->Key(), target) > 0) {
1633     it->Prev();
1634     if (!it->IsValid())
1635       return false;
1636   }
1637
1638   do {
1639     *found_key = it->Key().as_string();
1640
1641     // There can be several index keys that compare equal. We want the last one.
1642     it->Next();
1643   } while (it->IsValid() && !CompareIndexKeys(it->Key(), target));
1644
1645   return true;
1646 }
1647
1648 static bool VersionExists(LevelDBTransaction* transaction,
1649                           int64 database_id,
1650                           int64 object_store_id,
1651                           int64 version,
1652                           const std::string& encoded_primary_key,
1653                           bool* exists) {
1654   const std::string key =
1655       ExistsEntryKey::Encode(database_id, object_store_id, encoded_primary_key);
1656   std::string data;
1657
1658   bool ok = transaction->Get(key, &data, exists);
1659   if (!ok) {
1660     INTERNAL_READ_ERROR(VERSION_EXISTS);
1661     return false;
1662   }
1663   if (!*exists)
1664     return true;
1665
1666   StringPiece slice(data);
1667   int64 decoded;
1668   if (!DecodeInt(&slice, &decoded) || !slice.empty())
1669     return false;
1670   *exists = (decoded == version);
1671   return true;
1672 }
1673
1674 bool IndexedDBBackingStore::FindKeyInIndex(
1675     IndexedDBBackingStore::Transaction* transaction,
1676     int64 database_id,
1677     int64 object_store_id,
1678     int64 index_id,
1679     const IndexedDBKey& key,
1680     std::string* found_encoded_primary_key,
1681     bool* found) {
1682   IDB_TRACE("IndexedDBBackingStore::FindKeyInIndex");
1683   DCHECK(KeyPrefix::ValidIds(database_id, object_store_id, index_id));
1684
1685   DCHECK(found_encoded_primary_key->empty());
1686   *found = false;
1687
1688   LevelDBTransaction* leveldb_transaction = transaction->transaction();
1689   const std::string leveldb_key =
1690       IndexDataKey::Encode(database_id, object_store_id, index_id, key);
1691   scoped_ptr<LevelDBIterator> it = leveldb_transaction->CreateIterator();
1692   it->Seek(leveldb_key);
1693
1694   for (;;) {
1695     if (!it->IsValid())
1696       return true;
1697     if (CompareIndexKeys(it->Key(), leveldb_key) > 0)
1698       return true;
1699
1700     StringPiece slice(it->Value());
1701
1702     int64 version;
1703     if (!DecodeVarInt(&slice, &version)) {
1704       INTERNAL_READ_ERROR(FIND_KEY_IN_INDEX);
1705       return false;
1706     }
1707     *found_encoded_primary_key = slice.as_string();
1708
1709     bool exists = false;
1710     bool ok = VersionExists(leveldb_transaction,
1711                             database_id,
1712                             object_store_id,
1713                             version,
1714                             *found_encoded_primary_key,
1715                             &exists);
1716     if (!ok)
1717       return false;
1718     if (!exists) {
1719       // Delete stale index data entry and continue.
1720       leveldb_transaction->Remove(it->Key());
1721       it->Next();
1722       continue;
1723     }
1724     *found = true;
1725     return true;
1726   }
1727 }
1728
1729 bool IndexedDBBackingStore::GetPrimaryKeyViaIndex(
1730     IndexedDBBackingStore::Transaction* transaction,
1731     int64 database_id,
1732     int64 object_store_id,
1733     int64 index_id,
1734     const IndexedDBKey& key,
1735     scoped_ptr<IndexedDBKey>* primary_key) {
1736   IDB_TRACE("IndexedDBBackingStore::GetPrimaryKeyViaIndex");
1737   if (!KeyPrefix::ValidIds(database_id, object_store_id, index_id))
1738     return false;
1739
1740   bool found = false;
1741   std::string found_encoded_primary_key;
1742   bool ok = FindKeyInIndex(transaction,
1743                            database_id,
1744                            object_store_id,
1745                            index_id,
1746                            key,
1747                            &found_encoded_primary_key,
1748                            &found);
1749   if (!ok) {
1750     INTERNAL_READ_ERROR(GET_PRIMARY_KEY_VIA_INDEX);
1751     return false;
1752   }
1753   if (!found)
1754     return true;
1755   if (!found_encoded_primary_key.size()) {
1756     INTERNAL_READ_ERROR(GET_PRIMARY_KEY_VIA_INDEX);
1757     return false;
1758   }
1759
1760   StringPiece slice(found_encoded_primary_key);
1761   return DecodeIDBKey(&slice, primary_key) && slice.empty();
1762 }
1763
1764 bool IndexedDBBackingStore::KeyExistsInIndex(
1765     IndexedDBBackingStore::Transaction* transaction,
1766     int64 database_id,
1767     int64 object_store_id,
1768     int64 index_id,
1769     const IndexedDBKey& index_key,
1770     scoped_ptr<IndexedDBKey>* found_primary_key,
1771     bool* exists) {
1772   IDB_TRACE("IndexedDBBackingStore::KeyExistsInIndex");
1773   if (!KeyPrefix::ValidIds(database_id, object_store_id, index_id))
1774     return false;
1775
1776   *exists = false;
1777   std::string found_encoded_primary_key;
1778   bool ok = FindKeyInIndex(transaction,
1779                            database_id,
1780                            object_store_id,
1781                            index_id,
1782                            index_key,
1783                            &found_encoded_primary_key,
1784                            exists);
1785   if (!ok) {
1786     INTERNAL_READ_ERROR(KEY_EXISTS_IN_INDEX);
1787     return false;
1788   }
1789   if (!*exists)
1790     return true;
1791   if (found_encoded_primary_key.empty()) {
1792     INTERNAL_READ_ERROR(KEY_EXISTS_IN_INDEX);
1793     return false;
1794   }
1795
1796   StringPiece slice(found_encoded_primary_key);
1797   return DecodeIDBKey(&slice, found_primary_key) && slice.empty();
1798 }
1799
1800 IndexedDBBackingStore::Cursor::Cursor(
1801     const IndexedDBBackingStore::Cursor* other)
1802     : transaction_(other->transaction_),
1803       cursor_options_(other->cursor_options_),
1804       current_key_(new IndexedDBKey(*other->current_key_)) {
1805   if (other->iterator_) {
1806     iterator_ = transaction_->CreateIterator();
1807
1808     if (other->iterator_->IsValid()) {
1809       iterator_->Seek(other->iterator_->Key());
1810       DCHECK(iterator_->IsValid());
1811     }
1812   }
1813 }
1814
1815 IndexedDBBackingStore::Cursor::Cursor(LevelDBTransaction* transaction,
1816                                       const CursorOptions& cursor_options)
1817     : transaction_(transaction), cursor_options_(cursor_options) {}
1818 IndexedDBBackingStore::Cursor::~Cursor() {}
1819
1820 bool IndexedDBBackingStore::Cursor::FirstSeek() {
1821   iterator_ = transaction_->CreateIterator();
1822   if (cursor_options_.forward)
1823     iterator_->Seek(cursor_options_.low_key);
1824   else
1825     iterator_->Seek(cursor_options_.high_key);
1826
1827   return Continue(0, READY);
1828 }
1829
1830 bool IndexedDBBackingStore::Cursor::Advance(uint32 count) {
1831   while (count--) {
1832     if (!Continue())
1833       return false;
1834   }
1835   return true;
1836 }
1837
1838 bool IndexedDBBackingStore::Cursor::Continue(const IndexedDBKey* key,
1839                                              IteratorState next_state) {
1840   // TODO(alecflett): avoid a copy here?
1841   IndexedDBKey previous_key = current_key_ ? *current_key_ : IndexedDBKey();
1842
1843   bool first_iteration = true;
1844
1845   // When iterating with PrevNoDuplicate, spec requires that the
1846   // value we yield for each key is the first duplicate in forwards
1847   // order.
1848   IndexedDBKey last_duplicate_key;
1849
1850   bool forward = cursor_options_.forward;
1851
1852   for (;;) {
1853     if (next_state == SEEK) {
1854       // TODO(jsbell): Optimize seeking for reverse cursors as well.
1855       if (first_iteration && key && key->IsValid() && forward) {
1856         iterator_->Seek(EncodeKey(*key));
1857         first_iteration = false;
1858       } else if (forward) {
1859         iterator_->Next();
1860       } else {
1861         iterator_->Prev();
1862       }
1863     } else {
1864       next_state = SEEK;  // for subsequent iterations
1865     }
1866
1867     if (!iterator_->IsValid()) {
1868       if (!forward && last_duplicate_key.IsValid()) {
1869         // We need to walk forward because we hit the end of
1870         // the data.
1871         forward = true;
1872         continue;
1873       }
1874
1875       return false;
1876     }
1877
1878     if (IsPastBounds()) {
1879       if (!forward && last_duplicate_key.IsValid()) {
1880         // We need to walk forward because now we're beyond the
1881         // bounds defined by the cursor.
1882         forward = true;
1883         continue;
1884       }
1885
1886       return false;
1887     }
1888
1889     if (!HaveEnteredRange())
1890       continue;
1891
1892     // The row may not load because there's a stale entry in the
1893     // index. This is not fatal.
1894     if (!LoadCurrentRow())
1895       continue;
1896
1897     if (key && key->IsValid()) {
1898       if (forward) {
1899         if (current_key_->IsLessThan(*key))
1900           continue;
1901       } else {
1902         if (key->IsLessThan(*current_key_))
1903           continue;
1904       }
1905     }
1906
1907     if (cursor_options_.unique) {
1908       if (previous_key.IsValid() && current_key_->IsEqual(previous_key)) {
1909         // We should never be able to walk forward all the way
1910         // to the previous key.
1911         DCHECK(!last_duplicate_key.IsValid());
1912         continue;
1913       }
1914
1915       if (!forward) {
1916         if (!last_duplicate_key.IsValid()) {
1917           last_duplicate_key = *current_key_;
1918           continue;
1919         }
1920
1921         // We need to walk forward because we hit the boundary
1922         // between key ranges.
1923         if (!last_duplicate_key.IsEqual(*current_key_)) {
1924           forward = true;
1925           continue;
1926         }
1927
1928         continue;
1929       }
1930     }
1931     break;
1932   }
1933
1934   DCHECK(!last_duplicate_key.IsValid() ||
1935          (forward && last_duplicate_key.IsEqual(*current_key_)));
1936   return true;
1937 }
1938
1939 bool IndexedDBBackingStore::Cursor::HaveEnteredRange() const {
1940   if (cursor_options_.forward) {
1941     int compare = CompareIndexKeys(iterator_->Key(), cursor_options_.low_key);
1942     if (cursor_options_.low_open) {
1943       return compare > 0;
1944     }
1945     return compare >= 0;
1946   }
1947   int compare = CompareIndexKeys(iterator_->Key(), cursor_options_.high_key);
1948   if (cursor_options_.high_open) {
1949     return compare < 0;
1950   }
1951   return compare <= 0;
1952 }
1953
1954 bool IndexedDBBackingStore::Cursor::IsPastBounds() const {
1955   if (cursor_options_.forward) {
1956     int compare = CompareIndexKeys(iterator_->Key(), cursor_options_.high_key);
1957     if (cursor_options_.high_open) {
1958       return compare >= 0;
1959     }
1960     return compare > 0;
1961   }
1962   int compare = CompareIndexKeys(iterator_->Key(), cursor_options_.low_key);
1963   if (cursor_options_.low_open) {
1964     return compare <= 0;
1965   }
1966   return compare < 0;
1967 }
1968
1969 const IndexedDBKey& IndexedDBBackingStore::Cursor::primary_key() const {
1970   return *current_key_;
1971 }
1972
1973 const IndexedDBBackingStore::RecordIdentifier&
1974 IndexedDBBackingStore::Cursor::record_identifier() const {
1975   return record_identifier_;
1976 }
1977
1978 class ObjectStoreKeyCursorImpl : public IndexedDBBackingStore::Cursor {
1979  public:
1980   ObjectStoreKeyCursorImpl(
1981       LevelDBTransaction* transaction,
1982       const IndexedDBBackingStore::Cursor::CursorOptions& cursor_options)
1983       : IndexedDBBackingStore::Cursor(transaction, cursor_options) {}
1984
1985   virtual Cursor* Clone() OVERRIDE {
1986     return new ObjectStoreKeyCursorImpl(this);
1987   }
1988
1989   // IndexedDBBackingStore::Cursor
1990   virtual std::string* Value() OVERRIDE {
1991     NOTREACHED();
1992     return NULL;
1993   }
1994   virtual bool LoadCurrentRow() OVERRIDE;
1995
1996  protected:
1997   virtual std::string EncodeKey(const IndexedDBKey& key) OVERRIDE {
1998     return ObjectStoreDataKey::Encode(
1999         cursor_options_.database_id, cursor_options_.object_store_id, key);
2000   }
2001
2002  private:
2003   explicit ObjectStoreKeyCursorImpl(const ObjectStoreKeyCursorImpl* other)
2004       : IndexedDBBackingStore::Cursor(other) {}
2005 };
2006
2007 bool ObjectStoreKeyCursorImpl::LoadCurrentRow() {
2008   StringPiece slice(iterator_->Key());
2009   ObjectStoreDataKey object_store_data_key;
2010   if (!ObjectStoreDataKey::Decode(&slice, &object_store_data_key)) {
2011     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2012     return false;
2013   }
2014
2015   current_key_ = object_store_data_key.user_key();
2016
2017   int64 version;
2018   slice = StringPiece(iterator_->Value());
2019   if (!DecodeVarInt(&slice, &version)) {
2020     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2021     return false;
2022   }
2023
2024   // TODO(jsbell): This re-encodes what was just decoded; try and optimize.
2025   std::string encoded_key;
2026   EncodeIDBKey(*current_key_, &encoded_key);
2027   record_identifier_.Reset(encoded_key, version);
2028
2029   return true;
2030 }
2031
2032 class ObjectStoreCursorImpl : public IndexedDBBackingStore::Cursor {
2033  public:
2034   ObjectStoreCursorImpl(
2035       LevelDBTransaction* transaction,
2036       const IndexedDBBackingStore::Cursor::CursorOptions& cursor_options)
2037       : IndexedDBBackingStore::Cursor(transaction, cursor_options) {}
2038
2039   virtual Cursor* Clone() OVERRIDE { return new ObjectStoreCursorImpl(this); }
2040
2041   // IndexedDBBackingStore::Cursor
2042   virtual std::string* Value() OVERRIDE { return &current_value_; }
2043   virtual bool LoadCurrentRow() OVERRIDE;
2044
2045  protected:
2046   virtual std::string EncodeKey(const IndexedDBKey& key) OVERRIDE {
2047     return ObjectStoreDataKey::Encode(
2048         cursor_options_.database_id, cursor_options_.object_store_id, key);
2049   }
2050
2051  private:
2052   explicit ObjectStoreCursorImpl(const ObjectStoreCursorImpl* other)
2053       : IndexedDBBackingStore::Cursor(other),
2054         current_value_(other->current_value_) {}
2055
2056   std::string current_value_;
2057 };
2058
2059 bool ObjectStoreCursorImpl::LoadCurrentRow() {
2060   StringPiece slice(iterator_->Key());
2061   ObjectStoreDataKey object_store_data_key;
2062   if (!ObjectStoreDataKey::Decode(&slice, &object_store_data_key)) {
2063     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2064     return false;
2065   }
2066
2067   current_key_ = object_store_data_key.user_key();
2068
2069   int64 version;
2070   slice = StringPiece(iterator_->Value());
2071   if (!DecodeVarInt(&slice, &version)) {
2072     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2073     return false;
2074   }
2075
2076   // TODO(jsbell): This re-encodes what was just decoded; try and optimize.
2077   std::string encoded_key;
2078   EncodeIDBKey(*current_key_, &encoded_key);
2079   record_identifier_.Reset(encoded_key, version);
2080
2081   current_value_ = slice.as_string();
2082   return true;
2083 }
2084
2085 class IndexKeyCursorImpl : public IndexedDBBackingStore::Cursor {
2086  public:
2087   IndexKeyCursorImpl(
2088       LevelDBTransaction* transaction,
2089       const IndexedDBBackingStore::Cursor::CursorOptions& cursor_options)
2090       : IndexedDBBackingStore::Cursor(transaction, cursor_options) {}
2091
2092   virtual Cursor* Clone() OVERRIDE { return new IndexKeyCursorImpl(this); }
2093
2094   // IndexedDBBackingStore::Cursor
2095   virtual std::string* Value() OVERRIDE {
2096     NOTREACHED();
2097     return NULL;
2098   }
2099   virtual const IndexedDBKey& primary_key() const OVERRIDE {
2100     return *primary_key_;
2101   }
2102   virtual const IndexedDBBackingStore::RecordIdentifier& RecordIdentifier()
2103       const {
2104     NOTREACHED();
2105     return record_identifier_;
2106   }
2107   virtual bool LoadCurrentRow() OVERRIDE;
2108
2109  protected:
2110   virtual std::string EncodeKey(const IndexedDBKey& key) OVERRIDE {
2111     return IndexDataKey::Encode(cursor_options_.database_id,
2112                                 cursor_options_.object_store_id,
2113                                 cursor_options_.index_id,
2114                                 key);
2115   }
2116
2117  private:
2118   explicit IndexKeyCursorImpl(const IndexKeyCursorImpl* other)
2119       : IndexedDBBackingStore::Cursor(other),
2120         primary_key_(new IndexedDBKey(*other->primary_key_)) {}
2121
2122   scoped_ptr<IndexedDBKey> primary_key_;
2123 };
2124
2125 bool IndexKeyCursorImpl::LoadCurrentRow() {
2126   StringPiece slice(iterator_->Key());
2127   IndexDataKey index_data_key;
2128   if (!IndexDataKey::Decode(&slice, &index_data_key)) {
2129     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2130     return false;
2131   }
2132
2133   current_key_ = index_data_key.user_key();
2134   DCHECK(current_key_);
2135
2136   slice = StringPiece(iterator_->Value());
2137   int64 index_data_version;
2138   if (!DecodeVarInt(&slice, &index_data_version)) {
2139     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2140     return false;
2141   }
2142
2143   if (!DecodeIDBKey(&slice, &primary_key_) || !slice.empty()) {
2144     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2145     return false;
2146   }
2147
2148   std::string primary_leveldb_key =
2149       ObjectStoreDataKey::Encode(index_data_key.DatabaseId(),
2150                                  index_data_key.ObjectStoreId(),
2151                                  *primary_key_);
2152
2153   std::string result;
2154   bool found = false;
2155   bool ok = transaction_->Get(primary_leveldb_key, &result, &found);
2156   if (!ok) {
2157     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2158     return false;
2159   }
2160   if (!found) {
2161     transaction_->Remove(iterator_->Key());
2162     return false;
2163   }
2164   if (!result.size()) {
2165     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2166     return false;
2167   }
2168
2169   int64 object_store_data_version;
2170   slice = StringPiece(result);
2171   if (!DecodeVarInt(&slice, &object_store_data_version)) {
2172     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2173     return false;
2174   }
2175
2176   if (object_store_data_version != index_data_version) {
2177     transaction_->Remove(iterator_->Key());
2178     return false;
2179   }
2180
2181   return true;
2182 }
2183
2184 class IndexCursorImpl : public IndexedDBBackingStore::Cursor {
2185  public:
2186   IndexCursorImpl(
2187       LevelDBTransaction* transaction,
2188       const IndexedDBBackingStore::Cursor::CursorOptions& cursor_options)
2189       : IndexedDBBackingStore::Cursor(transaction, cursor_options) {}
2190
2191   virtual Cursor* Clone() OVERRIDE { return new IndexCursorImpl(this); }
2192
2193   // IndexedDBBackingStore::Cursor
2194   virtual std::string* Value() OVERRIDE { return &current_value_; }
2195   virtual const IndexedDBKey& primary_key() const OVERRIDE {
2196     return *primary_key_;
2197   }
2198   virtual const IndexedDBBackingStore::RecordIdentifier& RecordIdentifier()
2199       const {
2200     NOTREACHED();
2201     return record_identifier_;
2202   }
2203   virtual bool LoadCurrentRow() OVERRIDE;
2204
2205  protected:
2206   virtual std::string EncodeKey(const IndexedDBKey& key) OVERRIDE {
2207     return IndexDataKey::Encode(cursor_options_.database_id,
2208                                 cursor_options_.object_store_id,
2209                                 cursor_options_.index_id,
2210                                 key);
2211   }
2212
2213  private:
2214   explicit IndexCursorImpl(const IndexCursorImpl* other)
2215       : IndexedDBBackingStore::Cursor(other),
2216         primary_key_(new IndexedDBKey(*other->primary_key_)),
2217         current_value_(other->current_value_),
2218         primary_leveldb_key_(other->primary_leveldb_key_) {}
2219
2220   scoped_ptr<IndexedDBKey> primary_key_;
2221   std::string current_value_;
2222   std::string primary_leveldb_key_;
2223 };
2224
2225 bool IndexCursorImpl::LoadCurrentRow() {
2226   StringPiece slice(iterator_->Key());
2227   IndexDataKey index_data_key;
2228   if (!IndexDataKey::Decode(&slice, &index_data_key)) {
2229     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2230     return false;
2231   }
2232
2233   current_key_ = index_data_key.user_key();
2234   DCHECK(current_key_);
2235
2236   slice = StringPiece(iterator_->Value());
2237   int64 index_data_version;
2238   if (!DecodeVarInt(&slice, &index_data_version)) {
2239     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2240     return false;
2241   }
2242   if (!DecodeIDBKey(&slice, &primary_key_)) {
2243     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2244     return false;
2245   }
2246
2247   primary_leveldb_key_ =
2248       ObjectStoreDataKey::Encode(index_data_key.DatabaseId(),
2249                                  index_data_key.ObjectStoreId(),
2250                                  *primary_key_);
2251
2252   std::string result;
2253   bool found = false;
2254   bool ok = transaction_->Get(primary_leveldb_key_, &result, &found);
2255   if (!ok) {
2256     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2257     return false;
2258   }
2259   if (!found) {
2260     transaction_->Remove(iterator_->Key());
2261     return false;
2262   }
2263   if (!result.size()) {
2264     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2265     return false;
2266   }
2267
2268   int64 object_store_data_version;
2269   slice = StringPiece(result);
2270   if (!DecodeVarInt(&slice, &object_store_data_version)) {
2271     INTERNAL_READ_ERROR(LOAD_CURRENT_ROW);
2272     return false;
2273   }
2274
2275   if (object_store_data_version != index_data_version) {
2276     transaction_->Remove(iterator_->Key());
2277     return false;
2278   }
2279
2280   current_value_ = slice.as_string();
2281   return true;
2282 }
2283
2284 bool ObjectStoreCursorOptions(
2285     LevelDBTransaction* transaction,
2286     int64 database_id,
2287     int64 object_store_id,
2288     const IndexedDBKeyRange& range,
2289     indexed_db::CursorDirection direction,
2290     IndexedDBBackingStore::Cursor::CursorOptions* cursor_options) {
2291   cursor_options->database_id = database_id;
2292   cursor_options->object_store_id = object_store_id;
2293
2294   bool lower_bound = range.lower().IsValid();
2295   bool upper_bound = range.upper().IsValid();
2296   cursor_options->forward =
2297       (direction == indexed_db::CURSOR_NEXT_NO_DUPLICATE ||
2298        direction == indexed_db::CURSOR_NEXT);
2299   cursor_options->unique = (direction == indexed_db::CURSOR_NEXT_NO_DUPLICATE ||
2300                             direction == indexed_db::CURSOR_PREV_NO_DUPLICATE);
2301
2302   if (!lower_bound) {
2303     cursor_options->low_key =
2304         ObjectStoreDataKey::Encode(database_id, object_store_id, MinIDBKey());
2305     cursor_options->low_open = true;  // Not included.
2306   } else {
2307     cursor_options->low_key =
2308         ObjectStoreDataKey::Encode(database_id, object_store_id, range.lower());
2309     cursor_options->low_open = range.lowerOpen();
2310   }
2311
2312   if (!upper_bound) {
2313     cursor_options->high_key =
2314         ObjectStoreDataKey::Encode(database_id, object_store_id, MaxIDBKey());
2315
2316     if (cursor_options->forward) {
2317       cursor_options->high_open = true;  // Not included.
2318     } else {
2319       // We need a key that exists.
2320       if (!FindGreatestKeyLessThanOrEqual(transaction,
2321                                           cursor_options->high_key,
2322                                           &cursor_options->high_key))
2323         return false;
2324       cursor_options->high_open = false;
2325     }
2326   } else {
2327     cursor_options->high_key =
2328         ObjectStoreDataKey::Encode(database_id, object_store_id, range.upper());
2329     cursor_options->high_open = range.upperOpen();
2330
2331     if (!cursor_options->forward) {
2332       // For reverse cursors, we need a key that exists.
2333       std::string found_high_key;
2334       if (!FindGreatestKeyLessThanOrEqual(
2335                transaction, cursor_options->high_key, &found_high_key))
2336         return false;
2337
2338       // If the target key should not be included, but we end up with a smaller
2339       // key, we should include that.
2340       if (cursor_options->high_open &&
2341           CompareIndexKeys(found_high_key, cursor_options->high_key) < 0)
2342         cursor_options->high_open = false;
2343
2344       cursor_options->high_key = found_high_key;
2345     }
2346   }
2347
2348   return true;
2349 }
2350
2351 bool IndexCursorOptions(
2352     LevelDBTransaction* transaction,
2353     int64 database_id,
2354     int64 object_store_id,
2355     int64 index_id,
2356     const IndexedDBKeyRange& range,
2357     indexed_db::CursorDirection direction,
2358     IndexedDBBackingStore::Cursor::CursorOptions* cursor_options) {
2359   DCHECK(transaction);
2360   if (!KeyPrefix::ValidIds(database_id, object_store_id, index_id))
2361     return false;
2362
2363   cursor_options->database_id = database_id;
2364   cursor_options->object_store_id = object_store_id;
2365   cursor_options->index_id = index_id;
2366
2367   bool lower_bound = range.lower().IsValid();
2368   bool upper_bound = range.upper().IsValid();
2369   cursor_options->forward =
2370       (direction == indexed_db::CURSOR_NEXT_NO_DUPLICATE ||
2371        direction == indexed_db::CURSOR_NEXT);
2372   cursor_options->unique = (direction == indexed_db::CURSOR_NEXT_NO_DUPLICATE ||
2373                             direction == indexed_db::CURSOR_PREV_NO_DUPLICATE);
2374
2375   if (!lower_bound) {
2376     cursor_options->low_key =
2377         IndexDataKey::EncodeMinKey(database_id, object_store_id, index_id);
2378     cursor_options->low_open = false;  // Included.
2379   } else {
2380     cursor_options->low_key = IndexDataKey::Encode(
2381         database_id, object_store_id, index_id, range.lower());
2382     cursor_options->low_open = range.lowerOpen();
2383   }
2384
2385   if (!upper_bound) {
2386     cursor_options->high_key =
2387         IndexDataKey::EncodeMaxKey(database_id, object_store_id, index_id);
2388     cursor_options->high_open = false;  // Included.
2389
2390     if (!cursor_options->forward) {  // We need a key that exists.
2391       if (!FindGreatestKeyLessThanOrEqual(transaction,
2392                                           cursor_options->high_key,
2393                                           &cursor_options->high_key))
2394         return false;
2395       cursor_options->high_open = false;
2396     }
2397   } else {
2398     cursor_options->high_key = IndexDataKey::Encode(
2399         database_id, object_store_id, index_id, range.upper());
2400     cursor_options->high_open = range.upperOpen();
2401
2402     std::string found_high_key;
2403     // Seek to the *last* key in the set of non-unique keys
2404     if (!FindGreatestKeyLessThanOrEqual(
2405              transaction, cursor_options->high_key, &found_high_key))
2406       return false;
2407
2408     // If the target key should not be included, but we end up with a smaller
2409     // key, we should include that.
2410     if (cursor_options->high_open &&
2411         CompareIndexKeys(found_high_key, cursor_options->high_key) < 0)
2412       cursor_options->high_open = false;
2413
2414     cursor_options->high_key = found_high_key;
2415   }
2416
2417   return true;
2418 }
2419
2420 scoped_ptr<IndexedDBBackingStore::Cursor>
2421 IndexedDBBackingStore::OpenObjectStoreCursor(
2422     IndexedDBBackingStore::Transaction* transaction,
2423     int64 database_id,
2424     int64 object_store_id,
2425     const IndexedDBKeyRange& range,
2426     indexed_db::CursorDirection direction) {
2427   IDB_TRACE("IndexedDBBackingStore::OpenObjectStoreCursor");
2428   LevelDBTransaction* leveldb_transaction = transaction->transaction();
2429   IndexedDBBackingStore::Cursor::CursorOptions cursor_options;
2430   if (!ObjectStoreCursorOptions(leveldb_transaction,
2431                                 database_id,
2432                                 object_store_id,
2433                                 range,
2434                                 direction,
2435                                 &cursor_options))
2436     return scoped_ptr<IndexedDBBackingStore::Cursor>();
2437   scoped_ptr<ObjectStoreCursorImpl> cursor(
2438       new ObjectStoreCursorImpl(leveldb_transaction, cursor_options));
2439   if (!cursor->FirstSeek())
2440     return scoped_ptr<IndexedDBBackingStore::Cursor>();
2441
2442   return cursor.PassAs<IndexedDBBackingStore::Cursor>();
2443 }
2444
2445 scoped_ptr<IndexedDBBackingStore::Cursor>
2446 IndexedDBBackingStore::OpenObjectStoreKeyCursor(
2447     IndexedDBBackingStore::Transaction* transaction,
2448     int64 database_id,
2449     int64 object_store_id,
2450     const IndexedDBKeyRange& range,
2451     indexed_db::CursorDirection direction) {
2452   IDB_TRACE("IndexedDBBackingStore::OpenObjectStoreKeyCursor");
2453   LevelDBTransaction* leveldb_transaction = transaction->transaction();
2454   IndexedDBBackingStore::Cursor::CursorOptions cursor_options;
2455   if (!ObjectStoreCursorOptions(leveldb_transaction,
2456                                 database_id,
2457                                 object_store_id,
2458                                 range,
2459                                 direction,
2460                                 &cursor_options))
2461     return scoped_ptr<IndexedDBBackingStore::Cursor>();
2462   scoped_ptr<ObjectStoreKeyCursorImpl> cursor(
2463       new ObjectStoreKeyCursorImpl(leveldb_transaction, cursor_options));
2464   if (!cursor->FirstSeek())
2465     return scoped_ptr<IndexedDBBackingStore::Cursor>();
2466
2467   return cursor.PassAs<IndexedDBBackingStore::Cursor>();
2468 }
2469
2470 scoped_ptr<IndexedDBBackingStore::Cursor>
2471 IndexedDBBackingStore::OpenIndexKeyCursor(
2472     IndexedDBBackingStore::Transaction* transaction,
2473     int64 database_id,
2474     int64 object_store_id,
2475     int64 index_id,
2476     const IndexedDBKeyRange& range,
2477     indexed_db::CursorDirection direction) {
2478   IDB_TRACE("IndexedDBBackingStore::OpenIndexKeyCursor");
2479   LevelDBTransaction* leveldb_transaction = transaction->transaction();
2480   IndexedDBBackingStore::Cursor::CursorOptions cursor_options;
2481   if (!IndexCursorOptions(leveldb_transaction,
2482                           database_id,
2483                           object_store_id,
2484                           index_id,
2485                           range,
2486                           direction,
2487                           &cursor_options))
2488     return scoped_ptr<IndexedDBBackingStore::Cursor>();
2489   scoped_ptr<IndexKeyCursorImpl> cursor(
2490       new IndexKeyCursorImpl(leveldb_transaction, cursor_options));
2491   if (!cursor->FirstSeek())
2492     return scoped_ptr<IndexedDBBackingStore::Cursor>();
2493
2494   return cursor.PassAs<IndexedDBBackingStore::Cursor>();
2495 }
2496
2497 scoped_ptr<IndexedDBBackingStore::Cursor>
2498 IndexedDBBackingStore::OpenIndexCursor(
2499     IndexedDBBackingStore::Transaction* transaction,
2500     int64 database_id,
2501     int64 object_store_id,
2502     int64 index_id,
2503     const IndexedDBKeyRange& range,
2504     indexed_db::CursorDirection direction) {
2505   IDB_TRACE("IndexedDBBackingStore::OpenIndexCursor");
2506   LevelDBTransaction* leveldb_transaction = transaction->transaction();
2507   IndexedDBBackingStore::Cursor::CursorOptions cursor_options;
2508   if (!IndexCursorOptions(leveldb_transaction,
2509                           database_id,
2510                           object_store_id,
2511                           index_id,
2512                           range,
2513                           direction,
2514                           &cursor_options))
2515     return scoped_ptr<IndexedDBBackingStore::Cursor>();
2516   scoped_ptr<IndexCursorImpl> cursor(
2517       new IndexCursorImpl(leveldb_transaction, cursor_options));
2518   if (!cursor->FirstSeek())
2519     return scoped_ptr<IndexedDBBackingStore::Cursor>();
2520
2521   return cursor.PassAs<IndexedDBBackingStore::Cursor>();
2522 }
2523
2524 IndexedDBBackingStore::Transaction::Transaction(
2525     IndexedDBBackingStore* backing_store)
2526     : backing_store_(backing_store) {}
2527
2528 IndexedDBBackingStore::Transaction::~Transaction() {}
2529
2530 void IndexedDBBackingStore::Transaction::Begin() {
2531   IDB_TRACE("IndexedDBBackingStore::Transaction::Begin");
2532   DCHECK(!transaction_.get());
2533   transaction_ = new LevelDBTransaction(backing_store_->db_.get());
2534 }
2535
2536 bool IndexedDBBackingStore::Transaction::Commit() {
2537   IDB_TRACE("IndexedDBBackingStore::Transaction::Commit");
2538   DCHECK(transaction_.get());
2539   bool result = transaction_->Commit();
2540   transaction_ = NULL;
2541   if (!result)
2542     INTERNAL_WRITE_ERROR(TRANSACTION_COMMIT_METHOD);
2543   return result;
2544 }
2545
2546 void IndexedDBBackingStore::Transaction::Rollback() {
2547   IDB_TRACE("IndexedDBBackingStore::Transaction::Rollback");
2548   DCHECK(transaction_.get());
2549   transaction_->Rollback();
2550   transaction_ = NULL;
2551 }
2552
2553 }  // namespace content