michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef jsweakmap_h
michael@0: #define jsweakmap_h
michael@0: 
michael@0: #include "jscompartment.h"
michael@0: #include "jsfriendapi.h"
michael@0: #include "jsobj.h"
michael@0: 
michael@0: #include "gc/Marking.h"
michael@0: #include "js/HashTable.h"
michael@0: 
michael@0: namespace js {
michael@0: 
michael@0: // A subclass template of js::HashMap whose keys and values may be garbage-collected. When
michael@0: // a key is collected, the table entry disappears, dropping its reference to the value.
michael@0: //
michael@0: // More precisely:
michael@0: //
michael@0: //     A WeakMap entry is collected if and only if either the WeakMap or the entry's key
michael@0: //     is collected. If an entry is not collected, it remains in the WeakMap and it has a
michael@0: //     strong reference to the value.
michael@0: //
michael@0: // You must call this table's 'trace' method when the object of which it is a part is
michael@0: // reached by the garbage collection tracer. Once a table is known to be live, the
michael@0: // implementation takes care of the iterative marking needed for weak tables and removing
michael@0: // table entries when collection is complete.
michael@0: 
michael@0: // The value for the next pointer for maps not in the map list.
michael@0: static WeakMapBase * const WeakMapNotInList = reinterpret_cast<WeakMapBase *>(1);
michael@0: 
michael@0: typedef Vector<WeakMapBase *, 0, SystemAllocPolicy> WeakMapVector;
michael@0: 
michael@0: // Common base class for all WeakMap specializations. The collector uses this to call
michael@0: // their markIteratively and sweep methods.
michael@0: class WeakMapBase {
michael@0:   public:
michael@0:     WeakMapBase(JSObject *memOf, JSCompartment *c);
michael@0:     virtual ~WeakMapBase();
michael@0: 
michael@0:     void trace(JSTracer *tracer) {
michael@0:         if (IS_GC_MARKING_TRACER(tracer)) {
michael@0:             // We don't do anything with a WeakMap at trace time. Rather, we wait until as
michael@0:             // many keys as possible have been marked, and add ourselves to the list of
michael@0:             // known-live WeakMaps to be scanned in the iterative marking phase, by
michael@0:             // markAllIteratively.
michael@0:             JS_ASSERT(tracer->eagerlyTraceWeakMaps() == DoNotTraceWeakMaps);
michael@0: 
michael@0:             // Add ourselves to the list if we are not already in the list. We can already
michael@0:             // be in the list if the weak map is marked more than once due delayed marking.
michael@0:             if (next == WeakMapNotInList) {
michael@0:                 next = compartment->gcWeakMapList;
michael@0:                 compartment->gcWeakMapList = this;
michael@0:             }
michael@0:         } else {
michael@0:             // If we're not actually doing garbage collection, the keys won't be marked
michael@0:             // nicely as needed by the true ephemeral marking algorithm --- custom tracers
michael@0:             // such as the cycle collector must use their own means for cycle detection.
michael@0:             // So here we do a conservative approximation: pretend all keys are live.
michael@0:             if (tracer->eagerlyTraceWeakMaps() == DoNotTraceWeakMaps)
michael@0:                 return;
michael@0: 
michael@0:             nonMarkingTraceValues(tracer);
michael@0:             if (tracer->eagerlyTraceWeakMaps() == TraceWeakMapKeysValues)
michael@0:                 nonMarkingTraceKeys(tracer);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Garbage collector entry points.
michael@0: 
michael@0:     // Check all weak maps in a compartment that have been marked as live in this garbage
michael@0:     // collection, and mark the values of all entries that have become strong references
michael@0:     // to them. Return true if we marked any new values, indicating that we need to make
michael@0:     // another pass. In other words, mark my marked maps' marked members' mid-collection.
michael@0:     static bool markCompartmentIteratively(JSCompartment *c, JSTracer *tracer);
michael@0: 
michael@0:     // Remove entries whose keys are dead from all weak maps in a compartment marked as
michael@0:     // live in this garbage collection.
michael@0:     static void sweepCompartment(JSCompartment *c);
michael@0: 
michael@0:     // Trace all delayed weak map bindings. Used by the cycle collector.
michael@0:     static void traceAllMappings(WeakMapTracer *tracer);
michael@0: 
michael@0:     bool isInList() { return next != WeakMapNotInList; }
michael@0:     void check() { JS_ASSERT(!isInList()); }
michael@0: 
michael@0:     // Remove everything from the weak map list for a compartment.
michael@0:     static void resetCompartmentWeakMapList(JSCompartment *c);
michael@0: 
michael@0:     // Save the live weak map list for a compartment, appending the data to a vector.
michael@0:     static bool saveCompartmentWeakMapList(JSCompartment *c, WeakMapVector &vector);
michael@0: 
michael@0:     // Restore live weak map lists for multiple compartments from a vector.
michael@0:     static void restoreCompartmentWeakMapLists(WeakMapVector &vector);
michael@0: 
michael@0:     // Remove a weakmap from the live weakmaps list
michael@0:     static void removeWeakMapFromList(WeakMapBase *weakmap);
michael@0: 
michael@0:   protected:
michael@0:     // Instance member functions called by the above. Instantiations of WeakMap override
michael@0:     // these with definitions appropriate for their Key and Value types.
michael@0:     virtual void nonMarkingTraceKeys(JSTracer *tracer) = 0;
michael@0:     virtual void nonMarkingTraceValues(JSTracer *tracer) = 0;
michael@0:     virtual bool markIteratively(JSTracer *tracer) = 0;
michael@0:     virtual void sweep() = 0;
michael@0:     virtual void traceMappings(WeakMapTracer *tracer) = 0;
michael@0: 
michael@0:     // Object that this weak map is part of, if any.
michael@0:     JSObject *memberOf;
michael@0: 
michael@0:     // Compartment that this weak map is part of.
michael@0:     JSCompartment *compartment;
michael@0: 
michael@0:   private:
michael@0:     // Link in a list of WeakMaps to mark iteratively and sweep in this garbage
michael@0:     // collection, headed by JSCompartment::gcWeakMapList. The last element of
michael@0:     // the list has nullptr as its next. Maps not in the list have
michael@0:     // WeakMapNotInList as their next.  We must distinguish these cases to
michael@0:     // avoid creating infinite lists when a weak map gets traced twice due to
michael@0:     // delayed marking.
michael@0:     WeakMapBase *next;
michael@0: };
michael@0: 
michael@0: template <class Key, class Value,
michael@0:           class HashPolicy = DefaultHasher<Key> >
michael@0: class WeakMap : public HashMap<Key, Value, HashPolicy, RuntimeAllocPolicy>, public WeakMapBase
michael@0: {
michael@0:   public:
michael@0:     typedef HashMap<Key, Value, HashPolicy, RuntimeAllocPolicy> Base;
michael@0:     typedef typename Base::Enum Enum;
michael@0:     typedef typename Base::Lookup Lookup;
michael@0:     typedef typename Base::Range Range;
michael@0: 
michael@0:     explicit WeakMap(JSContext *cx, JSObject *memOf = nullptr)
michael@0:         : Base(cx->runtime()), WeakMapBase(memOf, cx->compartment()) { }
michael@0: 
michael@0:   private:
michael@0:     bool markValue(JSTracer *trc, Value *x) {
michael@0:         if (gc::IsMarked(x))
michael@0:             return false;
michael@0:         gc::Mark(trc, x, "WeakMap entry value");
michael@0:         JS_ASSERT(gc::IsMarked(x));
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     void nonMarkingTraceKeys(JSTracer *trc) {
michael@0:         for (Enum e(*this); !e.empty(); e.popFront()) {
michael@0:             Key key(e.front().key());
michael@0:             gc::Mark(trc, &key, "WeakMap entry key");
michael@0:             if (key != e.front().key())
michael@0:                 entryMoved(e, key);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     void nonMarkingTraceValues(JSTracer *trc) {
michael@0:         for (Range r = Base::all(); !r.empty(); r.popFront())
michael@0:             gc::Mark(trc, &r.front().value(), "WeakMap entry value");
michael@0:     }
michael@0: 
michael@0:     bool keyNeedsMark(JSObject *key) {
michael@0:         if (JSWeakmapKeyDelegateOp op = key->getClass()->ext.weakmapKeyDelegateOp) {
michael@0:             JSObject *delegate = op(key);
michael@0:             /*
michael@0:              * Check if the delegate is marked with any color to properly handle
michael@0:              * gray marking when the key's delegate is black and the map is
michael@0:              * gray.
michael@0:              */
michael@0:             return delegate && gc::IsObjectMarked(&delegate);
michael@0:         }
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     bool keyNeedsMark(gc::Cell *cell) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     bool markIteratively(JSTracer *trc) {
michael@0:         bool markedAny = false;
michael@0:         for (Enum e(*this); !e.empty(); e.popFront()) {
michael@0:             /* If the entry is live, ensure its key and value are marked. */
michael@0:             Key key(e.front().key());
michael@0:             if (gc::IsMarked(const_cast<Key *>(&key))) {
michael@0:                 if (markValue(trc, &e.front().value()))
michael@0:                     markedAny = true;
michael@0:                 if (e.front().key() != key)
michael@0:                     entryMoved(e, key);
michael@0:             } else if (keyNeedsMark(key)) {
michael@0:                 gc::Mark(trc, &e.front().value(), "WeakMap entry value");
michael@0:                 gc::Mark(trc, &key, "proxy-preserved WeakMap entry key");
michael@0:                 if (e.front().key() != key)
michael@0:                     entryMoved(e, key);
michael@0:                 markedAny = true;
michael@0:             }
michael@0:             key.unsafeSet(nullptr);
michael@0:         }
michael@0:         return markedAny;
michael@0:     }
michael@0: 
michael@0:     void sweep() {
michael@0:         /* Remove all entries whose keys remain unmarked. */
michael@0:         for (Enum e(*this); !e.empty(); e.popFront()) {
michael@0:             Key k(e.front().key());
michael@0:             if (gc::IsAboutToBeFinalized(&k))
michael@0:                 e.removeFront();
michael@0:             else if (k != e.front().key())
michael@0:                 entryMoved(e, k);
michael@0:         }
michael@0:         /*
michael@0:          * Once we've swept, all remaining edges should stay within the
michael@0:          * known-live part of the graph.
michael@0:          */
michael@0:         assertEntriesNotAboutToBeFinalized();
michael@0:     }
michael@0: 
michael@0:     /* memberOf can be nullptr, which means that the map is not part of a JSObject. */
michael@0:     void traceMappings(WeakMapTracer *tracer) {
michael@0:         for (Range r = Base::all(); !r.empty(); r.popFront()) {
michael@0:             gc::Cell *key = gc::ToMarkable(r.front().key());
michael@0:             gc::Cell *value = gc::ToMarkable(r.front().value());
michael@0:             if (key && value) {
michael@0:                 tracer->callback(tracer, memberOf,
michael@0:                                  key, gc::TraceKind(r.front().key()),
michael@0:                                  value, gc::TraceKind(r.front().value()));
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /* Rekey an entry when moved, ensuring we do not trigger barriers. */
michael@0:     void entryMoved(Enum &eArg, const Key &k) {
michael@0:         typedef typename HashMap<typename Unbarriered<Key>::type,
michael@0:                                  typename Unbarriered<Value>::type,
michael@0:                                  typename Unbarriered<HashPolicy>::type,
michael@0:                                  RuntimeAllocPolicy>::Enum UnbarrieredEnum;
michael@0:         UnbarrieredEnum &e = reinterpret_cast<UnbarrieredEnum &>(eArg);
michael@0:         e.rekeyFront(reinterpret_cast<const typename Unbarriered<Key>::type &>(k));
michael@0:     }
michael@0: 
michael@0: protected:
michael@0:     void assertEntriesNotAboutToBeFinalized() {
michael@0: #if DEBUG
michael@0:         for (Range r = Base::all(); !r.empty(); r.popFront()) {
michael@0:             Key k(r.front().key());
michael@0:             JS_ASSERT(!gc::IsAboutToBeFinalized(&k));
michael@0:             JS_ASSERT(!gc::IsAboutToBeFinalized(&r.front().value()));
michael@0:             JS_ASSERT(k == r.front().key());
michael@0:         }
michael@0: #endif
michael@0:     }
michael@0: };
michael@0: 
michael@0: } /* namespace js */
michael@0: 
michael@0: extern JSObject *
michael@0: js_InitWeakMapClass(JSContext *cx, js::HandleObject obj);
michael@0: 
michael@0: #endif /* jsweakmap_h */