IndexedDB: Protect against key prefix overflows
[WebKit-https.git] / Source / WebCore / Modules / indexeddb / IDBLevelDBCoding.cpp
1 /*
2  * Copyright (C) 2011 Google Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "IDBLevelDBCoding.h"
28
29 #if ENABLE(INDEXED_DATABASE)
30 #if USE(LEVELDB)
31
32 #include "IDBKey.h"
33 #include "IDBKeyPath.h"
34 #include "LevelDBSlice.h"
35 #include <wtf/ByteOrder.h>
36 #include <wtf/text/StringBuilder.h>
37
38 // LevelDB stores key/value pairs. Keys and values are strings of bytes, normally of type Vector<char>.
39 //
40 // The keys in the backing store are variable-length tuples with different types
41 // of fields. Each key in the backing store starts with a ternary prefix: (database id, object store id, index id). For each, 0 is reserved for meta-data.
42 // The prefix makes sure that data for a specific database, object store, and index are grouped together. The locality is important for performance: common
43 // operations should only need a minimal number of seek operations. For example, all the meta-data for a database is grouped together so that reading that
44 // meta-data only requires one seek.
45 //
46 // Each key type has a class (in square brackets below) which knows how to encode, decode, and compare that key type.
47 //
48 // Global meta-data have keys with prefix (0,0,0), followed by a type byte:
49 //
50 //     <0, 0, 0, 0>                                           => IndexedDB/LevelDB schema version [SchemaVersionKey]
51 //     <0, 0, 0, 1>                                           => The maximum database id ever allocated [MaxDatabaseIdKey]
52 //     <0, 0, 0, 2>                                           => SerializedScriptValue version [DataVersionKey]
53 //     <0, 0, 0, 100, database id>                            => Existence implies the database id is in the free list [DatabaseFreeListKey]
54 //     <0, 0, 0, 201, utf16 origin name, utf16 database name> => Database id [DatabaseNameKey]
55 //
56 //
57 // Database meta-data:
58 //
59 //     Again, the prefix is followed by a type byte.
60 //
61 //     <database id, 0, 0, 0> => utf16 origin name [DatabaseMetaDataKey]
62 //     <database id, 0, 0, 1> => utf16 database name [DatabaseMetaDataKey]
63 //     <database id, 0, 0, 2> => utf16 user version data [DatabaseMetaDataKey]
64 //     <database id, 0, 0, 3> => maximum object store id ever allocated [DatabaseMetaDataKey]
65 //     <database id, 0, 0, 4> => user integer version (var int) [DatabaseMetaDataKey]
66 //
67 //
68 // Object store meta-data:
69 //
70 //     The prefix is followed by a type byte, then a variable-length integer, and then another type byte.
71 //
72 //     <database id, 0, 0, 50, object store id, 0> => utf16 object store name [ObjectStoreMetaDataKey]
73 //     <database id, 0, 0, 50, object store id, 1> => utf16 key path [ObjectStoreMetaDataKey]
74 //     <database id, 0, 0, 50, object store id, 2> => has auto increment [ObjectStoreMetaDataKey]
75 //     <database id, 0, 0, 50, object store id, 3> => is evictable [ObjectStoreMetaDataKey]
76 //     <database id, 0, 0, 50, object store id, 4> => last "version" number [ObjectStoreMetaDataKey]
77 //     <database id, 0, 0, 50, object store id, 5> => maximum index id ever allocated [ObjectStoreMetaDataKey]
78 //     <database id, 0, 0, 50, object store id, 6> => has key path (vs. null) [ObjectStoreMetaDataKey]
79 //     <database id, 0, 0, 50, object store id, 7> => key generator current number [ObjectStoreMetaDataKey]
80 //
81 //
82 // Index meta-data:
83 //
84 //     The prefix is followed by a type byte, then two variable-length integers, and then another type byte.
85 //
86 //     <database id, 0, 0, 100, object store id, index id, 0> => utf16 index name [IndexMetaDataKey]
87 //     <database id, 0, 0, 100, object store id, index id, 1> => are index keys unique [IndexMetaDataKey]
88 //     <database id, 0, 0, 100, object store id, index id, 2> => utf16 key path [IndexMetaDataKey]
89 //     <database id, 0, 0, 100, object store id, index id, 3> => is index multi-entry [IndexMetaDataKey]
90 //
91 //
92 // Other object store and index meta-data:
93 //
94 //     The prefix is followed by a type byte. The object store and index id are variable length integers, the utf16 strings are variable length strings.
95 //
96 //     <database id, 0, 0, 150, object store id>                   => existence implies the object store id is in the free list [ObjectStoreFreeListKey]
97 //     <database id, 0, 0, 151, object store id, index id>         => existence implies the index id is in the free list [IndexFreeListKey]
98 //     <database id, 0, 0, 200, utf16 object store name>           => object store id [ObjectStoreNamesKey]
99 //     <database id, 0, 0, 201, object store id, utf16 index name> => index id [IndexNamesKey]
100 //
101 //
102 // Object store data:
103 //
104 //     The prefix is followed by a type byte. The user key is an encoded IDBKey.
105 //
106 //     <database id, object store id, 1, user key> => "version", serialized script value [ObjectStoreDataKey]
107 //
108 //
109 // "Exists" entry:
110 //
111 //     The prefix is followed by a type byte. The user key is an encoded IDBKey.
112 //
113 //     <database id, object store id, 2, user key> => "version" [ExistsEntryKey]
114 //
115 //
116 // Index data:
117 //
118 //     The prefix is followed by a type byte. The index key is an encoded IDBKey. The sequence number is a variable length integer.
119 //     The primary key is an encoded IDBKey.
120 //
121 //     <database id, object store id, index id, index key, sequence number, primary key> => "version", primary key [IndexDataKey]
122 //
123 //     (The sequence number is obsolete; it was used to allow two entries with
124 //     the same user (index) key in non-unique indexes prior to the inclusion of
125 //     the primary key in the data. The "version" field is used to weed out stale
126 //     index data. Whenever new object store data is inserted, it gets a new
127 //     "version" number, and new index data is written with this number. When
128 //     the index is used for look-ups, entries are validated against the
129 //     "exists" entries, and records with old "version" numbers are deleted
130 //     when they are encountered in getPrimaryKeyViaIndex,
131 //     IndexCursorImpl::loadCurrentRow, and IndexKeyCursorImpl::loadCurrentRow).
132
133 namespace WebCore {
134 namespace IDBLevelDBCoding {
135
136 #ifndef INT64_MAX
137 #define INT64_MAX 0x7fffffffffffffffLL
138 #endif
139 #ifndef INT32_MAX
140 #define INT32_MAX 0x7fffffffL
141 #endif
142
143 static const unsigned char IDBKeyNullTypeByte = 0;
144 static const unsigned char IDBKeyStringTypeByte = 1;
145 static const unsigned char IDBKeyDateTypeByte = 2;
146 static const unsigned char IDBKeyNumberTypeByte = 3;
147 static const unsigned char IDBKeyArrayTypeByte = 4;
148 static const unsigned char IDBKeyMinKeyTypeByte = 5;
149
150 static const unsigned char IDBKeyPathTypeCodedByte1 = 0;
151 static const unsigned char IDBKeyPathTypeCodedByte2 = 0;
152
153 static const unsigned char ObjectStoreDataIndexId = 1;
154 static const unsigned char ExistsEntryIndexId = 2;
155
156 static const unsigned char SchemaVersionTypeByte = 0;
157 static const unsigned char MaxDatabaseIdTypeByte = 1;
158 static const unsigned char DataVersionTypeByte = 2;
159 static const unsigned char MaxSimpleGlobalMetaDataTypeByte = 3; // Insert before this and increment.
160 static const unsigned char DatabaseFreeListTypeByte = 100;
161 static const unsigned char DatabaseNameTypeByte = 201;
162
163 static const unsigned char ObjectStoreMetaDataTypeByte = 50;
164 static const unsigned char IndexMetaDataTypeByte = 100;
165 static const unsigned char ObjectStoreFreeListTypeByte = 150;
166 static const unsigned char IndexFreeListTypeByte = 151;
167 static const unsigned char ObjectStoreNamesTypeByte = 200;
168 static const unsigned char IndexNamesKeyTypeByte = 201;
169
170 static const unsigned char ObjectMetaDataTypeMaximum = 255;
171 static const unsigned char IndexMetaDataTypeMaximum = 255;
172
173 Vector<char> encodeByte(unsigned char c)
174 {
175     Vector<char, DefaultInlineBufferSize> v;
176     v.append(c);
177
178     ASSERT(v.size() <= DefaultInlineBufferSize);
179     return v;
180 }
181
182 const char* decodeByte(const char* p, const char* limit, unsigned char& foundChar)
183 {
184     if (p >= limit)
185         return 0;
186
187     foundChar = *p++;
188     return p;
189 }
190
191 Vector<char> maxIDBKey()
192 {
193     return encodeByte(IDBKeyNullTypeByte);
194 }
195
196 Vector<char> minIDBKey()
197 {
198     return encodeByte(IDBKeyMinKeyTypeByte);
199 }
200
201 Vector<char> encodeBool(bool b)
202 {
203     Vector<char, DefaultInlineBufferSize> ret;
204     ret.append(b ? 1 : 0);
205
206     ASSERT(ret.size() <= DefaultInlineBufferSize);
207     return ret;
208 }
209
210 bool decodeBool(const char* begin, const char* end)
211 {
212     ASSERT(begin < end);
213     return *begin;
214 }
215
216 Vector<char> encodeInt(int64_t nParam)
217 {
218     ASSERT(nParam >= 0);
219     uint64_t n = static_cast<uint64_t>(nParam);
220     Vector<char, DefaultInlineBufferSize> ret;
221
222     do {
223         unsigned char c = n;
224         ret.append(c);
225         n >>= 8;
226     } while (n);
227
228     ASSERT(ret.size() <= DefaultInlineBufferSize);
229     return ret;
230 }
231
232 int64_t decodeInt(const char* begin, const char* end)
233 {
234     ASSERT(begin <= end);
235     int64_t ret = 0;
236
237     int shift = 0;
238     while (begin < end) {
239         unsigned char c = *begin++;
240         ret |= static_cast<int64_t>(c) << shift;
241         shift += 8;
242     }
243
244     return ret;
245 }
246
247 static int compareInts(int64_t a, int64_t b)
248 {
249     ASSERT(a >= 0);
250     ASSERT(b >= 0);
251
252     int64_t diff = a - b;
253     if (diff < 0)
254         return -1;
255     if (diff > 0)
256         return 1;
257     return 0;
258 }
259
260 Vector<char> encodeVarInt(int64_t nParam)
261 {
262     ASSERT(nParam >= 0);
263     uint64_t n = static_cast<uint64_t>(nParam);
264     Vector<char, DefaultInlineBufferSize> ret;
265
266     do {
267         unsigned char c = n & 0x7f;
268         n >>= 7;
269         if (n)
270             c |= 0x80;
271         ret.append(c);
272     } while (n);
273
274     ASSERT(ret.size() <= DefaultInlineBufferSize);
275     return ret;
276 }
277
278 const char* decodeVarInt(const char* p, const char* limit, int64_t& foundInt)
279 {
280     ASSERT(limit >= p);
281     foundInt = 0;
282     int shift = 0;
283
284     do {
285         if (p >= limit)
286             return 0;
287
288         unsigned char c = *p;
289         foundInt |= static_cast<int64_t>(c & 0x7f) << shift;
290         shift += 7;
291     } while (*p++ & 0x80);
292     return p;
293 }
294
295 Vector<char> encodeString(const String& s)
296 {
297     // Backing store is UTF-16BE, convert from host endianness.
298     size_t length = s.length();
299     Vector<char> ret(length * sizeof(UChar));
300
301     const UChar* src = s.characters();
302     UChar* dst = reinterpret_cast<UChar*>(ret.data());
303     for (unsigned i = 0; i < length; ++i)
304         *dst++ = htons(*src++);
305
306     return ret;
307 }
308
309 String decodeString(const char* start, const char* end)
310 {
311     // Backing store is UTF-16BE, convert to host endianness.
312     ASSERT(end >= start);
313     ASSERT(!((end - start) % sizeof(UChar)));
314
315     size_t length = (end - start) / sizeof(UChar);
316     Vector<UChar> buffer(length);
317
318     const UChar* src = reinterpret_cast<const UChar*>(start);
319     UChar* dst = buffer.data();
320     for (unsigned i = 0; i < length; ++i)
321         *dst++ = ntohs(*src++);
322
323     return String::adopt(buffer);
324 }
325
326 Vector<char> encodeStringWithLength(const String& s)
327 {
328     Vector<char> ret = encodeVarInt(s.length());
329     ret.append(encodeString(s));
330     return ret;
331 }
332
333 const char* decodeStringWithLength(const char* p, const char* limit, String& foundString)
334 {
335     ASSERT(limit >= p);
336     int64_t len;
337     p = decodeVarInt(p, limit, len);
338     if (!p || len < 0 || p + len * 2 > limit)
339         return 0;
340
341     foundString = decodeString(p, p + len * 2);
342     p += len * 2;
343     return p;
344 }
345
346 int compareEncodedStringsWithLength(const char*& p, const char* limitP, const char*& q, const char* limitQ, bool& ok)
347 {
348     ASSERT(&p != &q);
349     ASSERT(limitP >= p);
350     ASSERT(limitQ >= q);
351     int64_t lenP, lenQ;
352     p = decodeVarInt(p, limitP, lenP);
353     q = decodeVarInt(q, limitQ, lenQ);
354     if (!p || !q || lenP < 0 || lenQ < 0) {
355         ok = false;
356         return 0;
357     }
358     ASSERT(p && q);
359     ASSERT(lenP >= 0);
360     ASSERT(lenQ >= 0);
361     ASSERT(p + lenP * 2 <= limitP);
362     ASSERT(q + lenQ * 2 <= limitQ);
363
364     const char* startP = p;
365     const char* startQ = q;
366     p += lenP * 2;
367     q += lenQ * 2;
368
369     if (p > limitP || q > limitQ) {
370         ok = false;
371         return 0;
372     }
373
374     ok = true;
375     const size_t lmin = static_cast<size_t>(lenP < lenQ ? lenP : lenQ);
376     if (int x = memcmp(startP, startQ, lmin * 2))
377         return x;
378
379     if (lenP == lenQ)
380         return 0;
381
382     return (lenP > lenQ) ? 1 : -1;
383 }
384
385 Vector<char> encodeDouble(double x)
386 {
387     // FIXME: It would be nice if we could be byte order independent.
388     const char* p = reinterpret_cast<char*>(&x);
389     Vector<char, DefaultInlineBufferSize> v;
390     v.append(p, sizeof(x));
391
392     ASSERT(v.size() <= DefaultInlineBufferSize);
393     return v;
394 }
395
396 const char* decodeDouble(const char* p, const char* limit, double* d)
397 {
398     if (p + sizeof(*d) > limit)
399         return 0;
400
401     char* x = reinterpret_cast<char*>(d);
402     for (size_t i = 0; i < sizeof(*d); ++i)
403         *x++ = *p++;
404     return p;
405 }
406
407 Vector<char> encodeIDBKey(const IDBKey& key)
408 {
409     Vector<char, DefaultInlineBufferSize> ret;
410     encodeIDBKey(key, ret);
411     return ret;
412 }
413
414 void encodeIDBKey(const IDBKey& key, Vector<char, DefaultInlineBufferSize>& into)
415 {
416     size_t previousSize = into.size();
417     ASSERT(key.isValid());
418     switch (key.type()) {
419     case IDBKey::InvalidType:
420     case IDBKey::MinType:
421         ASSERT_NOT_REACHED();
422         into.append(encodeByte(IDBKeyNullTypeByte));
423         return;
424     case IDBKey::ArrayType: {
425         into.append(encodeByte(IDBKeyArrayTypeByte));
426         size_t length = key.array().size();
427         into.append(encodeVarInt(length));
428         for (size_t i = 0; i < length; ++i)
429             encodeIDBKey(*key.array()[i], into);
430         ASSERT_UNUSED(previousSize, into.size() > previousSize);
431         return;
432     }
433     case IDBKey::StringType:
434         into.append(encodeByte(IDBKeyStringTypeByte));
435         into.append(encodeStringWithLength(key.string()));
436         ASSERT_UNUSED(previousSize, into.size() > previousSize);
437         return;
438     case IDBKey::DateType:
439         into.append(encodeByte(IDBKeyDateTypeByte));
440         into.append(encodeDouble(key.date()));
441         ASSERT_UNUSED(previousSize, into.size() - previousSize == 9);
442         return;
443     case IDBKey::NumberType:
444         into.append(encodeByte(IDBKeyNumberTypeByte));
445         into.append(encodeDouble(key.number()));
446         ASSERT_UNUSED(previousSize, into.size() - previousSize == 9);
447         return;
448     }
449
450     ASSERT_NOT_REACHED();
451 }
452
453
454 const char* decodeIDBKey(const char* p, const char* limit, RefPtr<IDBKey>& foundKey)
455 {
456     ASSERT(limit >= p);
457     if (p >= limit)
458         return 0;
459
460     unsigned char type = *p++;
461
462     switch (type) {
463     case IDBKeyNullTypeByte:
464         foundKey = IDBKey::createInvalid();
465         return p;
466
467     case IDBKeyArrayTypeByte: {
468         int64_t length;
469         p = decodeVarInt(p, limit, length);
470         if (!p || length < 0)
471             return 0;
472         IDBKey::KeyArray array;
473         while (length--) {
474             RefPtr<IDBKey> key;
475             p = decodeIDBKey(p, limit, key);
476             if (!p)
477                 return 0;
478             array.append(key);
479         }
480         foundKey = IDBKey::createArray(array);
481         return p;
482     }
483     case IDBKeyStringTypeByte: {
484         String s;
485         p = decodeStringWithLength(p, limit, s);
486         if (!p)
487             return 0;
488         foundKey = IDBKey::createString(s);
489         return p;
490     }
491     case IDBKeyDateTypeByte: {
492         double d;
493         p = decodeDouble(p, limit, &d);
494         if (!p)
495             return 0;
496         foundKey = IDBKey::createDate(d);
497         return p;
498     }
499     case IDBKeyNumberTypeByte: {
500         double d;
501         p = decodeDouble(p, limit, &d);
502         if (!p)
503             return 0;
504         foundKey = IDBKey::createNumber(d);
505         return p;
506     }
507     }
508
509     ASSERT_NOT_REACHED();
510     return 0;
511 }
512
513 const char* extractEncodedIDBKey(const char* start, const char* limit, Vector<char>* result = 0)
514 {
515     const char* p = start;
516     if (p >= limit)
517         return 0;
518
519     unsigned char type = *p++;
520
521     switch (type) {
522     case IDBKeyNullTypeByte:
523     case IDBKeyMinKeyTypeByte:
524         break;
525     case IDBKeyArrayTypeByte: {
526         int64_t length;
527         p = decodeVarInt(p, limit, length);
528         if (!p || length < 0)
529             return 0;
530         while (length--) {
531             p = extractEncodedIDBKey(p, limit);
532             if (!p)
533                 return 0;
534         }
535         break;
536     }
537     case IDBKeyStringTypeByte: {
538         int64_t length;
539         p = decodeVarInt(p, limit, length);
540         if (!p || length < 0 || p + length * 2 > limit)
541             return 0;
542         p += length * 2;
543         break;
544     }
545     case IDBKeyDateTypeByte:
546     case IDBKeyNumberTypeByte:
547         if (p + sizeof(double) > limit)
548             return 0;
549         p += sizeof(double);
550         break;
551     }
552
553     if (result) {
554         ASSERT(p);
555         ASSERT(p <= limit);
556         result->clear();
557         result->append(start, p - start);
558     }
559
560     return p;
561 }
562
563 static IDBKey::Type keyTypeByteToKeyType(unsigned char type)
564 {
565     switch (type) {
566     case IDBKeyNullTypeByte:
567         return IDBKey::InvalidType;
568     case IDBKeyArrayTypeByte:
569         return IDBKey::ArrayType;
570     case IDBKeyStringTypeByte:
571         return IDBKey::StringType;
572     case IDBKeyDateTypeByte:
573         return IDBKey::DateType;
574     case IDBKeyNumberTypeByte:
575         return IDBKey::NumberType;
576     case IDBKeyMinKeyTypeByte:
577         return IDBKey::MinType;
578     }
579
580     ASSERT_NOT_REACHED();
581     return IDBKey::InvalidType;
582 }
583
584 int compareEncodedIDBKeys(const char*& ptrA, const char* limitA, const char*& ptrB, const char* limitB, bool& ok)
585 {
586     ok = true;
587     ASSERT(&ptrA != &ptrB);
588     ASSERT(ptrA < limitA);
589     ASSERT(ptrB < limitB);
590     unsigned char typeA = *ptrA++;
591     unsigned char typeB = *ptrB++;
592
593     if (int x = IDBKey::compareTypes(keyTypeByteToKeyType(typeA), keyTypeByteToKeyType(typeB)))
594         return x;
595
596     switch (typeA) {
597     case IDBKeyNullTypeByte:
598     case IDBKeyMinKeyTypeByte:
599         // Null type or max type; no payload to compare.
600         return 0;
601     case IDBKeyArrayTypeByte: {
602         int64_t lengthA, lengthB;
603         ptrA = decodeVarInt(ptrA, limitA, lengthA);
604         ptrB = decodeVarInt(ptrB, limitB, lengthB);
605         if (!ptrA || !ptrB || lengthA < 0 || lengthB < 0) {
606             ok = false;
607             return 0;
608         }
609         for (int64_t i = 0; i < lengthA && i < lengthB; ++i) {
610             int result = compareEncodedIDBKeys(ptrA, limitA, ptrB, limitB, ok);
611             if (!ok || result)
612                 return result;
613         }
614         if (lengthA < lengthB)
615             return -1;
616         if (lengthA > lengthB)
617             return 1;
618         return 0;
619     }
620     case IDBKeyStringTypeByte:
621         return compareEncodedStringsWithLength(ptrA, limitA, ptrB, limitB, ok);
622     case IDBKeyDateTypeByte:
623     case IDBKeyNumberTypeByte: {
624         double d, e;
625         ptrA = decodeDouble(ptrA, limitA, &d);
626         ptrB = decodeDouble(ptrB, limitB, &e);
627         ASSERT(ptrA);
628         ASSERT(ptrB);
629         if (!ptrA || !ptrB) {
630             ok = false;
631             return 0;
632         }
633         if (d < e)
634             return -1;
635         if (d > e)
636             return 1;
637         return 0;
638     }
639     }
640
641     ASSERT_NOT_REACHED();
642     return 0;
643 }
644
645 int compareEncodedIDBKeys(const Vector<char>& keyA, const Vector<char>& keyB, bool& ok)
646 {
647     ASSERT(keyA.size() >= 1);
648     ASSERT(keyB.size() >= 1);
649
650     const char* ptrA = keyA.data();
651     const char* limitA = ptrA + keyA.size();
652     const char* ptrB = keyB.data();
653     const char* limitB = ptrB + keyB.size();
654
655     return compareEncodedIDBKeys(ptrA, limitA, ptrB, limitB, ok);
656 }
657
658 Vector<char> encodeIDBKeyPath(const IDBKeyPath& keyPath)
659 {
660     // May be typed, or may be a raw string. An invalid leading
661     // byte is used to identify typed coding. New records are
662     // always written as typed.
663     Vector<char, DefaultInlineBufferSize> ret;
664     ret.append(IDBKeyPathTypeCodedByte1);
665     ret.append(IDBKeyPathTypeCodedByte2);
666     ret.append(static_cast<char>(keyPath.type()));
667     switch (keyPath.type()) {
668     case IDBKeyPath::NullType:
669         break;
670     case IDBKeyPath::StringType:
671         ret.append(encodeStringWithLength(keyPath.string()));
672         break;
673     case IDBKeyPath::ArrayType: {
674         const Vector<String>& array = keyPath.array();
675         size_t count = array.size();
676         ret.append(encodeVarInt(count));
677         for (size_t i = 0; i < count; ++i)
678             ret.append(encodeStringWithLength(array[i]));
679         break;
680     }
681     }
682     return ret;
683 }
684
685 IDBKeyPath decodeIDBKeyPath(const char* p, const char* limit)
686 {
687     // May be typed, or may be a raw string. An invalid leading
688     // byte sequence is used to identify typed coding. New records are
689     // always written as typed.
690     if (p == limit || (limit - p >= 2 && (*p != IDBKeyPathTypeCodedByte1 || *(p + 1) != IDBKeyPathTypeCodedByte2)))
691         return IDBKeyPath(decodeString(p, limit));
692     p += 2;
693
694     ASSERT(p != limit);
695     IDBKeyPath::Type type = static_cast<IDBKeyPath::Type>(*p++);
696     switch (type) {
697     case IDBKeyPath::NullType:
698         ASSERT(p == limit);
699         return IDBKeyPath();
700     case IDBKeyPath::StringType: {
701         String string;
702         p = decodeStringWithLength(p, limit, string);
703         ASSERT(p == limit);
704         return IDBKeyPath(string);
705     }
706     case IDBKeyPath::ArrayType: {
707         Vector<String> array;
708         int64_t count;
709         p = decodeVarInt(p, limit, count);
710         ASSERT(p);
711         ASSERT(count >= 0);
712         while (count--) {
713             String string;
714             p = decodeStringWithLength(p, limit, string);
715             ASSERT(p);
716             array.append(string);
717         }
718         ASSERT(p == limit);
719         return IDBKeyPath(array);
720     }
721     }
722     ASSERT_NOT_REACHED();
723     return IDBKeyPath();
724 }
725
726 namespace {
727
728 template<typename KeyType>
729 int compare(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates, bool& ok)
730 {
731     KeyType keyA;
732     KeyType keyB;
733
734     const char* ptrA = KeyType::decode(a.begin(), a.end(), &keyA);
735     ASSERT(ptrA);
736     if (!ptrA) {
737         ok = false;
738         return 0;
739     }
740     const char* ptrB = KeyType::decode(b.begin(), b.end(), &keyB);
741     ASSERT(ptrB);
742     if (!ptrB) {
743         ok = false;
744         return 0;
745     }
746
747     ok = true;
748     return keyA.compare(keyB);
749 }
750
751 template<>
752 int compare<ExistsEntryKey>(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates, bool& ok)
753 {
754     KeyPrefix prefixA;
755     KeyPrefix prefixB;
756     const char* ptrA = KeyPrefix::decode(a.begin(), a.end(), &prefixA);
757     const char* ptrB = KeyPrefix::decode(b.begin(), b.end(), &prefixB);
758     ASSERT(ptrA);
759     ASSERT(ptrB);
760     ASSERT(prefixA.m_databaseId);
761     ASSERT(prefixA.m_objectStoreId);
762     ASSERT(prefixA.m_indexId == ExistsEntryKey::SpecialIndexNumber);
763     ASSERT(prefixB.m_databaseId);
764     ASSERT(prefixB.m_objectStoreId);
765     ASSERT(prefixB.m_indexId == ExistsEntryKey::SpecialIndexNumber);
766     ASSERT(ptrA != a.end());
767     ASSERT(ptrB != b.end());
768     // Prefixes are not compared - it is assumed this was already done.
769     ASSERT(!prefixA.compare(prefixB));
770
771     return compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end(), ok);
772 }
773
774 template<>
775 int compare<ObjectStoreDataKey>(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates, bool& ok)
776 {
777     KeyPrefix prefixA;
778     KeyPrefix prefixB;
779     const char* ptrA = KeyPrefix::decode(a.begin(), a.end(), &prefixA);
780     const char* ptrB = KeyPrefix::decode(b.begin(), b.end(), &prefixB);
781     ASSERT(ptrA);
782     ASSERT(ptrB);
783     ASSERT(prefixA.m_databaseId);
784     ASSERT(prefixA.m_objectStoreId);
785     ASSERT(prefixA.m_indexId == ObjectStoreDataKey::SpecialIndexNumber);
786     ASSERT(prefixB.m_databaseId);
787     ASSERT(prefixB.m_objectStoreId);
788     ASSERT(prefixB.m_indexId == ObjectStoreDataKey::SpecialIndexNumber);
789     ASSERT(ptrA != a.end());
790     ASSERT(ptrB != b.end());
791     // Prefixes are not compared - it is assumed this was already done.
792     ASSERT(!prefixA.compare(prefixB));
793
794     return compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end(), ok);
795 }
796
797 template<>
798 int compare<IndexDataKey>(const LevelDBSlice& a, const LevelDBSlice& b, bool ignoreDuplicates, bool& ok)
799 {
800     KeyPrefix prefixA;
801     KeyPrefix prefixB;
802     const char* ptrA = KeyPrefix::decode(a.begin(), a.end(), &prefixA);
803     const char* ptrB = KeyPrefix::decode(b.begin(), b.end(), &prefixB);
804     ASSERT(ptrA);
805     ASSERT(ptrB);
806     ASSERT(prefixA.m_databaseId);
807     ASSERT(prefixA.m_objectStoreId);
808     ASSERT(prefixA.m_indexId >= MinimumIndexId);
809     ASSERT(prefixB.m_databaseId);
810     ASSERT(prefixB.m_objectStoreId);
811     ASSERT(prefixB.m_indexId >= MinimumIndexId);
812     ASSERT(ptrA != a.end());
813     ASSERT(ptrB != b.end());
814     // Prefixes are not compared - it is assumed this was already done.
815     ASSERT(!prefixA.compare(prefixB));
816
817     // index key
818     int result = compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end(), ok);
819     if (!ok || result)
820         return result;
821     if (ignoreDuplicates)
822         return 0;
823
824     // sequence number [optional]
825     int64_t sequenceNumberA = -1;
826     int64_t sequenceNumberB = -1;
827     if (ptrA != a.end())
828         ptrA = decodeVarInt(ptrA, a.end(), sequenceNumberA);
829     if (ptrB != b.end())
830         ptrB = decodeVarInt(ptrB, b.end(), sequenceNumberB);
831
832     // primary key [optional]
833     if (!ptrA || !ptrB)
834         return 0;
835     if (ptrA == a.end() && ptrB == b.end())
836         return 0;
837     if (ptrA == a.end())
838         return -1;
839     if (ptrB == b.end())
840         return 1;
841
842     result = compareEncodedIDBKeys(ptrA, a.end(), ptrB, b.end(), ok);
843     if (!ok || result)
844         return result;
845
846     return compareInts(sequenceNumberA, sequenceNumberB);
847 }
848
849 int compare(const LevelDBSlice& a, const LevelDBSlice& b, bool indexKeys, bool& ok)
850 {
851     const char* ptrA = a.begin();
852     const char* ptrB = b.begin();
853     const char* endA = a.end();
854     const char* endB = b.end();
855
856     KeyPrefix prefixA;
857     KeyPrefix prefixB;
858
859     ptrA = KeyPrefix::decode(ptrA, endA, &prefixA);
860     ptrB = KeyPrefix::decode(ptrB, endB, &prefixB);
861     ASSERT(ptrA);
862     ASSERT(ptrB);
863     if (!ptrA || !ptrB) {
864         ok = false;
865         return 0;
866     }
867
868     ok = true;
869     if (int x = prefixA.compare(prefixB))
870         return x;
871
872     if (prefixA.type() == KeyPrefix::GlobalMetaData) {
873         ASSERT(ptrA != endA);
874         ASSERT(ptrB != endB);
875
876         unsigned char typeByteA = *ptrA++;
877         unsigned char typeByteB = *ptrB++;
878
879         if (int x = typeByteA - typeByteB)
880             return x;
881         if (typeByteA < MaxSimpleGlobalMetaDataTypeByte)
882             return 0;
883
884         const bool ignoreDuplicates = false;
885         if (typeByteA == DatabaseFreeListTypeByte)
886             return compare<DatabaseFreeListKey>(a, b, ignoreDuplicates, ok);
887         if (typeByteA == DatabaseNameTypeByte)
888             return compare<DatabaseNameKey>(a, b, ignoreDuplicates, ok);
889     }
890
891     if (prefixA.type() == KeyPrefix::DatabaseMetaData) {
892         ASSERT(ptrA != endA);
893         ASSERT(ptrB != endB);
894
895         unsigned char typeByteA = *ptrA++;
896         unsigned char typeByteB = *ptrB++;
897
898         if (int x = typeByteA - typeByteB)
899             return x;
900         if (typeByteA < DatabaseMetaDataKey::MaxSimpleMetaDataType)
901             return 0;
902
903         const bool ignoreDuplicates = false;
904         if (typeByteA == ObjectStoreMetaDataTypeByte)
905             return compare<ObjectStoreMetaDataKey>(a, b, ignoreDuplicates, ok);
906         if (typeByteA == IndexMetaDataTypeByte)
907             return compare<IndexMetaDataKey>(a, b, ignoreDuplicates, ok);
908         if (typeByteA == ObjectStoreFreeListTypeByte)
909             return compare<ObjectStoreFreeListKey>(a, b, ignoreDuplicates, ok);
910         if (typeByteA == IndexFreeListTypeByte)
911             return compare<IndexFreeListKey>(a, b, ignoreDuplicates, ok);
912         if (typeByteA == ObjectStoreNamesTypeByte)
913             return compare<ObjectStoreNamesKey>(a, b, ignoreDuplicates, ok);
914         if (typeByteA == IndexNamesKeyTypeByte)
915             return compare<IndexNamesKey>(a, b, ignoreDuplicates, ok);
916     }
917
918     if (prefixA.type() == KeyPrefix::ObjectStoreData) {
919         if (ptrA == endA && ptrB == endB)
920             return 0;
921         if (ptrA == endA)
922             return -1;
923         if (ptrB == endB)
924             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
925
926         const bool ignoreDuplicates = false;
927         return compare<ObjectStoreDataKey>(a, b, ignoreDuplicates, ok);
928     }
929     if (prefixA.type() == KeyPrefix::ExistsEntry) {
930         if (ptrA == endA && ptrB == endB)
931             return 0;
932         if (ptrA == endA)
933             return -1;
934         if (ptrB == endB)
935             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
936
937         const bool ignoreDuplicates = false;
938         return compare<ExistsEntryKey>(a, b, ignoreDuplicates, ok);
939     }
940     if (prefixA.type() == KeyPrefix::IndexData) {
941         if (ptrA == endA && ptrB == endB)
942             return 0;
943         if (ptrA == endA)
944             return -1;
945         if (ptrB == endB)
946             return 1; // FIXME: This case of non-existing user keys should not have to be handled this way.
947
948         bool ignoreDuplicates = indexKeys;
949         return compare<IndexDataKey>(a, b, ignoreDuplicates, ok);
950     }
951
952     ASSERT_NOT_REACHED();
953     ok = false;
954     return 0;
955 }
956
957 }
958
959 int compare(const LevelDBSlice& a, const LevelDBSlice& b, bool indexKeys)
960 {
961     bool ok;
962     int result = compare(a, b, indexKeys, ok);
963     ASSERT(ok);
964     if (!ok)
965         return 0;
966     return result;
967 }
968
969 KeyPrefix::KeyPrefix()
970     : m_databaseId(InvalidType)
971     , m_objectStoreId(InvalidType)
972     , m_indexId(InvalidType)
973 {
974 }
975
976 KeyPrefix::KeyPrefix(int64_t databaseId)
977     : m_databaseId(databaseId)
978     , m_objectStoreId(0)
979     , m_indexId(0)
980 {
981     ASSERT(KeyPrefix::isValidDatabaseId(databaseId));
982 }
983
984 KeyPrefix::KeyPrefix(int64_t databaseId, int64_t objectStoreId)
985     : m_databaseId(databaseId)
986     , m_objectStoreId(objectStoreId)
987     , m_indexId(0)
988 {
989     ASSERT(KeyPrefix::isValidDatabaseId(databaseId));
990     ASSERT(KeyPrefix::isValidObjectStoreId(objectStoreId));
991 }
992
993 KeyPrefix::KeyPrefix(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
994     : m_databaseId(databaseId)
995     , m_objectStoreId(objectStoreId)
996     , m_indexId(indexId)
997 {
998     ASSERT(KeyPrefix::isValidDatabaseId(databaseId));
999     ASSERT(KeyPrefix::isValidObjectStoreId(objectStoreId));
1000     ASSERT(KeyPrefix::isValidIndexId(indexId));
1001 }
1002
1003 KeyPrefix::KeyPrefix(Type type, int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1004     : m_databaseId(databaseId)
1005     , m_objectStoreId(objectStoreId)
1006     , m_indexId(indexId)
1007 {
1008     ASSERT(type == InvalidType);
1009     ASSERT(KeyPrefix::isValidDatabaseId(databaseId));
1010     ASSERT(KeyPrefix::isValidObjectStoreId(objectStoreId));
1011 }
1012
1013
1014 KeyPrefix KeyPrefix::createWithSpecialIndex(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1015 {
1016     ASSERT(KeyPrefix::isValidDatabaseId(databaseId));
1017     ASSERT(KeyPrefix::isValidObjectStoreId(objectStoreId));
1018     ASSERT(indexId);
1019     return KeyPrefix(InvalidType, databaseId, objectStoreId, indexId);
1020 }
1021
1022
1023 bool KeyPrefix::isValidDatabaseId(int64_t databaseId)
1024 {
1025     return (databaseId > 0) && (databaseId < KeyPrefix::kMaxDatabaseId);
1026 }
1027
1028 bool KeyPrefix::isValidObjectStoreId(int64_t objectStoreId)
1029 {
1030     return (objectStoreId > 0) && (objectStoreId < KeyPrefix::kMaxObjectStoreId);
1031 }
1032
1033 bool KeyPrefix::isValidIndexId(int64_t indexId)
1034 {
1035     return (indexId >= MinimumIndexId) && (indexId < KeyPrefix::kMaxIndexId);
1036 }
1037
1038 const char* KeyPrefix::decode(const char* start, const char* limit, KeyPrefix* result)
1039 {
1040     if (start == limit)
1041         return 0;
1042
1043     unsigned char firstByte = *start++;
1044
1045     int databaseIdBytes = ((firstByte >> 5) & 0x7) + 1;
1046     int objectStoreIdBytes = ((firstByte >> 2) & 0x7) + 1;
1047     int indexIdBytes = (firstByte & 0x3) + 1;
1048
1049     if (start + databaseIdBytes + objectStoreIdBytes + indexIdBytes > limit)
1050         return 0;
1051
1052     result->m_databaseId = decodeInt(start, start + databaseIdBytes);
1053     start += databaseIdBytes;
1054     result->m_objectStoreId = decodeInt(start, start + objectStoreIdBytes);
1055     start += objectStoreIdBytes;
1056     result->m_indexId = decodeInt(start, start + indexIdBytes);
1057     start += indexIdBytes;
1058
1059     return start;
1060 }
1061
1062 Vector<char> KeyPrefix::encodeEmpty()
1063 {
1064     const Vector<char, 4> result(4, 0);
1065     ASSERT(encodeInternal(0, 0, 0) == Vector<char>(4, 0));
1066     return result;
1067 }
1068
1069 Vector<char> KeyPrefix::encode() const
1070 {
1071     ASSERT(m_databaseId != InvalidId);
1072     ASSERT(m_objectStoreId != InvalidId);
1073     ASSERT(m_indexId != InvalidId);
1074     return encodeInternal(m_databaseId, m_objectStoreId, m_indexId);
1075 }
1076
1077 Vector<char> KeyPrefix::encodeInternal(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1078 {
1079     Vector<char> databaseIdString = encodeIntSafely(databaseId, kMaxDatabaseId);
1080     Vector<char> objectStoreIdString = encodeIntSafely(objectStoreId, kMaxObjectStoreId);
1081     Vector<char> indexIdString = encodeIntSafely(indexId, kMaxIndexId);
1082
1083     ASSERT(databaseIdString.size() <= kMaxDatabaseIdSizeBytes);
1084     ASSERT(objectStoreIdString.size() <= kMaxObjectStoreIdSizeBytes);
1085     ASSERT(indexIdString.size() <= kMaxIndexIdSizeBytes);
1086
1087     unsigned char firstByte = (databaseIdString.size() - 1) << (kMaxObjectStoreIdSizeBits + kMaxIndexIdSizeBits) | (objectStoreIdString.size() - 1) << kMaxIndexIdSizeBits | (indexIdString.size() - 1);
1088     COMPILE_ASSERT(kMaxDatabaseIdSizeBits + kMaxObjectStoreIdSizeBits + kMaxIndexIdSizeBits == sizeof(firstByte) * 8, CANT_ENCODE_IDS);
1089     Vector<char, DefaultInlineBufferSize> ret;
1090     ret.append(firstByte);
1091     ret.append(databaseIdString);
1092     ret.append(objectStoreIdString);
1093     ret.append(indexIdString);
1094
1095     ASSERT(ret.size() <= DefaultInlineBufferSize);
1096     return ret;
1097 }
1098
1099 int KeyPrefix::compare(const KeyPrefix& other) const
1100 {
1101     ASSERT(m_databaseId != InvalidId);
1102     ASSERT(m_objectStoreId != InvalidId);
1103     ASSERT(m_indexId != InvalidId);
1104
1105     if (m_databaseId != other.m_databaseId)
1106         return compareInts(m_databaseId, other.m_databaseId);
1107     if (m_objectStoreId != other.m_objectStoreId)
1108         return compareInts(m_objectStoreId, other.m_objectStoreId);
1109     if (m_indexId != other.m_indexId)
1110         return compareInts(m_indexId, other.m_indexId);
1111     return 0;
1112 }
1113
1114 KeyPrefix::Type KeyPrefix::type() const
1115 {
1116     ASSERT(m_databaseId != InvalidId);
1117     ASSERT(m_objectStoreId != InvalidId);
1118     ASSERT(m_indexId != InvalidId);
1119
1120     if (!m_databaseId)
1121         return GlobalMetaData;
1122     if (!m_objectStoreId)
1123         return DatabaseMetaData;
1124     if (m_indexId == ObjectStoreDataIndexId)
1125         return ObjectStoreData;
1126     if (m_indexId == ExistsEntryIndexId)
1127         return ExistsEntry;
1128     if (m_indexId >= MinimumIndexId)
1129         return IndexData;
1130
1131     ASSERT_NOT_REACHED();
1132     return InvalidType;
1133 }
1134
1135 Vector<char> SchemaVersionKey::encode()
1136 {
1137     Vector<char> ret = KeyPrefix::encodeEmpty();
1138     ret.append(encodeByte(SchemaVersionTypeByte));
1139     return ret;
1140 }
1141
1142 Vector<char> MaxDatabaseIdKey::encode()
1143 {
1144     Vector<char> ret = KeyPrefix::encodeEmpty();
1145     ret.append(encodeByte(MaxDatabaseIdTypeByte));
1146     return ret;
1147 }
1148
1149 Vector<char> DataVersionKey::encode()
1150 {
1151     Vector<char> ret = KeyPrefix::encodeEmpty();
1152     ret.append(encodeByte(DataVersionTypeByte));
1153     return ret;
1154 }
1155
1156 DatabaseFreeListKey::DatabaseFreeListKey()
1157     : m_databaseId(-1)
1158 {
1159 }
1160
1161 const char* DatabaseFreeListKey::decode(const char* start, const char* limit, DatabaseFreeListKey* result)
1162 {
1163     KeyPrefix prefix;
1164     const char* p = KeyPrefix::decode(start, limit, &prefix);
1165     if (!p)
1166         return 0;
1167     ASSERT(!prefix.m_databaseId);
1168     ASSERT(!prefix.m_objectStoreId);
1169     ASSERT(!prefix.m_indexId);
1170     if (p == limit)
1171         return 0;
1172     unsigned char typeByte = 0;
1173     p = decodeByte(p, limit, typeByte);
1174     ASSERT_UNUSED(typeByte, typeByte == DatabaseFreeListTypeByte);
1175     if (p == limit)
1176         return 0;
1177     return decodeVarInt(p, limit, result->m_databaseId);
1178 }
1179
1180 Vector<char> DatabaseFreeListKey::encode(int64_t databaseId)
1181 {
1182     Vector<char> ret = KeyPrefix::encodeEmpty();
1183     ret.append(encodeByte(DatabaseFreeListTypeByte));
1184     ret.append(encodeVarInt(databaseId));
1185     return ret;
1186 }
1187
1188 Vector<char> DatabaseFreeListKey::encodeMaxKey()
1189 {
1190     return encode(INT64_MAX);
1191 }
1192
1193 int64_t DatabaseFreeListKey::databaseId() const
1194 {
1195     ASSERT(m_databaseId >= 0);
1196     return m_databaseId;
1197 }
1198
1199 int DatabaseFreeListKey::compare(const DatabaseFreeListKey& other) const
1200 {
1201     ASSERT(m_databaseId >= 0);
1202     return compareInts(m_databaseId, other.m_databaseId);
1203 }
1204
1205 const char* DatabaseNameKey::decode(const char* start, const char* limit, DatabaseNameKey* result)
1206 {
1207     KeyPrefix prefix;
1208     const char* p = KeyPrefix::decode(start, limit, &prefix);
1209     if (!p)
1210         return p;
1211     ASSERT(!prefix.m_databaseId);
1212     ASSERT(!prefix.m_objectStoreId);
1213     ASSERT(!prefix.m_indexId);
1214     if (p == limit)
1215         return 0;
1216     unsigned char typeByte = 0;
1217     p = decodeByte(p, limit, typeByte);
1218     ASSERT_UNUSED(typeByte, typeByte == DatabaseNameTypeByte);
1219     if (p == limit)
1220         return 0;
1221     p = decodeStringWithLength(p, limit, result->m_origin);
1222     if (!p)
1223         return 0;
1224     return decodeStringWithLength(p, limit, result->m_databaseName);
1225 }
1226
1227 Vector<char> DatabaseNameKey::encode(const String& origin, const String& databaseName)
1228 {
1229     Vector<char> ret = KeyPrefix::encodeEmpty();
1230     ret.append(encodeByte(DatabaseNameTypeByte));
1231     ret.append(encodeStringWithLength(origin));
1232     ret.append(encodeStringWithLength(databaseName));
1233     return ret;
1234 }
1235
1236 Vector<char> DatabaseNameKey::encodeMinKeyForOrigin(const String& origin)
1237 {
1238     return encode(origin, "");
1239 }
1240
1241 Vector<char> DatabaseNameKey::encodeStopKeyForOrigin(const String& origin)
1242 {
1243     // just after origin in collation order
1244     return encodeMinKeyForOrigin(origin + "\x01");
1245 }
1246
1247 int DatabaseNameKey::compare(const DatabaseNameKey& other)
1248 {
1249     if (int x = codePointCompare(m_origin, other.m_origin))
1250         return x;
1251     return codePointCompare(m_databaseName, other.m_databaseName);
1252 }
1253
1254 Vector<char> DatabaseMetaDataKey::encode(int64_t databaseId, MetaDataType metaDataType)
1255 {
1256     KeyPrefix prefix(databaseId);
1257     Vector<char> ret = prefix.encode();
1258     ret.append(encodeByte(metaDataType));
1259     return ret;
1260 }
1261
1262 ObjectStoreMetaDataKey::ObjectStoreMetaDataKey()
1263     : m_objectStoreId(-1)
1264     , m_metaDataType(-1)
1265 {
1266 }
1267
1268 const char* ObjectStoreMetaDataKey::decode(const char* start, const char* limit, ObjectStoreMetaDataKey* result)
1269 {
1270     KeyPrefix prefix;
1271     const char* p = KeyPrefix::decode(start, limit, &prefix);
1272     if (!p)
1273         return 0;
1274     ASSERT(prefix.m_databaseId);
1275     ASSERT(!prefix.m_objectStoreId);
1276     ASSERT(!prefix.m_indexId);
1277     if (p == limit)
1278         return 0;
1279     unsigned char typeByte = 0;
1280     p = decodeByte(p, limit, typeByte);
1281     ASSERT_UNUSED(typeByte, typeByte == ObjectStoreMetaDataTypeByte);
1282     if (p == limit)
1283         return 0;
1284     p = decodeVarInt(p, limit, result->m_objectStoreId);
1285     if (!p)
1286         return 0;
1287     ASSERT(result->m_objectStoreId);
1288     if (p == limit)
1289         return 0;
1290     return decodeByte(p, limit, result->m_metaDataType);
1291 }
1292
1293 Vector<char> ObjectStoreMetaDataKey::encode(int64_t databaseId, int64_t objectStoreId, unsigned char metaDataType)
1294 {
1295     KeyPrefix prefix(databaseId);
1296     Vector<char> ret = prefix.encode();
1297     ret.append(encodeByte(ObjectStoreMetaDataTypeByte));
1298     ret.append(encodeVarInt(objectStoreId));
1299     ret.append(encodeByte(metaDataType));
1300     return ret;
1301 }
1302
1303 Vector<char> ObjectStoreMetaDataKey::encodeMaxKey(int64_t databaseId)
1304 {
1305     return encode(databaseId, INT64_MAX, ObjectMetaDataTypeMaximum);
1306 }
1307
1308 Vector<char> ObjectStoreMetaDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1309 {
1310     return encode(databaseId, objectStoreId, ObjectMetaDataTypeMaximum);
1311 }
1312
1313 int64_t ObjectStoreMetaDataKey::objectStoreId() const
1314 {
1315     ASSERT(m_objectStoreId >= 0);
1316     return m_objectStoreId;
1317 }
1318 unsigned char ObjectStoreMetaDataKey::metaDataType() const
1319 {
1320     return m_metaDataType;
1321 }
1322
1323 int ObjectStoreMetaDataKey::compare(const ObjectStoreMetaDataKey& other)
1324 {
1325     ASSERT(m_objectStoreId >= 0);
1326     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1327         return x;
1328     int64_t result = m_metaDataType - other.m_metaDataType;
1329     if (result < 0)
1330         return -1;
1331     return (result > 0) ? 1 : result;
1332 }
1333
1334 IndexMetaDataKey::IndexMetaDataKey()
1335     : m_objectStoreId(-1)
1336     , m_indexId(-1)
1337     , m_metaDataType(0)
1338 {
1339 }
1340
1341 const char* IndexMetaDataKey::decode(const char* start, const char* limit, IndexMetaDataKey* result)
1342 {
1343     KeyPrefix prefix;
1344     const char* p = KeyPrefix::decode(start, limit, &prefix);
1345     if (!p)
1346         return 0;
1347     ASSERT(prefix.m_databaseId);
1348     ASSERT(!prefix.m_objectStoreId);
1349     ASSERT(!prefix.m_indexId);
1350     if (p == limit)
1351         return 0;
1352     unsigned char typeByte = 0;
1353     p = decodeByte(p, limit, typeByte);
1354     ASSERT_UNUSED(typeByte, typeByte == IndexMetaDataTypeByte);
1355     if (p == limit)
1356         return 0;
1357     p = decodeVarInt(p, limit, result->m_objectStoreId);
1358     if (!p)
1359         return 0;
1360     p = decodeVarInt(p, limit, result->m_indexId);
1361     if (!p)
1362         return 0;
1363     if (p == limit)
1364         return 0;
1365     return decodeByte(p, limit, result->m_metaDataType);
1366 }
1367
1368 Vector<char> IndexMetaDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, unsigned char metaDataType)
1369 {
1370     KeyPrefix prefix(databaseId);
1371     Vector<char> ret = prefix.encode();
1372     ret.append(encodeByte(IndexMetaDataTypeByte));
1373     ret.append(encodeVarInt(objectStoreId));
1374     ret.append(encodeVarInt(indexId));
1375     ret.append(encodeByte(metaDataType));
1376     return ret;
1377 }
1378
1379 Vector<char> IndexMetaDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1380 {
1381     return encode(databaseId, objectStoreId, INT64_MAX, IndexMetaDataTypeMaximum);
1382 }
1383
1384 Vector<char> IndexMetaDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1385 {
1386     return encode(databaseId, objectStoreId, indexId, IndexMetaDataTypeMaximum);
1387 }
1388
1389 int IndexMetaDataKey::compare(const IndexMetaDataKey& other)
1390 {
1391     ASSERT(m_objectStoreId >= 0);
1392     ASSERT(m_indexId >= 0);
1393
1394     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1395         return x;
1396     if (int x = compareInts(m_indexId, other.m_indexId))
1397         return x;
1398     return m_metaDataType - other.m_metaDataType;
1399 }
1400
1401 int64_t IndexMetaDataKey::indexId() const
1402 {
1403     ASSERT(m_indexId >= 0);
1404     return m_indexId;
1405 }
1406
1407 ObjectStoreFreeListKey::ObjectStoreFreeListKey()
1408     : m_objectStoreId(-1)
1409 {
1410 }
1411
1412 const char* ObjectStoreFreeListKey::decode(const char* start, const char* limit, ObjectStoreFreeListKey* result)
1413 {
1414     KeyPrefix prefix;
1415     const char* p = KeyPrefix::decode(start, limit, &prefix);
1416     if (!p)
1417         return 0;
1418     ASSERT(prefix.m_databaseId);
1419     ASSERT(!prefix.m_objectStoreId);
1420     ASSERT(!prefix.m_indexId);
1421     if (p == limit)
1422         return 0;
1423     unsigned char typeByte = 0;
1424     p = decodeByte(p, limit, typeByte);
1425     ASSERT_UNUSED(typeByte, typeByte == ObjectStoreFreeListTypeByte);
1426     if (p == limit)
1427         return 0;
1428     return decodeVarInt(p, limit, result->m_objectStoreId);
1429 }
1430
1431 Vector<char> ObjectStoreFreeListKey::encode(int64_t databaseId, int64_t objectStoreId)
1432 {
1433     KeyPrefix prefix(databaseId);
1434     Vector<char> ret = prefix.encode();
1435     ret.append(encodeByte(ObjectStoreFreeListTypeByte));
1436     ret.append(encodeVarInt(objectStoreId));
1437     return ret;
1438 }
1439
1440 Vector<char> ObjectStoreFreeListKey::encodeMaxKey(int64_t databaseId)
1441 {
1442     return encode(databaseId, INT64_MAX);
1443 }
1444
1445 int64_t ObjectStoreFreeListKey::objectStoreId() const
1446 {
1447     ASSERT(m_objectStoreId >= 0);
1448     return m_objectStoreId;
1449 }
1450
1451 int ObjectStoreFreeListKey::compare(const ObjectStoreFreeListKey& other)
1452 {
1453     // FIXME: It may seem strange that we're not comparing database id's,
1454     // but that comparison will have been made earlier.
1455     // We should probably make this more clear, though...
1456     ASSERT(m_objectStoreId >= 0);
1457     return compareInts(m_objectStoreId, other.m_objectStoreId);
1458 }
1459
1460 IndexFreeListKey::IndexFreeListKey()
1461     : m_objectStoreId(-1)
1462     , m_indexId(-1)
1463 {
1464 }
1465
1466 const char* IndexFreeListKey::decode(const char* start, const char* limit, IndexFreeListKey* result)
1467 {
1468     KeyPrefix prefix;
1469     const char* p = KeyPrefix::decode(start, limit, &prefix);
1470     if (!p)
1471         return 0;
1472     ASSERT(prefix.m_databaseId);
1473     ASSERT(!prefix.m_objectStoreId);
1474     ASSERT(!prefix.m_indexId);
1475     if (p == limit)
1476         return 0;
1477     unsigned char typeByte = 0;
1478     p = decodeByte(p, limit, typeByte);
1479     ASSERT_UNUSED(typeByte, typeByte == IndexFreeListTypeByte);
1480     if (p == limit)
1481         return 0;
1482     p = decodeVarInt(p, limit, result->m_objectStoreId);
1483     if (!p)
1484         return 0;
1485     return decodeVarInt(p, limit, result->m_indexId);
1486 }
1487
1488 Vector<char> IndexFreeListKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1489 {
1490     KeyPrefix prefix(databaseId);
1491     Vector<char> ret = prefix.encode();
1492     ret.append(encodeByte(IndexFreeListTypeByte));
1493     ret.append(encodeVarInt(objectStoreId));
1494     ret.append(encodeVarInt(indexId));
1495     return ret;
1496 }
1497
1498 Vector<char> IndexFreeListKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId)
1499 {
1500     return encode(databaseId, objectStoreId, INT64_MAX);
1501 }
1502
1503 int IndexFreeListKey::compare(const IndexFreeListKey& other)
1504 {
1505     ASSERT(m_objectStoreId >= 0);
1506     ASSERT(m_indexId >= 0);
1507     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1508         return x;
1509     return compareInts(m_indexId, other.m_indexId);
1510 }
1511
1512 int64_t IndexFreeListKey::objectStoreId() const
1513 {
1514     ASSERT(m_objectStoreId >= 0);
1515     return m_objectStoreId;
1516 }
1517
1518 int64_t IndexFreeListKey::indexId() const
1519 {
1520     ASSERT(m_indexId >= 0);
1521     return m_indexId;
1522 }
1523
1524 // FIXME: We never use this to look up object store ids, because a mapping
1525 // is kept in the IDBDatabaseBackendImpl. Can the mapping become unreliable?
1526 // Can we remove this?
1527 const char* ObjectStoreNamesKey::decode(const char* start, const char* limit, ObjectStoreNamesKey* result)
1528 {
1529     KeyPrefix prefix;
1530     const char* p = KeyPrefix::decode(start, limit, &prefix);
1531     if (!p)
1532         return 0;
1533     ASSERT(prefix.m_databaseId);
1534     ASSERT(!prefix.m_objectStoreId);
1535     ASSERT(!prefix.m_indexId);
1536     if (p == limit)
1537         return 0;
1538     unsigned char typeByte = 0;
1539     p = decodeByte(p, limit, typeByte);
1540     ASSERT_UNUSED(typeByte, typeByte == ObjectStoreNamesTypeByte);
1541     return decodeStringWithLength(p, limit, result->m_objectStoreName);
1542 }
1543
1544 Vector<char> ObjectStoreNamesKey::encode(int64_t databaseId, const String& objectStoreName)
1545 {
1546     KeyPrefix prefix(databaseId);
1547     Vector<char> ret = prefix.encode();
1548     ret.append(encodeByte(ObjectStoreNamesTypeByte));
1549     ret.append(encodeStringWithLength(objectStoreName));
1550     return ret;
1551 }
1552
1553 int ObjectStoreNamesKey::compare(const ObjectStoreNamesKey& other)
1554 {
1555     return codePointCompare(m_objectStoreName, other.m_objectStoreName);
1556 }
1557
1558 IndexNamesKey::IndexNamesKey()
1559     : m_objectStoreId(-1)
1560 {
1561 }
1562
1563 // FIXME: We never use this to look up index ids, because a mapping
1564 // is kept at a higher level.
1565 const char* IndexNamesKey::decode(const char* start, const char* limit, IndexNamesKey* result)
1566 {
1567     KeyPrefix prefix;
1568     const char* p = KeyPrefix::decode(start, limit, &prefix);
1569     if (!p)
1570         return 0;
1571     ASSERT(prefix.m_databaseId);
1572     ASSERT(!prefix.m_objectStoreId);
1573     ASSERT(!prefix.m_indexId);
1574     if (p == limit)
1575         return 0;
1576     unsigned char typeByte = 0;
1577     p = decodeByte(p, limit, typeByte);
1578     ASSERT_UNUSED(typeByte, typeByte == IndexNamesKeyTypeByte);
1579     if (p == limit)
1580         return 0;
1581     p = decodeVarInt(p, limit, result->m_objectStoreId);
1582     if (!p)
1583         return 0;
1584     return decodeStringWithLength(p, limit, result->m_indexName);
1585 }
1586
1587 Vector<char> IndexNamesKey::encode(int64_t databaseId, int64_t objectStoreId, const String& indexName)
1588 {
1589     KeyPrefix prefix(databaseId);
1590     Vector<char> ret = prefix.encode();
1591     ret.append(encodeByte(IndexNamesKeyTypeByte));
1592     ret.append(encodeVarInt(objectStoreId));
1593     ret.append(encodeStringWithLength(indexName));
1594     return ret;
1595 }
1596
1597 int IndexNamesKey::compare(const IndexNamesKey& other)
1598 {
1599     ASSERT(m_objectStoreId >= 0);
1600     if (int x = compareInts(m_objectStoreId, other.m_objectStoreId))
1601         return x;
1602     return codePointCompare(m_indexName, other.m_indexName);
1603 }
1604
1605 const char* ObjectStoreDataKey::decode(const char* start, const char* end, ObjectStoreDataKey* result)
1606 {
1607     KeyPrefix prefix;
1608     const char* p = KeyPrefix::decode(start, end, &prefix);
1609     if (!p)
1610         return 0;
1611     ASSERT(prefix.m_databaseId);
1612     ASSERT(prefix.m_objectStoreId);
1613     ASSERT(prefix.m_indexId == SpecialIndexNumber);
1614     if (p == end)
1615         return 0;
1616     return extractEncodedIDBKey(p, end, &result->m_encodedUserKey);
1617 }
1618
1619 Vector<char> ObjectStoreDataKey::encode(int64_t databaseId, int64_t objectStoreId, const Vector<char> encodedUserKey)
1620 {
1621     KeyPrefix prefix(KeyPrefix::createWithSpecialIndex(databaseId, objectStoreId, SpecialIndexNumber));
1622     Vector<char> ret = prefix.encode();
1623     ret.append(encodedUserKey);
1624
1625     return ret;
1626 }
1627
1628 Vector<char> ObjectStoreDataKey::encode(int64_t databaseId, int64_t objectStoreId, const IDBKey& userKey)
1629 {
1630     return encode(databaseId, objectStoreId, encodeIDBKey(userKey));
1631 }
1632
1633 int ObjectStoreDataKey::compare(const ObjectStoreDataKey& other, bool& ok)
1634 {
1635     return compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey, ok);
1636 }
1637
1638 PassRefPtr<IDBKey> ObjectStoreDataKey::userKey() const
1639 {
1640     RefPtr<IDBKey> key;
1641     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1642     return key;
1643 }
1644
1645 const int64_t ObjectStoreDataKey::SpecialIndexNumber = ObjectStoreDataIndexId;
1646
1647 const char* ExistsEntryKey::decode(const char* start, const char* end, ExistsEntryKey* result)
1648 {
1649     KeyPrefix prefix;
1650     const char* p = KeyPrefix::decode(start, end, &prefix);
1651     if (!p)
1652         return 0;
1653     ASSERT(prefix.m_databaseId);
1654     ASSERT(prefix.m_objectStoreId);
1655     ASSERT(prefix.m_indexId == SpecialIndexNumber);
1656     if (p == end)
1657         return 0;
1658     return extractEncodedIDBKey(p, end, &result->m_encodedUserKey);
1659 }
1660
1661 Vector<char> ExistsEntryKey::encode(int64_t databaseId, int64_t objectStoreId, const Vector<char>& encodedKey)
1662 {
1663     KeyPrefix prefix(KeyPrefix::createWithSpecialIndex(databaseId, objectStoreId, SpecialIndexNumber));
1664     Vector<char> ret = prefix.encode();
1665     ret.append(encodedKey);
1666     return ret;
1667 }
1668
1669 Vector<char> ExistsEntryKey::encode(int64_t databaseId, int64_t objectStoreId, const IDBKey& userKey)
1670 {
1671     return encode(databaseId, objectStoreId, encodeIDBKey(userKey));
1672 }
1673
1674 int ExistsEntryKey::compare(const ExistsEntryKey& other, bool& ok)
1675 {
1676     return compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey, ok);
1677 }
1678
1679 PassRefPtr<IDBKey> ExistsEntryKey::userKey() const
1680 {
1681     RefPtr<IDBKey> key;
1682     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1683     return key;
1684 }
1685
1686 const int64_t ExistsEntryKey::SpecialIndexNumber = ExistsEntryIndexId;
1687
1688 IndexDataKey::IndexDataKey()
1689     : m_databaseId(-1)
1690     , m_objectStoreId(-1)
1691     , m_indexId(-1)
1692     , m_sequenceNumber(-1)
1693 {
1694 }
1695
1696 const char* IndexDataKey::decode(const char* start, const char* limit, IndexDataKey* result)
1697 {
1698     KeyPrefix prefix;
1699     const char* p = KeyPrefix::decode(start, limit, &prefix);
1700     if (!p)
1701         return 0;
1702     ASSERT(prefix.m_databaseId);
1703     ASSERT(prefix.m_objectStoreId);
1704     ASSERT(prefix.m_indexId >= MinimumIndexId);
1705     result->m_databaseId = prefix.m_databaseId;
1706     result->m_objectStoreId = prefix.m_objectStoreId;
1707     result->m_indexId = prefix.m_indexId;
1708     result->m_sequenceNumber = -1;
1709     result->m_encodedPrimaryKey = minIDBKey();
1710
1711     p = extractEncodedIDBKey(p, limit, &result->m_encodedUserKey);
1712     if (!p)
1713         return 0;
1714
1715     // [optional] sequence number
1716     if (p == limit)
1717         return p;
1718     p =  decodeVarInt(p, limit, result->m_sequenceNumber);
1719     if (!p)
1720         return 0;
1721
1722     // [optional] primary key
1723     if (p == limit)
1724         return p;
1725     p = extractEncodedIDBKey(p, limit, &result->m_encodedPrimaryKey);
1726     if (!p)
1727         return 0;
1728
1729     return p;
1730 }
1731
1732 Vector<char> IndexDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const Vector<char>& encodedUserKey, const Vector<char>& encodedPrimaryKey, int64_t sequenceNumber)
1733 {
1734     KeyPrefix prefix(databaseId, objectStoreId, indexId);
1735     Vector<char> ret = prefix.encode();
1736     ret.append(encodedUserKey);
1737     ret.append(encodeVarInt(sequenceNumber));
1738     ret.append(encodedPrimaryKey);
1739     return ret;
1740 }
1741
1742 Vector<char> IndexDataKey::encode(int64_t databaseId, int64_t objectStoreId, int64_t indexId, const IDBKey& userKey)
1743 {
1744     return encode(databaseId, objectStoreId, indexId, encodeIDBKey(userKey), minIDBKey());
1745 }
1746
1747 Vector<char> IndexDataKey::encodeMinKey(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1748 {
1749     return encode(databaseId, objectStoreId, indexId, minIDBKey(), minIDBKey());
1750 }
1751
1752 Vector<char> IndexDataKey::encodeMaxKey(int64_t databaseId, int64_t objectStoreId, int64_t indexId)
1753 {
1754     return encode(databaseId, objectStoreId, indexId, maxIDBKey(), maxIDBKey(), INT64_MAX);
1755 }
1756
1757 int IndexDataKey::compare(const IndexDataKey& other, bool ignoreDuplicates, bool& ok)
1758 {
1759     ASSERT(m_databaseId >= 0);
1760     ASSERT(m_objectStoreId >= 0);
1761     ASSERT(m_indexId >= 0);
1762     int result = compareEncodedIDBKeys(m_encodedUserKey, other.m_encodedUserKey, ok);
1763     if (!ok || result)
1764         return result;
1765     if (ignoreDuplicates)
1766         return 0;
1767     result = compareEncodedIDBKeys(m_encodedPrimaryKey, other.m_encodedPrimaryKey, ok);
1768     if (!ok || result)
1769         return result;
1770     return compareInts(m_sequenceNumber, other.m_sequenceNumber);
1771 }
1772
1773 int64_t IndexDataKey::databaseId() const
1774 {
1775     ASSERT(m_databaseId >= 0);
1776     return m_databaseId;
1777 }
1778
1779 int64_t IndexDataKey::objectStoreId() const
1780 {
1781     ASSERT(m_objectStoreId >= 0);
1782     return m_objectStoreId;
1783 }
1784
1785 int64_t IndexDataKey::indexId() const
1786 {
1787     ASSERT(m_indexId >= 0);
1788     return m_indexId;
1789 }
1790
1791 PassRefPtr<IDBKey> IndexDataKey::userKey() const
1792 {
1793     RefPtr<IDBKey> key;
1794     decodeIDBKey(m_encodedUserKey.begin(), m_encodedUserKey.end(), key);
1795     return key;
1796 }
1797
1798 PassRefPtr<IDBKey> IndexDataKey::primaryKey() const
1799 {
1800     RefPtr<IDBKey> key;
1801     decodeIDBKey(m_encodedPrimaryKey.begin(), m_encodedPrimaryKey.end(), key);
1802     return key;
1803 }
1804
1805 } // namespace IDBLevelDBCoding
1806 } // namespace WebCore
1807
1808 #endif // USE(LEVELDB)
1809 #endif // ENABLE(INDEXED_DATABASE)