Bug 697479 - Implement Map and Set builtins for JS. r=jimb.
authorJason Orendorff <jorendorff@mozilla.com>
Fri, 20 Jan 2012 06:11:43 -0600
changeset 84973 6a5e20a0f7419f896f82f19d3665f75b7334ed08
parent 84972 bd3c52671d7455ce4bb88b5b618e649407da057a
child 84974 af0a15a363630c67b9ab89d23b34a89c235142f1
push id5094
push userjorendorff@mozilla.com
push dateFri, 20 Jan 2012 12:12:04 +0000
treeherdermozilla-inbound@6a5e20a0f741 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjimb
bugs697479
milestone12.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 697479 - Implement Map and Set builtins for JS. r=jimb.
js/src/Makefile.in
js/src/builtin/MapObject.cpp
js/src/builtin/MapObject.h
js/src/gc/Barrier.h
js/src/jit-test/tests/basic/testCrossCompartmentTransparency.js
js/src/jit-test/tests/collections/Map-delete.js
js/src/jit-test/tests/collections/Map-gc-1.js
js/src/jit-test/tests/collections/Map-gc-2.js
js/src/jit-test/tests/collections/Map-get.js
js/src/jit-test/tests/collections/Map-scale.js
js/src/jit-test/tests/collections/Map-set-undefined.js
js/src/jit-test/tests/collections/Map-surfaces-1.js
js/src/jit-test/tests/collections/Map-surfaces-2.js
js/src/jit-test/tests/collections/Map-surfaces-3.js
js/src/jit-test/tests/collections/Set-gc-1.js
js/src/jit-test/tests/collections/Set-scale.js
js/src/jit-test/tests/collections/Set-surfaces-1.js
js/src/jit-test/tests/collections/Set-surfaces-2.js
js/src/jit-test/tests/collections/Set-surfaces-3.js
js/src/jit-test/tests/collections/for-in.js
js/src/jit-test/tests/collections/key-equality-0.js
js/src/jit-test/tests/collections/key-equality-1.js
js/src/jit-test/tests/collections/key-equality-2.js
js/src/jit-test/tests/collections/key-equality-NaN.js
js/src/jsapi.cpp
js/src/jsapi.h
js/src/jsobj.cpp
js/src/jsproto.tbl
js/src/vm/GlobalObject.cpp
--- a/js/src/Makefile.in
+++ b/js/src/Makefile.in
@@ -166,16 +166,17 @@ CPPSRCS		= \
 		BytecodeEmitter.cpp \
 		FoldConstants.cpp \
 		ParseMaps.cpp \
 		ParseNode.cpp \
 		Parser.cpp \
 		SemanticAnalysis.cpp \
 		TokenStream.cpp \
 		LifoAlloc.cpp \
+		MapObject.cpp \
 		MemoryMetrics.cpp \
 		RegExpObject.cpp \
 		RegExpStatics.cpp \
 		RegExp.cpp \
 		Statistics.cpp \
 		Unicode.cpp \
 		$(NULL)
 
