--- 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 \
 		RegExpObject.cpp \
 		RegExpStatics.cpp \
 		RegExp.cpp \
 		Statistics.cpp \
 		Unicode.cpp \
 		$(NULL)
 
 # Changes to internal header files, used externally, massively slow down

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
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *  Jason Orendorff <[email protected]>
+ *
+ * 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 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 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_ALWAYS_TRUE(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())
+        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())
+        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
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *  Jason Orendorff <[email protected]>
+ *
+ * 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
@@ -312,34 +312,37 @@ 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 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 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(); }
 
     inline void boxNonDoubleFrom(JSValueType type, uint64 *out);
 
     uint64 asRawBits() const { return value.asRawBits(); }
 
 #ifdef DEBUG

new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/lib/referencesVia.js
@@ -0,0 +1,26 @@
+function referencesVia(from, edge, to) {
+    if (typeof findReferences !== 'function')
+        return true;
+
+    edge = "edge: " + edge;
+    var edges = findReferences(to);
+    if (edge in edges && edges[edge].indexOf(from) != -1)
+        return true;
+
+    // Be nice: make it easy to fix if the edge name has just changed.
+    var alternatives = [];
+    for (var e in edges) {
+        if (edges[e].indexOf(from) != -1)
+            alternatives.push(e);
+    }
+    if (alternatives.length == 0) {
+        print("referent not referred to by referrer after all");
+    } else {
+        print("referent is not referenced via: " + uneval(edge));
+        print("but it is referenced via:       " + uneval(alternatives));
+    }
+    print("all incoming edges, from any object:");
+    for (var e in edges)
+        print(e);
+    return false;
+}

--- 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 "jsatominlines.h"
 #include "jsinferinlines.h"
 #include "jsobjinlines.h"
 #include "jsscopeinlines.h"
@@ -1718,16 +1719,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/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 "jsarrayinlines.h"
 #include "jsinterpinlines.h"
 #include "jsobjinlines.h"
 #include "jsscopeinlines.h"
@@ -7072,17 +7073,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
@@ -40,16 +40,17 @@
 
 #include "GlobalObject.h"
 
 #include "jscntxt.h"
 #include "jsexn.h"
 #include "jsmath.h"
 #include "json.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"
 
@@ -306,17 +307,19 @@ GlobalObject::initStandardClasses(JSCont
            js_InitTypedArrayClasses(cx, this) &&
 #if JS_HAS_XML_SUPPORT
            js_InitXMLClasses(cx, this) &&
 #endif
 #if JS_HAS_GENERATORS
            js_InitIteratorClasses(cx, this) &&
 #endif
            js_InitDateClass(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());