1// Copyright 2014 the V8 project 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#ifndef V8_UTIL_H_
6#define V8_UTIL_H_
7
8#include <assert.h>
9
10#include <map>
11#include <vector>
12
13#include "v8-function-callback.h"  // NOLINT(build/include_directory)
14#include "v8-persistent-handle.h"  // NOLINT(build/include_directory)
15
16/**
17 * Support for Persistent containers.
18 *
19 * C++11 embedders can use STL containers with Global values,
20 * but pre-C++11 does not support the required move semantic and hence
21 * may want these container classes.
22 */
23namespace v8 {
24
25template <typename K, typename V, typename Traits>
26class GlobalValueMap;
27
28typedef uintptr_t PersistentContainerValue;
29static const uintptr_t kPersistentContainerNotFound = 0;
30enum PersistentContainerCallbackType {
31  kNotWeak,
32  // These correspond to v8::WeakCallbackType
33  kWeakWithParameter,
34  kWeakWithInternalFields
35};
36
37/**
38 * A default trait implementation for PersistentValueMap which uses std::map
39 * as a backing map.
40 *
41 * Users will have to implement their own weak callbacks & dispose traits.
42 */
43template<typename K, typename V>
44class StdMapTraits {
45 public:
46  // STL map & related:
47  typedef std::map<K, PersistentContainerValue> Impl;
48  typedef typename Impl::iterator Iterator;
49
50  static bool Empty(Impl* impl) { return impl->empty(); }
51  static size_t Size(Impl* impl) { return impl->size(); }
52  static void Swap(Impl& a, Impl& b) { std::swap(a, b); }
53  static Iterator Begin(Impl* impl) { return impl->begin(); }
54  static Iterator End(Impl* impl) { return impl->end(); }
55  static K Key(Iterator it) { return it->first; }
56  static PersistentContainerValue Value(Iterator it) { return it->second; }
57  static PersistentContainerValue Set(Impl* impl, K key,
58      PersistentContainerValue value) {
59    std::pair<Iterator, bool> res = impl->insert(std::make_pair(key, value));
60    PersistentContainerValue old_value = kPersistentContainerNotFound;
61    if (!res.second) {
62      old_value = res.first->second;
63      res.first->second = value;
64    }
65    return old_value;
66  }
67  static PersistentContainerValue Get(Impl* impl, K key) {
68    Iterator it = impl->find(key);
69    if (it == impl->end()) return kPersistentContainerNotFound;
70    return it->second;
71  }
72  static PersistentContainerValue Remove(Impl* impl, K key) {
73    Iterator it = impl->find(key);
74    if (it == impl->end()) return kPersistentContainerNotFound;
75    PersistentContainerValue value = it->second;
76    impl->erase(it);
77    return value;
78  }
79};
80
81
82/**
83 * A default trait implementation for PersistentValueMap, which inherits
84 * a std:map backing map from StdMapTraits and holds non-weak persistent
85 * objects and has no special Dispose handling.
86 *
87 * You should not derive from this class, since MapType depends on the
88 * surrounding class, and hence a subclass cannot simply inherit the methods.
89 */
90template<typename K, typename V>
91class DefaultPersistentValueMapTraits : public StdMapTraits<K, V> {
92 public:
93  // Weak callback & friends:
94  static const PersistentContainerCallbackType kCallbackType = kNotWeak;
95  typedef PersistentValueMap<K, V, DefaultPersistentValueMapTraits<K, V> >
96      MapType;
97  typedef void WeakCallbackDataType;
98
99  static WeakCallbackDataType* WeakCallbackParameter(
100      MapType* map, const K& key, Local<V> value) {
101    return nullptr;
102  }
103  static MapType* MapFromWeakCallbackInfo(
104      const WeakCallbackInfo<WeakCallbackDataType>& data) {
105    return nullptr;
106  }
107  static K KeyFromWeakCallbackInfo(
108      const WeakCallbackInfo<WeakCallbackDataType>& data) {
109    return K();
110  }
111  static void DisposeCallbackData(WeakCallbackDataType* data) { }
112  static void Dispose(Isolate* isolate, Global<V> value, K key) {}
113};
114
115
116template <typename K, typename V>
117class DefaultGlobalMapTraits : public StdMapTraits<K, V> {
118 private:
119  template <typename T>
120  struct RemovePointer;
121
122 public:
123  // Weak callback & friends:
124  static const PersistentContainerCallbackType kCallbackType = kNotWeak;
125  typedef GlobalValueMap<K, V, DefaultGlobalMapTraits<K, V> > MapType;
126  typedef void WeakCallbackDataType;
127
128  static WeakCallbackDataType* WeakCallbackParameter(MapType* map, const K& key,
129                                                     Local<V> value) {
130    return nullptr;
131  }
132  static MapType* MapFromWeakCallbackInfo(
133      const WeakCallbackInfo<WeakCallbackDataType>& data) {
134    return nullptr;
135  }
136  static K KeyFromWeakCallbackInfo(
137      const WeakCallbackInfo<WeakCallbackDataType>& data) {
138    return K();
139  }
140  static void DisposeCallbackData(WeakCallbackDataType* data) {}
141  static void OnWeakCallback(
142      const WeakCallbackInfo<WeakCallbackDataType>& data) {}
143  static void Dispose(Isolate* isolate, Global<V> value, K key) {}
144  // This is a second pass callback, so SetSecondPassCallback cannot be called.
145  static void DisposeWeak(const WeakCallbackInfo<WeakCallbackDataType>& data) {}
146
147 private:
148  template <typename T>
149  struct RemovePointer<T*> {
150    typedef T Type;
151  };
152};
153
154
155/**
156 * A map wrapper that allows using Global as a mapped value.
157 * C++11 embedders don't need this class, as they can use Global
158 * directly in std containers.
159 *
160 * The map relies on a backing map, whose type and accessors are described
161 * by the Traits class. The backing map will handle values of type
162 * PersistentContainerValue, with all conversion into and out of V8
163 * handles being transparently handled by this class.
164 */
165template <typename K, typename V, typename Traits>
166class PersistentValueMapBase {
167 public:
168  Isolate* GetIsolate() { return isolate_; }
169
170  /**
171   * Return size of the map.
172   */
173  size_t Size() { return Traits::Size(&impl_); }
174
175  /**
176   * Return whether the map holds weak persistents.
177   */
178  bool IsWeak() { return Traits::kCallbackType != kNotWeak; }
179
180  /**
181   * Get value stored in map.
182   */
183  Local<V> Get(const K& key) {
184    V* p = FromVal(Traits::Get(&impl_, key));
185#ifdef V8_ENABLE_DIRECT_LOCAL
186    if (p == nullptr) return Local<V>();
187#endif
188    return Local<V>::New(isolate_, p);
189  }
190
191  /**
192   * Check whether a value is contained in the map.
193   */
194  bool Contains(const K& key) {
195    return Traits::Get(&impl_, key) != kPersistentContainerNotFound;
196  }
197
198  /**
199   * Get value stored in map and set it in returnValue.
200   * Return true if a value was found.
201   */
202  bool SetReturnValue(const K& key,
203      ReturnValue<Value> returnValue) {
204    return SetReturnValueFromVal(&returnValue, Traits::Get(&impl_, key));
205  }
206
207  /**
208   * Return value for key and remove it from the map.
209   */
210  Global<V> Remove(const K& key) {
211    return Release(Traits::Remove(&impl_, key)).Pass();
212  }
213
214  /**
215  * Traverses the map repeatedly,
216  * in case side effects of disposal cause insertions.
217  **/
218  void Clear() {
219    typedef typename Traits::Iterator It;
220    HandleScope handle_scope(isolate_);
221    // TODO(dcarney): figure out if this swap and loop is necessary.
222    while (!Traits::Empty(&impl_)) {
223      typename Traits::Impl impl;
224      Traits::Swap(impl_, impl);
225      for (It i = Traits::Begin(&impl); i != Traits::End(&impl); ++i) {
226        Traits::Dispose(isolate_, Release(Traits::Value(i)).Pass(),
227                        Traits::Key(i));
228      }
229    }
230  }
231
232  /**
233   * Helper class for GetReference/SetWithReference. Do not use outside
234   * that context.
235   */
236  class PersistentValueReference {
237   public:
238    PersistentValueReference() : value_(kPersistentContainerNotFound) { }
239    PersistentValueReference(const PersistentValueReference& other)
240        : value_(other.value_) { }
241
242    Local<V> NewLocal(Isolate* isolate) const {
243      return Local<V>::New(
244          isolate, internal::ValueHelper::SlotAsValue<V>(FromVal(value_)));
245    }
246    bool IsEmpty() const {
247      return value_ == kPersistentContainerNotFound;
248    }
249    template<typename T>
250    bool SetReturnValue(ReturnValue<T> returnValue) {
251      return SetReturnValueFromVal(&returnValue, value_);
252    }
253    void Reset() {
254      value_ = kPersistentContainerNotFound;
255    }
256    void operator=(const PersistentValueReference& other) {
257      value_ = other.value_;
258    }
259
260   private:
261    friend class PersistentValueMapBase;
262    friend class PersistentValueMap<K, V, Traits>;
263    friend class GlobalValueMap<K, V, Traits>;
264
265    explicit PersistentValueReference(PersistentContainerValue value)
266        : value_(value) { }
267
268    void operator=(PersistentContainerValue value) {
269      value_ = value;
270    }
271
272    PersistentContainerValue value_;
273  };
274
275  /**
276   * Get a reference to a map value. This enables fast, repeated access
277   * to a value stored in the map while the map remains unchanged.
278   *
279   * Careful: This is potentially unsafe, so please use with care.
280   * The value will become invalid if the value for this key changes
281   * in the underlying map, as a result of Set or Remove for the same
282   * key; as a result of the weak callback for the same key; or as a
283   * result of calling Clear() or destruction of the map.
284   */
285  PersistentValueReference GetReference(const K& key) {
286    return PersistentValueReference(Traits::Get(&impl_, key));
287  }
288
289 protected:
290  explicit PersistentValueMapBase(Isolate* isolate)
291      : isolate_(isolate), label_(nullptr) {}
292  PersistentValueMapBase(Isolate* isolate, const char* label)
293      : isolate_(isolate), label_(label) {}
294
295  ~PersistentValueMapBase() { Clear(); }
296
297  Isolate* isolate() { return isolate_; }
298  typename Traits::Impl* impl() { return &impl_; }
299
300  static V* FromVal(PersistentContainerValue v) {
301    return reinterpret_cast<V*>(v);
302  }
303
304  static PersistentContainerValue ClearAndLeak(Global<V>* persistent) {
305    V* v = persistent->template value<V>();
306    persistent->Clear();
307    return reinterpret_cast<PersistentContainerValue>(v);
308  }
309
310  static PersistentContainerValue Leak(Global<V>* persistent) {
311    return reinterpret_cast<PersistentContainerValue>(persistent->slot());
312  }
313
314  /**
315   * Return a container value as Global and make sure the weak
316   * callback is properly disposed of. All remove functionality should go
317   * through this.
318   */
319  static Global<V> Release(PersistentContainerValue v) {
320    Global<V> p;
321    p.slot() = reinterpret_cast<internal::Address*>(FromVal(v));
322    if (Traits::kCallbackType != kNotWeak && p.IsWeak()) {
323      Traits::DisposeCallbackData(
324          p.template ClearWeak<typename Traits::WeakCallbackDataType>());
325    }
326    return p.Pass();
327  }
328
329  void RemoveWeak(const K& key) {
330    Global<V> p;
331    p.slot() = reinterpret_cast<internal::Address*>(
332        FromVal(Traits::Remove(&impl_, key)));
333    p.Reset();
334  }
335
336  void AnnotateStrongRetainer(Global<V>* persistent) {
337    persistent->AnnotateStrongRetainer(label_);
338  }
339
340 private:
341  PersistentValueMapBase(PersistentValueMapBase&);
342  void operator=(PersistentValueMapBase&);
343
344  static bool SetReturnValueFromVal(ReturnValue<Value>* returnValue,
345                                    PersistentContainerValue value) {
346    bool hasValue = value != kPersistentContainerNotFound;
347    if (hasValue) {
348      returnValue->SetInternal(
349          *reinterpret_cast<internal::Address*>(FromVal(value)));
350    }
351    return hasValue;
352  }
353
354  Isolate* isolate_;
355  typename Traits::Impl impl_;
356  const char* label_;
357};
358
359template <typename K, typename V, typename Traits>
360class PersistentValueMap : public PersistentValueMapBase<K, V, Traits> {
361 public:
362  explicit PersistentValueMap(Isolate* isolate)
363      : PersistentValueMapBase<K, V, Traits>(isolate) {}
364  PersistentValueMap(Isolate* isolate, const char* label)
365      : PersistentValueMapBase<K, V, Traits>(isolate, label) {}
366
367  typedef
368      typename PersistentValueMapBase<K, V, Traits>::PersistentValueReference
369          PersistentValueReference;
370
371  /**
372   * Put value into map. Depending on Traits::kIsWeak, the value will be held
373   * by the map strongly or weakly.
374   * Returns old value as Global.
375   */
376  Global<V> Set(const K& key, Local<V> value) {
377    Global<V> persistent(this->isolate(), value);
378    return SetUnique(key, &persistent);
379  }
380
381  /**
382   * Put value into map, like Set(const K&, Local<V>).
383   */
384  Global<V> Set(const K& key, Global<V> value) {
385    return SetUnique(key, &value);
386  }
387
388  /**
389   * Put the value into the map, and set the 'weak' callback when demanded
390   * by the Traits class.
391   */
392  Global<V> SetUnique(const K& key, Global<V>* persistent) {
393    if (Traits::kCallbackType == kNotWeak) {
394      this->AnnotateStrongRetainer(persistent);
395    } else {
396      WeakCallbackType callback_type =
397          Traits::kCallbackType == kWeakWithInternalFields
398              ? WeakCallbackType::kInternalFields
399              : WeakCallbackType::kParameter;
400      auto value = Local<V>::New(this->isolate(), *persistent);
401      persistent->template SetWeak<typename Traits::WeakCallbackDataType>(
402          Traits::WeakCallbackParameter(this, key, value), WeakCallback,
403          callback_type);
404    }
405    PersistentContainerValue old_value =
406        Traits::Set(this->impl(), key, this->ClearAndLeak(persistent));
407    return this->Release(old_value).Pass();
408  }
409
410  /**
411   * Put a value into the map and update the reference.
412   * Restrictions of GetReference apply here as well.
413   */
414  Global<V> Set(const K& key, Global<V> value,
415                PersistentValueReference* reference) {
416    *reference = this->Leak(&value);
417    return SetUnique(key, &value);
418  }
419
420 private:
421  static void WeakCallback(
422      const WeakCallbackInfo<typename Traits::WeakCallbackDataType>& data) {
423    if (Traits::kCallbackType != kNotWeak) {
424      PersistentValueMap<K, V, Traits>* persistentValueMap =
425          Traits::MapFromWeakCallbackInfo(data);
426      K key = Traits::KeyFromWeakCallbackInfo(data);
427      Traits::Dispose(data.GetIsolate(),
428                      persistentValueMap->Remove(key).Pass(), key);
429      Traits::DisposeCallbackData(data.GetParameter());
430    }
431  }
432};
433
434
435template <typename K, typename V, typename Traits>
436class GlobalValueMap : public PersistentValueMapBase<K, V, Traits> {
437 public:
438  explicit GlobalValueMap(Isolate* isolate)
439      : PersistentValueMapBase<K, V, Traits>(isolate) {}
440  GlobalValueMap(Isolate* isolate, const char* label)
441      : PersistentValueMapBase<K, V, Traits>(isolate, label) {}
442
443  typedef
444      typename PersistentValueMapBase<K, V, Traits>::PersistentValueReference
445          PersistentValueReference;
446
447  /**
448   * Put value into map. Depending on Traits::kIsWeak, the value will be held
449   * by the map strongly or weakly.
450   * Returns old value as Global.
451   */
452  Global<V> Set(const K& key, Local<V> value) {
453    Global<V> persistent(this->isolate(), value);
454    return SetUnique(key, &persistent);
455  }
456
457  /**
458   * Put value into map, like Set(const K&, Local<V>).
459   */
460  Global<V> Set(const K& key, Global<V> value) {
461    return SetUnique(key, &value);
462  }
463
464  /**
465   * Put the value into the map, and set the 'weak' callback when demanded
466   * by the Traits class.
467   */
468  Global<V> SetUnique(const K& key, Global<V>* persistent) {
469    if (Traits::kCallbackType == kNotWeak) {
470      this->AnnotateStrongRetainer(persistent);
471    } else {
472      WeakCallbackType callback_type =
473          Traits::kCallbackType == kWeakWithInternalFields
474              ? WeakCallbackType::kInternalFields
475              : WeakCallbackType::kParameter;
476      auto value = Local<V>::New(this->isolate(), *persistent);
477      persistent->template SetWeak<typename Traits::WeakCallbackDataType>(
478          Traits::WeakCallbackParameter(this, key, value), OnWeakCallback,
479          callback_type);
480    }
481    PersistentContainerValue old_value =
482        Traits::Set(this->impl(), key, this->ClearAndLeak(persistent));
483    return this->Release(old_value).Pass();
484  }
485
486  /**
487   * Put a value into the map and update the reference.
488   * Restrictions of GetReference apply here as well.
489   */
490  Global<V> Set(const K& key, Global<V> value,
491                PersistentValueReference* reference) {
492    *reference = this->Leak(&value);
493    return SetUnique(key, &value);
494  }
495
496 private:
497  static void OnWeakCallback(
498      const WeakCallbackInfo<typename Traits::WeakCallbackDataType>& data) {
499    if (Traits::kCallbackType != kNotWeak) {
500      auto map = Traits::MapFromWeakCallbackInfo(data);
501      K key = Traits::KeyFromWeakCallbackInfo(data);
502      map->RemoveWeak(key);
503      Traits::OnWeakCallback(data);
504      data.SetSecondPassCallback(SecondWeakCallback);
505    }
506  }
507
508  static void SecondWeakCallback(
509      const WeakCallbackInfo<typename Traits::WeakCallbackDataType>& data) {
510    Traits::DisposeWeak(data);
511  }
512};
513
514
515/**
516 * A map that uses Global as value and std::map as the backing
517 * implementation. Persistents are held non-weak.
518 *
519 * C++11 embedders don't need this class, as they can use
520 * Global directly in std containers.
521 */
522template<typename K, typename V,
523    typename Traits = DefaultPersistentValueMapTraits<K, V> >
524class StdPersistentValueMap : public PersistentValueMap<K, V, Traits> {
525 public:
526  explicit StdPersistentValueMap(Isolate* isolate)
527      : PersistentValueMap<K, V, Traits>(isolate) {}
528};
529
530
531/**
532 * A map that uses Global as value and std::map as the backing
533 * implementation. Globals are held non-weak.
534 *
535 * C++11 embedders don't need this class, as they can use
536 * Global directly in std containers.
537 */
538template <typename K, typename V,
539          typename Traits = DefaultGlobalMapTraits<K, V> >
540class StdGlobalValueMap : public GlobalValueMap<K, V, Traits> {
541 public:
542  explicit StdGlobalValueMap(Isolate* isolate)
543      : GlobalValueMap<K, V, Traits>(isolate) {}
544};
545
546class DefaultPersistentValueVectorTraits {
547 public:
548  typedef std::vector<PersistentContainerValue> Impl;
549
550  static void Append(Impl* impl, PersistentContainerValue value) {
551    impl->push_back(value);
552  }
553  static bool IsEmpty(const Impl* impl) {
554    return impl->empty();
555  }
556  static size_t Size(const Impl* impl) {
557    return impl->size();
558  }
559  static PersistentContainerValue Get(const Impl* impl, size_t i) {
560    return (i < impl->size()) ? impl->at(i) : kPersistentContainerNotFound;
561  }
562  static void ReserveCapacity(Impl* impl, size_t capacity) {
563    impl->reserve(capacity);
564  }
565  static void Clear(Impl* impl) {
566    impl->clear();
567  }
568};
569
570/**
571 * A vector wrapper that safely stores Global values.
572 * C++11 embedders don't need this class, as they can use Global
573 * directly in std containers.
574 *
575 * This class relies on a backing vector implementation, whose type and methods
576 * are described by the Traits class. The backing map will handle values of type
577 * PersistentContainerValue, with all conversion into and out of V8
578 * handles being transparently handled by this class.
579 */
580template <typename V, typename Traits = DefaultPersistentValueVectorTraits>
581class V8_DEPRECATE_SOON("Use std::vector<Global<V>>.") PersistentValueVector {
582 public:
583  explicit PersistentValueVector(Isolate* isolate) : isolate_(isolate) { }
584
585  ~PersistentValueVector() {
586    Clear();
587  }
588
589  /**
590   * Append a value to the vector.
591   */
592  void Append(Local<V> value) {
593    Global<V> persistent(isolate_, value);
594    Traits::Append(&impl_, ClearAndLeak(&persistent));
595  }
596
597  /**
598   * Append a persistent's value to the vector.
599   */
600  void Append(Global<V> persistent) {
601    Traits::Append(&impl_, ClearAndLeak(&persistent));
602  }
603
604  /**
605   * Are there any values in the vector?
606   */
607  bool IsEmpty() const {
608    return Traits::IsEmpty(&impl_);
609  }
610
611  /**
612   * How many elements are in the vector?
613   */
614  size_t Size() const {
615    return Traits::Size(&impl_);
616  }
617
618  /**
619   * Retrieve the i-th value in the vector.
620   */
621  Local<V> Get(size_t index) const {
622    return Local<V>::New(isolate_, internal::ValueHelper::SlotAsValue<V>(
623                                       FromVal(Traits::Get(&impl_, index))));
624  }
625
626  /**
627   * Remove all elements from the vector.
628   */
629  void Clear() {
630    size_t length = Traits::Size(&impl_);
631    for (size_t i = 0; i < length; i++) {
632      Global<V> p;
633      p.slot() =
634          reinterpret_cast<internal::Address>(FromVal(Traits::Get(&impl_, i)));
635    }
636    Traits::Clear(&impl_);
637  }
638
639  /**
640   * Reserve capacity in the vector.
641   * (Efficiency gains depend on the backing implementation.)
642   */
643  void ReserveCapacity(size_t capacity) {
644    Traits::ReserveCapacity(&impl_, capacity);
645  }
646
647 private:
648  static PersistentContainerValue ClearAndLeak(Global<V>* persistent) {
649    auto slot = persistent->slot();
650    persistent->Clear();
651    return reinterpret_cast<PersistentContainerValue>(slot);
652  }
653
654  static V* FromVal(PersistentContainerValue v) {
655    return reinterpret_cast<V*>(v);
656  }
657
658  Isolate* isolate_;
659  typename Traits::Impl impl_;
660};
661
662}  // namespace v8
663
664#endif  // V8_UTIL_H
665