new file mode 100644
--- /dev/null
+++ b/js/src/builtin/MapObject.cpp
@@ -0,0 +1,407 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sw=4 et tw=99 ft=cpp:
+ *
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is SpiderMonkey JavaScript engine.
+ *
+ * The Initial Developer of the Original Code is
+ * the Mozilla Foundation.
+ * Portions created by the Initial Developer are Copyright (C) 2011-2012
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *  Jason Orendorff <jorendorff@mozilla.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#include "builtin/MapObject.h"
+
+#include "jscntxt.h"
+#include "jsgcmark.h"
+#include "jsobj.h"
+
+#include "vm/GlobalObject.h"
+#include "vm/Stack.h"
+
+#include "jsobjinlines.h"
+
+using namespace js;
+
+static JSObject *
+InitClass(JSContext *cx, GlobalObject *global, Class *clasp, JSProtoKey key, Native construct,
+          JSFunctionSpec *methods)
+{
+    JSObject *proto = global->createBlankPrototype(cx, clasp);
+    if (!proto)
+        return NULL;
+    proto->setPrivate(NULL);
+
+    JSAtom *atom = cx->runtime->atomState.classAtoms[key];
+    JSFunction *ctor = global->createConstructor(cx, construct, clasp, atom, 0);
+    if (!ctor ||
+        !LinkConstructorAndPrototype(cx, ctor, proto) ||
+        !DefinePropertiesAndBrand(cx, proto, NULL, methods) ||
+        !DefineConstructorAndPrototype(cx, global, key, ctor, proto))
+    {
+        return NULL;
+    }
+    return proto;
+}
+
+
+/*** HashableValue *******************************************************************************/
+
+bool
+HashableValue::setValue(JSContext *cx, const Value &v)
+{
+    if (v.isString() && v.toString()->isRope()) {
+        /* Flatten this rope so that equals() is infallible. */
+        JSString *str = v.toString()->ensureLinear(cx);
+        if (!str)
+            return false;
+        value = StringValue(str);
+    } else if (v.isDouble()) {
+        jsdouble d = v.toDouble();
+        int32_t i;
+        if (JSDOUBLE_IS_INT32(d, &i)) {
+            /* Normalize int32-valued doubles to int32 for faster hashing and testing. */
+            value = Int32Value(i);
+        } else {
+#ifdef DEBUG
+            /* All NaN values are the same. The bit-pattern must reflect this. */
+            jsval_layout a, b;
+            a.asDouble = d;
+            b.asDouble = JS_CANONICALIZE_NAN(d);
+            JS_ASSERT(a.asBits == b.asBits);
+#endif
+            value = v;
+        }
+    } else {
+        value = v;
+    }
+
+    JS_ASSERT(value.isUndefined() || value.isNull() || value.isBoolean() ||
+              value.isNumber() || value.isString() || value.isObject());
+    return true;
+}
+
+HashNumber
+HashableValue::hash() const
+{
+    /*
+     * HashableValue::setValue normalizes values so that the SameValue relation
+     * on HashableValues is the same as the == relationship on
+     * value.data.asBits, except for strings.
+     */
+    if (value.isString()) {
+        JSLinearString &s = value.toString()->asLinear();
+        return HashChars(s.chars(), s.length());
+    }
+
+    /* Having dispensed with strings, we can just hash asBits. */
+    uint64_t u = value.asRawBits();
+    return HashNumber((u >> 3) ^ (u >> (32 + 3)) ^ (u << (32 - 3)));
+}
+
+bool
+HashableValue::equals(const HashableValue &other) const
+{
+    /* Two HashableValues are equal if they have equal bits or they're equal strings. */
+    bool b = (value.asRawBits() == other.value.asRawBits()) ||
+              (value.isString() &&
+               other.value.isString() &&
+               EqualStrings(&value.toString()->asLinear(),
+                            &other.value.toString()->asLinear()));
+
+#ifdef DEBUG
+    JSBool same;
+    JS_ASSERT(SameValue(NULL, value, other.value, &same));
+    JS_ASSERT(same == b);
+#endif
+    return b;
+}
+
+
+/*** Map *****************************************************************************************/
+
+Class MapObject::class_ = {
+    "Map",
+    JSCLASS_HAS_PRIVATE |
+    JSCLASS_HAS_CACHED_PROTO(JSProto_Map),
+    JS_PropertyStub,         /* addProperty */
+    JS_PropertyStub,         /* delProperty */
+    JS_PropertyStub,         /* getProperty */
+    JS_StrictPropertyStub,   /* setProperty */
+    JS_EnumerateStub,
+    JS_ResolveStub,
+    JS_ConvertStub,
+    finalize,
+    NULL,                    /* reserved0   */
+    NULL,                    /* checkAccess */
+    NULL,                    /* call        */
+    NULL,                    /* construct   */
+    NULL,                    /* xdrObject   */
+    NULL,                    /* hasInstance */
+    mark
+};
+
+JSFunctionSpec MapObject::methods[] = {
+    JS_FN("get", get, 1, 0),
+    JS_FN("has", has, 1, 0),
+    JS_FN("set", set, 2, 0),
+    JS_FN("delete", delete_, 1, 0),
+    JS_FS_END
+};
+
+JSObject *
+MapObject::initClass(JSContext *cx, JSObject *obj)
+{
+    return InitClass(cx, &obj->asGlobal(), &class_, JSProto_Map, construct, methods);
+}
+
+void
+MapObject::mark(JSTracer *trc, JSObject *obj)
+{
+    MapObject *mapobj = static_cast<MapObject *>(obj);
+    if (ValueMap *map = mapobj->getData()) {
+        for (ValueMap::Range r = map->all(); !r.empty(); r.popFront()) {
+            gc::MarkValue(trc, r.front().key, "key");
+            gc::MarkValue(trc, r.front().value, "value");
+        }
+    }
+}
+
+void
+MapObject::finalize(JSContext *cx, JSObject *obj)
+{
+    MapObject *mapobj = static_cast<MapObject *>(obj);
+    if (ValueMap *map = mapobj->getData())
+        cx->delete_(map);
+}
+
+JSBool
+MapObject::construct(JSContext *cx, uintN argc, Value *vp)
+{
+    JSObject *obj = NewBuiltinClassInstance(cx, &class_);
+    if (!obj)
+        return false;
+
+    ValueMap *map = cx->new_<ValueMap>(cx->runtime);
+    if (!map || !map->init())
+        return false;
+    obj->setPrivate(map);
+
+    CallArgsFromVp(argc, vp).rval().setObject(*obj);
+    return true;
+}
+
+#define UNPACK_THIS(T, native, cx, argc, vp, args, data)                      \
+    CallArgs args = CallArgsFromVp(argc, vp);                                 \
+    if (!args.thisv().isObject() ||                                           \
+        !args.thisv().toObject().hasClass(&T::class_))                        \
+    {                                                                         \
+        return js::HandleNonGenericMethodClassMismatch(cx, args, native,      \
+                                                       &T::class_);           \
+    }                                                                         \
+    if (!args.thisv().toObject().getPrivate()) {                              \
+        ReportIncompatibleMethod(cx, args, &T::class_);                       \
+        return false;                                                         \
+    }                                                                         \
+    T::Data &data = *static_cast<T &>(args.thisv().toObject()).getData();     \
+    (void) data
+
+#define THIS_MAP(native, cx, argc, vp, args, map)                             \
+    UNPACK_THIS(MapObject, native, cx, argc, vp, args, map)
+
+#define ARG0_KEY(cx, args, key)                                               \
+    HashableValue key;                                                        \
+    if (args.length() > 0 && !key.setValue(cx, args[0]))                      \
+        return false
+
+JSBool
+MapObject::get(JSContext *cx, uintN argc, Value *vp)
+{
+    THIS_MAP(get, cx, argc, vp, args, map);
+    ARG0_KEY(cx, args, key);
+
+    if (ValueMap::Ptr p = map.lookup(key))
+        args.rval() = p->value;
+    else
+        args.rval().setUndefined();
+    return true;
+}
+
+JSBool
+MapObject::has(JSContext *cx, uintN argc, Value *vp)
+{
+    THIS_MAP(has, cx, argc, vp, args, map);
+    ARG0_KEY(cx, args, key);
+    args.rval().setBoolean(map.lookup(key));
+    return true;
+}
+
+JSBool
+MapObject::set(JSContext *cx, uintN argc, Value *vp)
+{
+    THIS_MAP(set, cx, argc, vp, args, map);
+    ARG0_KEY(cx, args, key);
+    map.put(key, args.length() > 1 ? args[1] : UndefinedValue());
+    args.rval().setUndefined();
+    return true;
+}
+
+JSBool
+MapObject::delete_(JSContext *cx, uintN argc, Value *vp)
+{
+    THIS_MAP(delete_, cx, argc, vp, args, map);
+    ARG0_KEY(cx, args, key);
+    ValueMap::Ptr p = map.lookup(key);
+    bool found = p.found();
+    if (found)
+        map.remove(p);
+    args.rval().setBoolean(found);
+    return true;
+}
+
+JSObject *
+js_InitMapClass(JSContext *cx, JSObject *obj)
+{
+    return MapObject::initClass(cx, obj);
+}
+
+
+/*** Set *****************************************************************************************/
+
+Class SetObject::class_ = {
+    "Set",
+    JSCLASS_HAS_PRIVATE |
+    JSCLASS_HAS_CACHED_PROTO(JSProto_Set),
+    JS_PropertyStub,         /* addProperty */
+    JS_PropertyStub,         /* delProperty */
+    JS_PropertyStub,         /* getProperty */
+    JS_StrictPropertyStub,   /* setProperty */
+    JS_EnumerateStub,
+    JS_ResolveStub,
+    JS_ConvertStub,
+    finalize,
+    NULL,                    /* reserved0   */
+    NULL,                    /* checkAccess */
+    NULL,                    /* call        */
+    NULL,                    /* construct   */
+    NULL,                    /* xdrObject   */
+    NULL,                    /* hasInstance */
+    mark
+};
+
+JSFunctionSpec SetObject::methods[] = {
+    JS_FN("has", has, 1, 0),
+    JS_FN("add", add, 1, 0),
+    JS_FN("delete", delete_, 1, 0),
+    JS_FS_END
+};
+
+JSObject *
+SetObject::initClass(JSContext *cx, JSObject *obj)
+{
+    return InitClass(cx, &obj->asGlobal(), &class_, JSProto_Set, construct, methods);
+}
+
+void
+SetObject::mark(JSTracer *trc, JSObject *obj)
+{
+    SetObject *setobj = static_cast<SetObject *>(obj);
+    if (ValueSet *set = setobj->getData()) {
+        for (ValueSet::Range r = set->all(); !r.empty(); r.popFront())
+            gc::MarkValue(trc, r.front(), "key");
+    }
+}
+
+void
+SetObject::finalize(JSContext *cx, JSObject *obj)
+{
+    SetObject *setobj = static_cast<SetObject *>(obj);
+    if (ValueSet *set = setobj->getData())
+        cx->delete_(set);
+}
+
+JSBool
+SetObject::construct(JSContext *cx, uintN argc, Value *vp)
+{
+    JSObject *obj = NewBuiltinClassInstance(cx, &class_);
+    if (!obj)
+        return false;
+
+    ValueSet *set = cx->new_<ValueSet>(cx->runtime);
+    if (!set || !set->init())
+        return false;
+    obj->setPrivate(set);
+
+    CallArgsFromVp(argc, vp).rval().setObject(*obj);
+    return true;
+}
+
+#define THIS_SET(native, cx, argc, vp, args, set)                             \
+    UNPACK_THIS(SetObject, native, cx, argc, vp, args, set)
+
+JSBool
+SetObject::has(JSContext *cx, uintN argc, Value *vp)
+{
+    THIS_SET(has, cx, argc, vp, args, set);
+    ARG0_KEY(cx, args, key);
+    args.rval().setBoolean(set.has(key));
+    return true;
+}
+
+JSBool
+SetObject::add(JSContext *cx, uintN argc, Value *vp)
+{
+    THIS_SET(add, cx, argc, vp, args, set);
+    ARG0_KEY(cx, args, key);
+    if (!set.put(key))
+        return false;
+    args.rval().setUndefined();
+    return true;
+}
+
+JSBool
+SetObject::delete_(JSContext *cx, uintN argc, Value *vp)
+{
+    THIS_SET(delete_, cx, argc, vp, args, set);
+    ARG0_KEY(cx, args, key);
+    ValueSet::Ptr p = set.lookup(key);
+    bool found = p.found();
+    if (found)
+        set.remove(p);
+    args.rval().setBoolean(found);
+    return true;
+}
+
+JSObject *
+js_InitSetClass(JSContext *cx, JSObject *obj)
+{
+    return SetObject::initClass(cx, obj);
+} 
new file mode 100644
--- /dev/null
+++ b/js/src/builtin/MapObject.h
@@ -0,0 +1,122 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sw=4 et tw=99 ft=cpp:
+ *
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is SpiderMonkey JavaScript engine.
+ *
+ * The Initial Developer of the Original Code is
+ * the Mozilla Foundation.
+ * Portions created by the Initial Developer are Copyright (C) 2011-2012
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *  Jason Orendorff <jorendorff@mozilla.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#ifndef MapObject_h__
+#define MapObject_h__
+
+#include "jsapi.h"
+#include "jscntxt.h"
+#include "jsobj.h"
+
+#include "js/HashTable.h"
+
+namespace js {
+
+/*
+ * Comparing two ropes for equality can fail. The js::HashTable template
+ * requires infallible hash() and match() operations. Therefore we require
+ * all values to be converted to hashable form before being used as a key
+ * in a Map or Set object.
+ *
+ * All values except ropes are hashable as-is.
+ */
+class HashableValue {
+    HeapValue value;
+
+  public:
+    struct Hasher {
+        typedef HashableValue Lookup;
+        static HashNumber hash(const Lookup &v) { return v.hash(); }
+        static bool match(const HashableValue &k, const Lookup &l) { return k.equals(l); }
+    };
+
+    HashableValue() : value(UndefinedValue()) {}
+
+    operator const HeapValue &() const { return value; }
+    bool setValue(JSContext *cx, const Value &v);
+    HashNumber hash() const;
+    bool equals(const HashableValue &other) const;
+};
+
+typedef HashMap<HashableValue, HeapValue, HashableValue::Hasher, RuntimeAllocPolicy> ValueMap;
+typedef HashSet<HashableValue, HashableValue::Hasher, RuntimeAllocPolicy> ValueSet;
+
+class MapObject : public JSObject {
+  public:
+    static JSObject *initClass(JSContext *cx, JSObject *obj);
+    static Class class_;
+  private:
+    typedef ValueMap Data;
+    static JSFunctionSpec methods[];
+    ValueMap *getData() { return static_cast<ValueMap *>(getPrivate()); }
+    static void mark(JSTracer *trc, JSObject *obj);
+    static void finalize(JSContext *cx, JSObject *obj);
+    static JSBool construct(JSContext *cx, uintN argc, Value *vp);
+    static JSBool get(JSContext *cx, uintN argc, Value *vp);
+    static JSBool has(JSContext *cx, uintN argc, Value *vp);
+    static JSBool set(JSContext *cx, uintN argc, Value *vp);
+    static JSBool delete_(JSContext *cx, uintN argc, Value *vp);
+};
+
+class SetObject : public JSObject {
+  public:
+    static JSObject *initClass(JSContext *cx, JSObject *obj);
+    static Class class_;
+  private:
+    typedef ValueSet Data;
+    static JSFunctionSpec methods[];
+    ValueSet *getData() { return static_cast<ValueSet *>(getPrivate()); }
+    static void mark(JSTracer *trc, JSObject *obj);
+    static void finalize(JSContext *cx, JSObject *obj);
+    static JSBool construct(JSContext *cx, uintN argc, Value *vp);
+    static JSBool has(JSContext *cx, uintN argc, Value *vp);
+    static JSBool add(JSContext *cx, uintN argc, Value *vp);
+    static JSBool delete_(JSContext *cx, uintN argc, Value *vp);
+};
+
+} /* namespace js */
+
+extern JSObject *
+js_InitMapClass(JSContext *cx, JSObject *obj);
+
+extern JSObject *
+js_InitSetClass(JSContext *cx, JSObject *obj);
+
+#endif  /* MapObject_h__ */
--- a/js/src/gc/Barrier.h
+++ b/js/src/gc/Barrier.h
@@ -316,37 +316,42 @@ class HeapValue
      * the barrier. If you already know the compartment, it's faster to pass it
      * in.
      */
     inline void set(JSCompartment *comp, const Value &v);
 
     const Value &get() const { return value; }
     operator const Value &() const { return value; }
 
