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