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