-    bool isMarkable() const { return value.isMarkable(); }
-    bool isMagic(JSWhyMagic why) const { return value.isMagic(why); }
     bool isUndefined() const { return value.isUndefined(); }
-    bool isObject() const { return value.isObject(); }
-    bool isGCThing() const { return value.isGCThing(); }
+    bool isNull() const { return value.isNull(); }
+    bool isBoolean() const { return value.isBoolean(); }
     bool isTrue() const { return value.isTrue(); }
     bool isFalse() const { return value.isFalse(); }
+    bool isNumber() const { return value.isNumber(); }
     bool isInt32() const { return value.isInt32(); }
-    bool isNull() const { return value.isNull(); }
+    bool isString() const { return value.isString(); }
+    bool isObject() const { return value.isObject(); }
+    bool isMagic(JSWhyMagic why) const { return value.isMagic(why); }
+    bool isGCThing() const { return value.isGCThing(); }
+    bool isMarkable() const { return value.isMarkable(); }
 
+    bool toBoolean() const { return value.toBoolean(); }
+    double toNumber() const { return value.toNumber(); }
+    int32_t toInt32() const { return value.toInt32(); }
+    double toDouble() const { return value.toDouble(); }
+    JSString *toString() const { return value.toString(); }
     JSObject &toObject() const { return value.toObject(); }
     JSObject *toObjectOrNull() const { return value.toObjectOrNull(); }
     void *toGCThing() const { return value.toGCThing(); }
