Speed up HashTable decoding by reserving capacity and avoiding rehashing
[WebKit-https.git] / Source / WebKit / Platform / IPC / ArgumentCoders.h
1 /*
2  * Copyright (C) 2010-2017 Apple 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  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #pragma once
27
28 #include "Decoder.h"
29 #include "Encoder.h"
30 #include <utility>
31 #include <wtf/Forward.h>
32 #include <wtf/MonotonicTime.h>
33 #include <wtf/SHA1.h>
34 #include <wtf/Unexpected.h>
35 #include <wtf/WallTime.h>
36
37 namespace IPC {
38
39 // An argument coder works on POD types
40 template<typename T> struct SimpleArgumentCoder {
41     static void encode(Encoder& encoder, const T& t)
42     {
43         encoder.encodeFixedLengthData(reinterpret_cast<const uint8_t*>(&t), sizeof(T), alignof(T));
44     }
45
46     static bool decode(Decoder& decoder, T& t)
47     {
48         return decoder.decodeFixedLengthData(reinterpret_cast<uint8_t*>(&t), sizeof(T), alignof(T));
49     }
50 };
51
52 template<typename T> struct ArgumentCoder<OptionSet<T>> {
53     static void encode(Encoder& encoder, const OptionSet<T>& optionSet)
54     {
55         encoder << (static_cast<uint64_t>(optionSet.toRaw()));
56     }
57
58     static bool decode(Decoder& decoder, OptionSet<T>& optionSet)
59     {
60         uint64_t value;
61         if (!decoder.decode(value))
62             return false;
63
64         optionSet = OptionSet<T>::fromRaw(value);
65         return true;
66     }
67
68     static Optional<OptionSet<T>> decode(Decoder& decoder)
69     {
70         Optional<uint64_t> value;
71         decoder >> value;
72         if (!value)
73             return WTF::nullopt;
74         return OptionSet<T>::fromRaw(*value);
75     }
76 };
77
78 template<typename T> struct ArgumentCoder<Optional<T>> {
79     static void encode(Encoder& encoder, const Optional<T>& optional)
80     {
81         if (!optional) {
82             encoder << false;
83             return;
84         }
85
86         encoder << true;
87         encoder << optional.value();
88     }
89
90     static bool decode(Decoder& decoder, Optional<T>& optional)
91     {
92         bool isEngaged;
93         if (!decoder.decode(isEngaged))
94             return false;
95
96         if (!isEngaged) {
97             optional = WTF::nullopt;
98             return true;
99         }
100
101         T value;
102         if (!decoder.decode(value))
103             return false;
104
105         optional = WTFMove(value);
106         return true;
107     }
108     
109     static Optional<Optional<T>> decode(Decoder& decoder)
110     {
111         Optional<bool> isEngaged;
112         decoder >> isEngaged;
113         if (!isEngaged)
114             return WTF::nullopt;
115         if (*isEngaged) {
116             Optional<T> value;
117             decoder >> value;
118             if (!value)
119                 return WTF::nullopt;
120             return Optional<Optional<T>>(WTFMove(*value));
121         }
122         return Optional<Optional<T>>(Optional<T>(WTF::nullopt));
123     }
124 };
125
126 template<typename T, typename U> struct ArgumentCoder<std::pair<T, U>> {
127     static void encode(Encoder& encoder, const std::pair<T, U>& pair)
128     {
129         encoder << pair.first << pair.second;
130     }
131
132     static bool decode(Decoder& decoder, std::pair<T, U>& pair)
133     {
134         T first;
135         if (!decoder.decode(first))
136             return false;
137
138         U second;
139         if (!decoder.decode(second))
140             return false;
141
142         pair.first = first;
143         pair.second = second;
144         return true;
145     }
146
147     static Optional<std::pair<T, U>> decode(Decoder& decoder)
148     {
149         Optional<T> first;
150         decoder >> first;
151         if (!first)
152             return WTF::nullopt;
153         
154         Optional<U> second;
155         decoder >> second;
156         if (!second)
157             return WTF::nullopt;
158         
159         return {{ WTFMove(*first), WTFMove(*second) }};
160     }
161 };
162
163 template<size_t index, typename... Elements>
164 struct TupleEncoder {
165     static void encode(Encoder& encoder, const std::tuple<Elements...>& tuple)
166     {
167         encoder << std::get<sizeof...(Elements) - index>(tuple);
168         TupleEncoder<index - 1, Elements...>::encode(encoder, tuple);
169     }
170 };
171
172 template<typename... Elements>
173 struct TupleEncoder<0, Elements...> {
174     static void encode(Encoder&, const std::tuple<Elements...>&)
175     {
176     }
177 };
178
179 template <typename T, typename... Elements, size_t... Indices>
180 auto tupleFromTupleAndObject(T&& object, std::tuple<Elements...>&& tuple, std::index_sequence<Indices...>)
181 {
182     return std::make_tuple(WTFMove(object), WTFMove(std::get<Indices>(tuple))...);
183 }
184
185 template <typename T, typename... Elements>
186 auto tupleFromTupleAndObject(T&& object, std::tuple<Elements...>&& tuple)
187 {
188     return tupleFromTupleAndObject(WTFMove(object), WTFMove(tuple), std::index_sequence_for<Elements...>());
189 }
190
191 template<typename Type, typename... Types>
192 struct TupleDecoderImpl {
193     static Optional<std::tuple<Type, Types...>> decode(Decoder& decoder)
194     {
195         Optional<Type> optional;
196         decoder >> optional;
197         if (!optional)
198             return WTF::nullopt;
199
200         Optional<std::tuple<Types...>> subTuple = TupleDecoderImpl<Types...>::decode(decoder);
201         if (!subTuple)
202             return WTF::nullopt;
203
204         return tupleFromTupleAndObject(WTFMove(*optional), WTFMove(*subTuple));
205     }
206 };
207
208 template<typename Type>
209 struct TupleDecoderImpl<Type> {
210     static Optional<std::tuple<Type>> decode(Decoder& decoder)
211     {
212         Optional<Type> optional;
213         decoder >> optional;
214         if (!optional)
215             return WTF::nullopt;
216         return std::make_tuple(WTFMove(*optional));
217     }
218 };
219
220 template<size_t size, typename... Elements>
221 struct TupleDecoder {
222     static Optional<std::tuple<Elements...>> decode(Decoder& decoder)
223     {
224         return TupleDecoderImpl<Elements...>::decode(decoder);
225     }
226 };
227
228 template<>
229 struct TupleDecoder<0> {
230     static Optional<std::tuple<>> decode(Decoder& decoder)
231     {
232         return std::make_tuple();
233     }
234 };
235
236 template<typename... Elements> struct ArgumentCoder<std::tuple<Elements...>> {
237     static void encode(Encoder& encoder, const std::tuple<Elements...>& tuple)
238     {
239         TupleEncoder<sizeof...(Elements), Elements...>::encode(encoder, tuple);
240     }
241
242     static Optional<std::tuple<Elements...>> decode(Decoder& decoder)
243     {
244         return TupleDecoder<sizeof...(Elements), Elements...>::decode(decoder);
245     }
246 };
247
248 template<typename KeyType, typename ValueType> struct ArgumentCoder<WTF::KeyValuePair<KeyType, ValueType>> {
249     static void encode(Encoder& encoder, const WTF::KeyValuePair<KeyType, ValueType>& pair)
250     {
251         encoder << pair.key << pair.value;
252     }
253
254     static bool decode(Decoder& decoder, WTF::KeyValuePair<KeyType, ValueType>& pair)
255     {
256         KeyType key;
257         if (!decoder.decode(key))
258             return false;
259
260         ValueType value;
261         if (!decoder.decode(value))
262             return false;
263
264         pair.key = key;
265         pair.value = value;
266         return true;
267     }
268 };
269
270 template<bool fixedSizeElements, typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> struct VectorArgumentCoder;
271
272 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> struct VectorArgumentCoder<false, T, inlineCapacity, OverflowHandler, minCapacity> {
273     static void encode(Encoder& encoder, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& vector)
274     {
275         encoder << static_cast<uint64_t>(vector.size());
276         for (size_t i = 0; i < vector.size(); ++i)
277             encoder << vector[i];
278     }
279
280     static bool decode(Decoder& decoder, Vector<T, inlineCapacity, OverflowHandler, minCapacity>& vector)
281     {
282         Optional<Vector<T, inlineCapacity, OverflowHandler, minCapacity>> optional;
283         decoder >> optional;
284         if (!optional)
285             return false;
286         vector = WTFMove(*optional);
287         return true;
288     }
289
290     static Optional<Vector<T, inlineCapacity, OverflowHandler, minCapacity>> decode(Decoder& decoder)
291     {
292         uint64_t size;
293         if (!decoder.decode(size))
294             return WTF::nullopt;
295
296         Vector<T, inlineCapacity, OverflowHandler, minCapacity> vector;
297         for (size_t i = 0; i < size; ++i) {
298             Optional<T> element;
299             decoder >> element;
300             if (!element)
301                 return WTF::nullopt;
302             vector.append(WTFMove(*element));
303         }
304         vector.shrinkToFit();
305         return vector;
306     }
307 };
308
309 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> struct VectorArgumentCoder<true, T, inlineCapacity, OverflowHandler, minCapacity> {
310     static void encode(Encoder& encoder, const Vector<T, inlineCapacity, OverflowHandler, minCapacity>& vector)
311     {
312         encoder << static_cast<uint64_t>(vector.size());
313         encoder.encodeFixedLengthData(reinterpret_cast<const uint8_t*>(vector.data()), vector.size() * sizeof(T), alignof(T));
314     }
315     
316     static bool decode(Decoder& decoder, Vector<T, inlineCapacity, OverflowHandler, minCapacity>& vector)
317     {
318         uint64_t size;
319         if (!decoder.decode(size))
320             return false;
321
322         // Since we know the total size of the elements, we can allocate the vector in
323         // one fell swoop. Before allocating we must however make sure that the decoder buffer
324         // is big enough.
325         if (!decoder.bufferIsLargeEnoughToContain<T>(size)) {
326             decoder.markInvalid();
327             return false;
328         }
329
330         Vector<T, inlineCapacity, OverflowHandler, minCapacity> temp;
331         temp.grow(size);
332
333         decoder.decodeFixedLengthData(reinterpret_cast<uint8_t*>(temp.data()), size * sizeof(T), alignof(T));
334
335         vector.swap(temp);
336         return true;
337     }
338     
339     static Optional<Vector<T, inlineCapacity, OverflowHandler, minCapacity>> decode(Decoder& decoder)
340     {
341         uint64_t size;
342         if (!decoder.decode(size))
343             return WTF::nullopt;
344         
345         // Since we know the total size of the elements, we can allocate the vector in
346         // one fell swoop. Before allocating we must however make sure that the decoder buffer
347         // is big enough.
348         if (!decoder.bufferIsLargeEnoughToContain<T>(size)) {
349             decoder.markInvalid();
350             return WTF::nullopt;
351         }
352         
353         Vector<T, inlineCapacity, OverflowHandler, minCapacity> vector;
354         vector.grow(size);
355         
356         decoder.decodeFixedLengthData(reinterpret_cast<uint8_t*>(vector.data()), size * sizeof(T), alignof(T));
357         
358         return vector;
359     }
360 };
361
362 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity> struct ArgumentCoder<Vector<T, inlineCapacity, OverflowHandler, minCapacity>> : VectorArgumentCoder<std::is_arithmetic<T>::value, T, inlineCapacity, OverflowHandler, minCapacity> { };
363
364 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> struct ArgumentCoder<HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>> {
365     typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> HashMapType;
366
367     static void encode(Encoder& encoder, const HashMapType& hashMap)
368     {
369         encoder << static_cast<uint32_t>(hashMap.size());
370         for (typename HashMapType::const_iterator it = hashMap.begin(), end = hashMap.end(); it != end; ++it)
371             encoder << *it;
372     }
373
374     static Optional<HashMapType> decode(Decoder& decoder)
375     {
376         uint32_t hashMapSize;
377         if (!decoder.decode(hashMapSize))
378             return WTF::nullopt;
379
380         HashMapType hashMap;
381         hashMap.reserveInitialCapacity(hashMapSize);
382         for (uint32_t i = 0; i < hashMapSize; ++i) {
383             Optional<KeyArg> key;
384             decoder >> key;
385             if (UNLIKELY(!key))
386                 return WTF::nullopt;
387
388             Optional<MappedArg> value;
389             decoder >> value;
390             if (UNLIKELY(!value))
391                 return WTF::nullopt;
392
393             if (UNLIKELY(!hashMap.add(WTFMove(*key), WTFMove(*value)).isNewEntry)) {
394                 // The hash map already has the specified key, bail.
395                 decoder.markInvalid();
396                 return WTF::nullopt;
397             }
398         }
399
400         return WTFMove(hashMap);
401     }
402
403     static bool decode(Decoder& decoder, HashMapType& hashMap)
404     {
405         Optional<HashMapType> tempHashMap;
406         decoder >> tempHashMap;
407         if (!tempHashMap)
408             return false;
409         hashMap.swap(*tempHashMap);
410         return true;
411     }
412 };
413
414 template<typename KeyArg, typename HashArg, typename KeyTraitsArg> struct ArgumentCoder<HashSet<KeyArg, HashArg, KeyTraitsArg>> {
415     typedef HashSet<KeyArg, HashArg, KeyTraitsArg> HashSetType;
416
417     static void encode(Encoder& encoder, const HashSetType& hashSet)
418     {
419         encoder << static_cast<uint64_t>(hashSet.size());
420         for (typename HashSetType::const_iterator it = hashSet.begin(), end = hashSet.end(); it != end; ++it)
421             encoder << *it;
422     }
423
424     static bool decode(Decoder& decoder, HashSetType& hashSet)
425     {
426         Optional<HashSetType> tempHashSet;
427         decoder >> tempHashSet;
428         if (!tempHashSet)
429             return false;
430
431         hashSet.swap(tempHashSet.value());
432         return true;
433     }
434
435     static Optional<HashSetType> decode(Decoder& decoder)
436     {
437         uint64_t hashSetSize;
438         if (!decoder.decode(hashSetSize))
439             return WTF::nullopt;
440
441         HashSetType hashSet;
442         for (uint64_t i = 0; i < hashSetSize; ++i) {
443             Optional<KeyArg> key;
444             decoder >> key;
445             if (!key)
446                 return WTF::nullopt;
447
448             if (!hashSet.add(WTFMove(key.value())).isNewEntry) {
449                 // The hash set already has the specified key, bail.
450                 decoder.markInvalid();
451                 return WTF::nullopt;
452             }
453         }
454
455         return hashSet;
456     }
457 };
458
459 template<typename KeyArg, typename HashArg, typename KeyTraitsArg> struct ArgumentCoder<HashCountedSet<KeyArg, HashArg, KeyTraitsArg>> {
460     typedef HashCountedSet<KeyArg, HashArg, KeyTraitsArg> HashCountedSetType;
461     
462     static void encode(Encoder& encoder, const HashCountedSetType& hashCountedSet)
463     {
464         encoder << static_cast<uint64_t>(hashCountedSet.size());
465         
466         for (auto entry : hashCountedSet) {
467             encoder << entry.key;
468             encoder << entry.value;
469         }
470     }
471     
472     static bool decode(Decoder& decoder, HashCountedSetType& hashCountedSet)
473     {
474         uint64_t hashCountedSetSize;
475         if (!decoder.decode(hashCountedSetSize))
476             return false;
477         
478         HashCountedSetType tempHashCountedSet;
479         for (uint64_t i = 0; i < hashCountedSetSize; ++i) {
480             KeyArg key;
481             if (!decoder.decode(key))
482                 return false;
483             
484             unsigned count;
485             if (!decoder.decode(count))
486                 return false;
487             
488             if (!tempHashCountedSet.add(key, count).isNewEntry) {
489                 // The hash counted set already has the specified key, bail.
490                 decoder.markInvalid();
491                 return false;
492             }
493         }
494         
495         hashCountedSet.swap(tempHashCountedSet);
496         return true;
497     }
498 };
499
500 template<typename ValueType, typename ErrorType> struct ArgumentCoder<Expected<ValueType, ErrorType>> {
501     static void encode(Encoder& encoder, const Expected<ValueType, ErrorType>& expected)
502     {
503         if (!expected.has_value()) {
504             encoder << false;
505             encoder << expected.error();
506             return;
507         }
508         encoder << true;
509         encoder << expected.value();
510     }
511
512     static Optional<Expected<ValueType, ErrorType>> decode(Decoder& decoder)
513     {
514         Optional<bool> hasValue;
515         decoder >> hasValue;
516         if (!hasValue)
517             return WTF::nullopt;
518         
519         if (*hasValue) {
520             Optional<ValueType> value;
521             decoder >> value;
522             if (!value)
523                 return WTF::nullopt;
524             
525             Expected<ValueType, ErrorType> expected(WTFMove(*value));
526             return expected;
527         }
528         Optional<ErrorType> error;
529         decoder >> error;
530         if (!error)
531             return WTF::nullopt;
532         return { makeUnexpected(WTFMove(*error)) };
533     }
534 };
535
536 template<size_t index, typename... Types>
537 struct VariantCoder {
538     static void encode(Encoder& encoder, const WTF::Variant<Types...>& variant, unsigned i)
539     {
540         if (i == index) {
541             encoder << WTF::get<index>(variant);
542             return;
543         }
544         VariantCoder<index - 1, Types...>::encode(encoder, variant, i);
545     }
546     
547     static Optional<WTF::Variant<Types...>> decode(Decoder& decoder, unsigned i)
548     {
549         if (i == index) {
550             Optional<typename WTF::variant_alternative<index, WTF::Variant<Types...>>::type> optional;
551             decoder >> optional;
552             if (!optional)
553                 return WTF::nullopt;
554             return { WTFMove(*optional) };
555         }
556         return VariantCoder<index - 1, Types...>::decode(decoder, i);
557     }
558 };
559
560 template<typename... Types>
561 struct VariantCoder<0, Types...> {
562     static void encode(Encoder& encoder, const WTF::Variant<Types...>& variant, unsigned i)
563     {
564         ASSERT_UNUSED(i, !i);
565         encoder << WTF::get<0>(variant);
566     }
567     
568     static Optional<WTF::Variant<Types...>> decode(Decoder& decoder, unsigned i)
569     {
570         ASSERT_UNUSED(i, !i);
571         Optional<typename WTF::variant_alternative<0, WTF::Variant<Types...>>::type> optional;
572         decoder >> optional;
573         if (!optional)
574             return WTF::nullopt;
575         return { WTFMove(*optional) };
576     }
577 };
578
579 template<typename... Types> struct ArgumentCoder<WTF::Variant<Types...>> {
580     static void encode(Encoder& encoder, const WTF::Variant<Types...>& variant)
581     {
582         unsigned i = variant.index();
583         encoder << i;
584         VariantCoder<sizeof...(Types) - 1, Types...>::encode(encoder, variant, i);
585     }
586     
587     static Optional<WTF::Variant<Types...>> decode(Decoder& decoder)
588     {
589         Optional<unsigned> i;
590         decoder >> i;
591         if (!i)
592             return WTF::nullopt;
593         return VariantCoder<sizeof...(Types) - 1, Types...>::decode(decoder, *i);
594     }
595 };
596     
597 template<> struct ArgumentCoder<WallTime> {
598     static void encode(Encoder&, const WallTime&);
599     static bool decode(Decoder&, WallTime&);
600     static Optional<WallTime> decode(Decoder&);
601 };
602
603 template<> struct ArgumentCoder<AtomString> {
604     static void encode(Encoder&, const AtomString&);
605     static bool decode(Decoder&, AtomString&);
606 };
607
608 template<> struct ArgumentCoder<CString> {
609     static void encode(Encoder&, const CString&);
610     static bool decode(Decoder&, CString&);
611 };
612
613 template<> struct ArgumentCoder<String> {
614     static void encode(Encoder&, const String&);
615     static bool decode(Decoder&, String&);
616     static Optional<String> decode(Decoder&);
617 };
618
619 template<> struct ArgumentCoder<SHA1::Digest> {
620     static void encode(Encoder&, const SHA1::Digest&);
621     static bool decode(Decoder&, SHA1::Digest&);
622 };
623
624 } // namespace IPC