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