-    double toDouble() const { return value.toDouble(); }
-    int32_t toInt32() const { return value.toInt32(); }
-    JSString *toString() const { return value.toString(); }
-    bool toBoolean() const { return value.toBoolean(); }
-    double toNumber() const { return value.toNumber(); }
 
     JSGCTraceKind gcKind() const { return value.gcKind(); }
 
+    uint64_t asRawBits() const { return value.asRawBits(); }
+
 #ifdef DEBUG
     JSWhyMagic whyMagic() const { return value.whyMagic(); }
 #endif
 
     static inline void writeBarrierPre(const Value &v);
     static inline void writeBarrierPost(const Value &v, void *addr);
 
     static inline void writeBarrierPre(JSCompartment *comp, const Value &v);
--- a/js/src/jit-test/tests/basic/testCrossCompartmentTransparency.js
+++ b/js/src/jit-test/tests/basic/testCrossCompartmentTransparency.js
@@ -77,16 +77,23 @@ test("new String('one')", function(s) St
 test("new RegExp('1')", function(r) RegExp.prototype.toString.call(r));
 test("new RegExp('1')", function(r) RegExp.prototype.exec.call(r, '1').toString());
 test("new RegExp('1')", function(r) RegExp.prototype.test.call(r, '1'));
 test("new RegExp('1')", function(r) RegExp.prototype.compile.call(r, '1').toString());
 test("new WeakMap()", function(w) WeakMap.prototype.has.call(w, {}));
 test("new WeakMap()", function(w) WeakMap.prototype.get.call(w, {}));
 test("new WeakMap()", function(w) WeakMap.prototype.delete.call(w, {}));
 test("new WeakMap()", function(w) WeakMap.prototype.set.call(w, {}));
+test("new Map()", function(w) Map.prototype.has.call(w, {}));
+test("new Map()", function(w) Map.prototype.get.call(w, {}));
+test("new Map()", function(w) Map.prototype.delete.call(w, {}));
+test("new Map()", function(w) Map.prototype.set.call(w, {}));
+test("new Set()", function(w) Set.prototype.has.call(w, {}));
+test("new Set()", function(w) Set.prototype.add.call(w, {}));
+test("new Set()", function(w) Set.prototype.delete.call(w, {}));
 
 test("new Int8Array(1)", function(a) Int8Array.prototype.subarray.call(a).toString());
 test("new Uint8Array(1)", function(a) Uint8Array.prototype.subarray.call(a).toString());
 test("new Int16Array(1)", function(a) Int16Array.prototype.subarray.call(a).toString());
 test("new Uint16Array(1)", function(a) Uint16Array.prototype.subarray.call(a).toString());
 test("new Int32Array(1)", function(a) Int32Array.prototype.subarray.call(a).toString());
 test("new Uint32Array(1)", function(a) Uint32Array.prototype.subarray.call(a).toString());
 test("new Float32Array(1)", function(a) Float32Array.prototype.subarray.call(a).toString());
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Map-delete.js
@@ -0,0 +1,18 @@
+// Map.prototype.delete works whether the key is present or not.
+
+var m = new Map;
+var key = {};
+
+// when the map is new
+assertEq(m.delete(key), false);
+assertEq(m.has(key), false);
+
+// when the key is present
+assertEq(m.set(key, 'x'), undefined);
+assertEq(m.delete(key), true);
+assertEq(m.has(key), false);
+assertEq(m.get(key), undefined);
+
+// when the key has already been deleted
+assertEq(m.delete(key), false);
+assertEq(m.has(key), false);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Map-gc-1.js
@@ -0,0 +1,16 @@
+// Check marking through the keys of a Map.
+
+load(libdir + "referencesVia.js");
+
+var m = new Map;
+for (var i = 0; i < 20; i++) {
+    var n = new Map;
+    n.set(m, i);
+    assertEq(referencesVia(n, 'key', m), true);
+    m = n;
+}
+
+gc();
+gc();
+
+// TODO: walk the chain using for-of to make sure everything is still there
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Map-gc-2.js
@@ -0,0 +1,14 @@
+// Check marking through the values of a Map.
+
+load(libdir + "referencesVia.js");
+
+var m = new Map;
+for (var i = 0; i < 20; i++) {
+    var n = new Map;
+    n.set(i, m);
+    assertEq(referencesVia(n, 'value', m), true);
+    m = n;
+}
+
+gc();
+gc();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Map-get.js
@@ -0,0 +1,41 @@
+// Map.prototype.get and .has basically work
+var m = new Map;
+
+function rope() {
+    var s = "s";
+    for (var i = 0; i < 16; i++)
+        s += s;
+    return s;
+}
+
+var keys = [undefined, null, true, false,
+            0, 1, 65535, 65536, 2147483647, 2147483648, 4294967295, 4294967296,
+            -1, -65536, -2147483648,
+            0.5, Math.sqrt(81), Math.PI,
+            Number.MAX_VALUE, -Number.MAX_VALUE, Number.MIN_VALUE, -Number.MIN_VALUE,
+            -0, NaN, Infinity, -Infinity,
+            "", "\0", "a", "ab", "abcdefg", rope(),
+            {}, [], /a*b/, Object.prototype, Object];
+
+for (var i = 0; i < keys.length; i++) {
+    // without being set
+    var key = keys[i];
+    assertEq(m.has(key), false);
+    assertEq(m.get(key), undefined);
+
+    // after being set
+    var v = {};
+    assertEq(m.set(key, v), undefined);
+    assertEq(m.has(key), true);
+    assertEq(m.get(key), v);
+
+    // after being deleted
+    assertEq(m.delete(key), true);
+    assertEq(m.has(key), false);
+    assertEq(m.get(key), undefined);
+
+    m.set(key, v);
+}
+
+for (var i = 0; i < keys.length; i++)
+    assertEq(m.has(keys[i]), true);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Map-scale.js
@@ -0,0 +1,8 @@
+// Maps can hold at least 64K values.
+
+var N = 1 << 16;
+var m = new Map;
+for (var i = 0; i < N; i++)
+    assertEq(m.set(i, i), undefined);
+for (var i = 0; i < N; i++)
+    assertEq(m.get(i), i);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Map-set-undefined.js
@@ -0,0 +1,15 @@
+// Setting a Map key to undefined, or a missing argument, isn't the same as deleting it.
+
+var m = new Map;
+m.set(42, undefined);
+assertEq(m.has(42), true);
+assertEq(m.get(42), undefined);
+
+m.set(42, "wrong");
+m.set(42);
+assertEq(m.has(42), true);
+assertEq(m.get(42), undefined);
+
+m.set();
+assertEq(m.has(undefined), true);
+assertEq(m.get(undefined), undefined);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Map-surfaces-1.js
@@ -0,0 +1,33 @@
+// Map surfaces
+
+var desc = Object.getOwnPropertyDescriptor(this, "Map");
+assertEq(desc.enumerable, false);
+assertEq(desc.configurable, true);
+assertEq(desc.writable, true);
+
+assertEq(typeof Map, 'function');
+assertEq(Object.keys(Map).length, 0);
+assertEq(Map.length, 0);
+assertEq(Map.name, "Map");
+
+assertEq(Object.getPrototypeOf(Map.prototype), Object.prototype);
+assertEq(Object.prototype.toString.call(Map.prototype), "[object Map]");
+assertEq(Object.prototype.toString.call(new Map), "[object Map]");
+assertEq(Object.prototype.toString.call(Map()), "[object Map]");
+assertEq(Object.keys(Map.prototype).join(), "");
+assertEq(Map.prototype.constructor, Map);
+
+function checkMethod(name, arity) { 
+    var desc = Object.getOwnPropertyDescriptor(Map.prototype, name);
+    assertEq(desc.enumerable, false);
+    assertEq(desc.configurable, true);
+    assertEq(desc.writable, true);
+    assertEq(typeof desc.value, 'function');
+    assertEq(desc.value.name, name);
+    assertEq(desc.value.length, arity);
+}
+
+checkMethod("get", 1);
+checkMethod("has", 1);
+checkMethod("set", 2);
+checkMethod("delete", 1);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Map-surfaces-2.js
@@ -0,0 +1,23 @@
+// Map methods throw when passed a this-value that isn't a Map.
+
+load(libdir + "asserts.js");
+
+function testcase(obj, fn) {
+    assertEq(typeof fn, "function");
+    var args = Array.slice(arguments, 2);
+    assertThrowsInstanceOf(function () { fn.apply(obj, args); }, TypeError);
+}
+
+function test(obj) {
+    testcase(obj, Map.prototype.get, "x");
+    testcase(obj, Map.prototype.has, "x");
+    testcase(obj, Map.prototype.set, "x", 1);
+    testcase(obj, Map.prototype.delete, "x");
+}
+
+test(Map.prototype);
+test(Object.create(new Map));
+test(new Set());
+test({});
+test(null);
+test(undefined);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Map-surfaces-3.js
@@ -0,0 +1,14 @@
+// Map methods work when arguments are omitted.
+
+var m = new Map;
+assertEq(m.has(), false);
+assertEq(m.get(), undefined);
+assertEq(m.delete(), false);
+assertEq(m.has(), false);
+assertEq(m.get(), undefined);
+assertEq(m.set(), undefined);
+assertEq(m.has(), true);
+assertEq(m.get(), undefined);
+assertEq(m.delete(), true);
+assertEq(m.has(), false);
+assertEq(m.get(), undefined);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Set-gc-1.js
@@ -0,0 +1,16 @@
+// Check marking through the elements of a Set.
+
+load(libdir + "referencesVia.js");
+
+var s = new Set;
+for (var i = 0; i < 20; i++) {
+    var t = new Set;
+    t.add(s);
+    assertEq(referencesVia(t, 'key', s), true);
+    s = t;
+}
+
+gc();
+gc();
+
+// TODO: walk the chain and make sure it's still intact
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Set-scale.js
@@ -0,0 +1,8 @@
+// Sets can hold at least 64K values.
+
+var N = 1 << 16;
+var s = new Set;
+for (var i = 0; i < N; i++)
+    assertEq(s.add(i), undefined);
+for (var i = 0; i < N; i++)
+    assertEq(s.has(i), true);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Set-surfaces-1.js
@@ -0,0 +1,32 @@
+// Set surfaces
+
+var desc = Object.getOwnPropertyDescriptor(this, "Set");
+assertEq(desc.enumerable, false);
+assertEq(desc.configurable, true);
+assertEq(desc.writable, true);
+
+assertEq(typeof Set, 'function');
+assertEq(Object.keys(Set).length, 0);
+assertEq(Set.length, 0);
+assertEq(Set.name, "Set");
+
+assertEq(Object.getPrototypeOf(Set.prototype), Object.prototype);
+assertEq(Object.prototype.toString.call(Set.prototype), "[object Set]");
+assertEq(Object.prototype.toString.call(new Set), "[object Set]");
+assertEq(Object.prototype.toString.call(Set()), "[object Set]");
+assertEq(Object.keys(Set.prototype).join(), "");
+assertEq(Set.prototype.constructor, Set);
+
+function checkMethod(name, arity) { 
+    var desc = Object.getOwnPropertyDescriptor(Set.prototype, name);
+    assertEq(desc.enumerable, false);
+    assertEq(desc.configurable, true);
+    assertEq(desc.writable, true);
+    assertEq(typeof desc.value, 'function');
+    assertEq(desc.value.name, name);
+    assertEq(desc.value.length, arity);
+}
+
+checkMethod("has", 1);
+checkMethod("add", 1);
+checkMethod("delete", 1);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Set-surfaces-2.js
@@ -0,0 +1,22 @@
+// Set methods throw when passed a this-value that isn't a Set.
+
+load(libdir + "asserts.js");
+
+function testcase(obj, fn) {
+    assertEq(typeof fn, "function");
+    var args = Array.slice(arguments, 2);
+    assertThrowsInstanceOf(function () { fn.apply(obj, args); }, TypeError);
+}
+
+function test(obj) {
+    testcase(obj, Set.prototype.has, 12);
+    testcase(obj, Set.prototype.add, 12);
+    testcase(obj, Set.prototype.delete, 12);
+}
+
+test(Set.prototype);
+test(Object.create(new Set));
+test(new Map());
+test({});
+test(null);
+test(undefined);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/Set-surfaces-3.js
@@ -0,0 +1,10 @@
+// Set methods work when arguments are omitted.
+
+var s = new Set;
+assertEq(s.has(), false);
+assertEq(s.delete(), false);
+assertEq(s.has(), false);
+assertEq(s.add(), undefined);
+assertEq(s.has(), true);
+assertEq(s.delete(), true);
+assertEq(s.has(), false);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/for-in.js
@@ -0,0 +1,25 @@
+// for-in loops on Maps and Sets enumerate properties.
+
+var test = function test(obj) {
+    assertEq(Object.keys(obj).length, 0);
+
+    var i = 0, v;
+    for (v in obj)
+        i++;
+    assertEq(i, 0);
+
+    obj.ownProp = 1;
+    assertEq(Object.keys(obj).join(), "ownProp");
+
+    for (v in obj)
+        i++;
+    assertEq(i, 1);
+    assertEq(v, "ownProp");
+
+    delete obj.ownProp;
+};
+
+test(Map.prototype);
+test(new Map);
+test(Set.prototype);
+test(new Set);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/key-equality-0.js
@@ -0,0 +1,37 @@
+// -0 is a distinct key from +0.
+
+var s = new Set;
+s.add(-0);
+assertEq(s.has(0), false);
+assertEq(s.has(-0), true);
+
+assertEq(s.delete(0), false);
+assertEq(s.has(-0), true);
+
+s.add(0);
+assertEq(s.delete(-0), true);
+assertEq(s.has(0), true);
+assertEq(s.has(-0), false);
+
+var m = new Map;
+m.set(-0, 'x');
+assertEq(m.has(0), false);
+assertEq(m.get(0), undefined);
+assertEq(m.has(-0), true);
+assertEq(m.get(-0), 'x');
+
+assertEq(m.delete(0), false);
+assertEq(m.has(-0), true);
+assertEq(m.get(-0), 'x');
+
+m.set(0, 'y');
+assertEq(m.has(0), true);
+assertEq(m.get(0), 'y');
+assertEq(m.has(-0), true);
+assertEq(m.get(-0), 'x');
+
+assertEq(m.delete(-0), true);
+assertEq(m.has(0), true);
+assertEq(m.get(0), 'y');
+assertEq(m.has(-0), false);
+assertEq(m.get(-0), undefined);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/key-equality-1.js
@@ -0,0 +1,28 @@
+// Different representations of the same number or string are treated as the same Map key.
+
+var m = new Map;
+var test = function test(a, b) {
+    m.set(a, 'secret');
+    assertEq(m.get(b), 'secret');
+    m.set(b, 'password');
+    assertEq(m.get(a), 'password');
+
+    assertEq(a, b);
+};
+
+// Float and integer representations of the same number are the same key.
+test(9, Math.sqrt(81));
+
+// Ordinary strings and ropes are the same key.
+var a = Array(1001).join('x');
+var b = Array(501).join('x') + Array(501).join('x');
+test(a, b);
+
+// Two structurally different ropes with the same characters are the same key.
+a = "";
+b = "";
+for (var i = 0; i < 10; i++) {
+    a = Array(501).join('x') + a;
+    b = b + Array(501).join('x');
+}
+test(a, b);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/key-equality-2.js
@@ -0,0 +1,11 @@
+// Number keys are distinct from string keys that would name the same property.
+
+var s = new Set;
+
+s.add(17);
+assertEq(s.has("17"), false);
+assertEq(s.has(17), true);
+s.add("17");
+assertEq(s.delete(17), true);
+assertEq(s.has("17"), true);
+assertEq(s.has(17), false);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/collections/key-equality-NaN.js
@@ -0,0 +1,15 @@
+// NaN is equal to itself for the purpose of key lookups.
+
+var m = new Map;
+m.set(NaN, "ok");
+assertEq(m.has(NaN), true);
+assertEq(m.get(NaN), "ok");
+assertEq(m.delete(NaN), true);
+assertEq(m.has(NaN), false);
+assertEq(m.get(NaN), undefined);
+
+var s = new Set;
+s.add(NaN);
+assertEq(s.has(NaN), true);
+assertEq(s.delete(NaN), true);
+assertEq(s.has(NaN), false);
--- a/js/src/jsapi.cpp
+++ b/js/src/jsapi.cpp
@@ -78,16 +78,17 @@
 #include "jsscript.h"
 #include "jsstr.h"
 #include "prmjtime.h"
 #include "jsweakmap.h"
 #include "jswrapper.h"
 #include "jstypedarray.h"
 
 #include "ds/LifoAlloc.h"
+#include "builtin/MapObject.h"
 #include "builtin/RegExp.h"
 #include "frontend/BytecodeCompiler.h"
 #include "frontend/BytecodeEmitter.h"
 #include "js/MemoryMetrics.h"
 #include "mozilla/Util.h" // DebugOnly
 
 #include "jsatominlines.h"
 #include "jsinferinlines.h"
@@ -1784,16 +1785,18 @@ static JSStdName standard_class_atoms[] 
     {js_InitQNameClass,                 EAGER_ATOM_AND_CLASP(QName)},
 #endif
 #if JS_HAS_GENERATORS
     {js_InitIteratorClasses,            EAGER_ATOM_AND_CLASP(StopIteration)},
 #endif
     {js_InitJSONClass,                  EAGER_ATOM_AND_CLASP(JSON)},
     {js_InitTypedArrayClasses,          EAGER_CLASS_ATOM(ArrayBuffer), &js::ArrayBuffer::slowClass},
     {js_InitWeakMapClass,               EAGER_CLASS_ATOM(WeakMap), &js::WeakMapClass},
+    {js_InitMapClass,                   EAGER_CLASS_ATOM(Map), &js::MapObject::class_},
+    {js_InitSetClass,                   EAGER_CLASS_ATOM(Set), &js::SetObject::class_},
     {NULL,                              0, NULL, NULL}
 };
 
 /*
  * Table of top-level function and constant names and their init functions.
  * If you add a "standard" global function or property, remember to update
  * this table.
  */
--- a/js/src/jsapi.h
+++ b/js/src/jsapi.h
@@ -562,16 +562,21 @@ class Value
 
     JS_ALWAYS_INLINE
     uint32_t payloadAsRawUint32() const {
         JS_ASSERT(!isDouble());
         return data.s.payload.u32;
     }
 
     JS_ALWAYS_INLINE
+    uint64_t asRawBits() const {
+        return data.asBits;
+    }
+
+    JS_ALWAYS_INLINE
     JSValueType extractNonDoubleType() const {
         return JSVAL_EXTRACT_NON_DOUBLE_TYPE_IMPL(data);
     }
 
     /*
      * Private API
      *
      * Private setters/getters allow the caller to read/write arbitrary types
--- a/js/src/jsobj.cpp
+++ b/js/src/jsobj.cpp
@@ -74,16 +74,17 @@
 #include "jsscript.h"
 #include "jsstdint.h"
 #include "jsstr.h"
 #include "jsdbgapi.h"
 #include "json.h"
 #include "jswatchpoint.h"
 #include "jswrapper.h"
 
+#include "builtin/MapObject.h"
 #include "frontend/BytecodeCompiler.h"
 #include "frontend/BytecodeEmitter.h"
 #include "frontend/Parser.h"
 #include "js/MemoryMetrics.h"
 
 #include "jsarrayinlines.h"
 #include "jsinterpinlines.h"
 #include "jsobjinlines.h"
@@ -6545,17 +6546,19 @@ js_GetterOnlyPropertyStub(JSContext *cx,
 
 void
 js::ReportIncompatibleMethod(JSContext *cx, CallReceiver call, Class *clasp)
 {
     Value &thisv = call.thisv();
 
 #ifdef DEBUG
     if (thisv.isObject()) {
-        JS_ASSERT(thisv.toObject().getClass() != clasp);
+        JS_ASSERT(thisv.toObject().getClass() != clasp ||
+                  !thisv.toObject().getProto() ||
+                  thisv.toObject().getProto()->getClass() != clasp);
     } else if (thisv.isString()) {
         JS_ASSERT(clasp != &StringClass);
     } else if (thisv.isNumber()) {
         JS_ASSERT(clasp != &NumberClass);
     } else if (thisv.isBoolean()) {
         JS_ASSERT(clasp != &BooleanClass);
     } else {
         JS_ASSERT(thisv.isUndefined() || thisv.isNull());
--- a/js/src/jsproto.tbl
+++ b/js/src/jsproto.tbl
@@ -87,12 +87,14 @@ JS_PROTO(Uint16Array,           28,     
 JS_PROTO(Int32Array,            29,     js_InitTypedArrayClasses)
 JS_PROTO(Uint32Array,           30,     js_InitTypedArrayClasses)
 JS_PROTO(Float32Array,          31,     js_InitTypedArrayClasses)
 JS_PROTO(Float64Array,          32,     js_InitTypedArrayClasses)
 JS_PROTO(Uint8ClampedArray,     33,     js_InitTypedArrayClasses)
 JS_PROTO(Proxy,                 34,     js_InitProxyClass)
 JS_PROTO(AnyName,               35,     js_InitNullClass)
 JS_PROTO(WeakMap,               36,     js_InitWeakMapClass)
+JS_PROTO(Map,                   37,     js_InitMapClass)
+JS_PROTO(Set,                   38,     js_InitSetClass)
 
 #undef XML_INIT
 #undef NAMESPACE_INIT
 #undef QNAME_INIT
--- a/js/src/vm/GlobalObject.cpp
+++ b/js/src/vm/GlobalObject.cpp
@@ -41,16 +41,17 @@
 #include "GlobalObject.h"
 
 #include "jscntxt.h"
 #include "jsexn.h"
 #include "jsmath.h"
 #include "json.h"
 #include "jsweakmap.h"
 
+#include "builtin/MapObject.h"
 #include "builtin/RegExp.h"
 #include "frontend/BytecodeEmitter.h"
 #include "vm/GlobalObject-inl.h"
 
 #include "jsobjinlines.h"
 #include "vm/RegExpObject-inl.h"
 #include "vm/RegExpStatics-inl.h"
 
@@ -316,17 +317,19 @@ GlobalObject::initStandardClasses(JSCont
 #if JS_HAS_XML_SUPPORT
            js_InitXMLClasses(cx, this) &&
 #endif
 #if JS_HAS_GENERATORS
            js_InitIteratorClasses(cx, this) &&
 #endif
            js_InitDateClass(cx, this) &&
            js_InitWeakMapClass(cx, this) &&
-           js_InitProxyClass(cx, this);
+           js_InitProxyClass(cx, this) &&
+           js_InitMapClass(cx, this) &&
+           js_InitSetClass(cx, this);
 }
 
 void
 GlobalObject::clear(JSContext *cx)
 {
     for (int key = JSProto_Null; key < JSProto_LIMIT * 3; key++)
         setSlot(key, UndefinedValue());