blob: 142e0a87ac72f59c9f8323aed518c3406b4487cb [file] [log] [blame]
// Copyright (C) 2011 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (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.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
/**
* @fileoverview Install a leaky WeakMap emulation on platforms that
* don't provide a built-in one.
*
* <p>Assumes that an ES5 platform where, if {@code WeakMap} is
* already present, then it conforms to the anticipated ES6
* specification. To run this file on an ES5 or almost ES5
* implementation where the {@code WeakMap} specification does not
* quite conform, run <code>repairES5.js</code> first.
*
* <p>Even though WeakMapModule is not global, the linter thinks it
* is, which is why it is in the overrides list below.
*
* <p>NOTE: Before using this WeakMap emulation in a non-SES
* environment, see the note below about hiddenRecord.
*
* @author Mark S. Miller
* @requires crypto, ArrayBuffer, Uint8Array, navigator, console
* @overrides WeakMap, ses, Proxy
* @overrides WeakMapModule
*/
/**
* This {@code WeakMap} emulation is observably equivalent to the
* ES-Harmony WeakMap, but with leakier garbage collection properties.
*
* <p>As with true WeakMaps, in this emulation, a key does not
* retain maps indexed by that key and (crucially) a map does not
* retain the keys it indexes. A map by itself also does not retain
* the values associated with that map.
*
* <p>However, the values associated with a key in some map are
* retained so long as that key is retained and those associations are
* not overridden. For example, when used to support membranes, all
* values exported from a given membrane will live for the lifetime
* they would have had in the absence of an interposed membrane. Even
* when the membrane is revoked, all objects that would have been
* reachable in the absence of revocation will still be reachable, as
* far as the GC can tell, even though they will no longer be relevant
* to ongoing computation.
*
* <p>The API implemented here is approximately the API as implemented
* in FF6.0a1 and agreed to by MarkM, Andreas Gal, and Dave Herman,
* rather than the offially approved proposal page. TODO(erights):
* upgrade the ecmascript WeakMap proposal page to explain this API
* change and present to EcmaScript committee for their approval.
*
* <p>The first difference between the emulation here and that in
* FF6.0a1 is the presence of non enumerable {@code get___, has___,
* set___, and delete___} methods on WeakMap instances to represent
* what would be the hidden internal properties of a primitive
* implementation. Whereas the FF6.0a1 WeakMap.prototype methods
* require their {@code this} to be a genuine WeakMap instance (i.e.,
* an object of {@code [[Class]]} "WeakMap}), since there is nothing
* unforgeable about the pseudo-internal method names used here,
* nothing prevents these emulated prototype methods from being
* applied to non-WeakMaps with pseudo-internal methods of the same
* names.
*
* <p>Another difference is that our emulated {@code
* WeakMap.prototype} is not itself a WeakMap. A problem with the
* current FF6.0a1 API is that WeakMap.prototype is itself a WeakMap
* providing ambient mutability and an ambient communications
* channel. Thus, if a WeakMap is already present and has this
* problem, repairES5.js wraps it in a safe wrappper in order to
* prevent access to this channel. (See
* PATCH_MUTABLE_FROZEN_WEAKMAP_PROTO in repairES5.js).
*/
/**
* If this is a full <a href=
* "http://code.google.com/p/es-lab/wiki/SecureableES5"
* >secureable ES5</a> platform and the ES-Harmony {@code WeakMap} is
* absent, install an approximate emulation.
*
* <p>If WeakMap is present but cannot store some objects, use our approximate
* emulation as a wrapper.
*
* <p>If this is almost a secureable ES5 platform, then WeakMap.js
* should be run after repairES5.js.
*
* <p>See {@code WeakMap} for documentation of the garbage collection
* properties of this WeakMap emulation.
*/
(function WeakMapModule() {
"use strict";
if (typeof ses !== 'undefined' && ses.ok && !ses.ok()) {
// already too broken, so give up
return;
}
/**
* In some cases (current Firefox), we must make a choice betweeen a
* WeakMap which is capable of using all varieties of host objects as
* keys and one which is capable of safely using proxies as keys. See
* comments below about HostWeakMap and DoubleWeakMap for details.
*
* This function (which is a global, not exposed to guests) marks a
* WeakMap as permitted to do what is necessary to index all host
* objects, at the cost of making it unsafe for proxies.
*
* Do not apply this function to anything which is not a genuine
* fresh WeakMap.
*/
function weakMapPermitHostObjects(map) {
// identity of function used as a secret -- good enough and cheap
if (map.permitHostObjects___) {
map.permitHostObjects___(weakMapPermitHostObjects);
}
}
if (typeof ses !== 'undefined') {
ses.weakMapPermitHostObjects = weakMapPermitHostObjects;
}
// IE 11 has no Proxy but has a broken WeakMap such that we need to patch
// it using DoubleWeakMap; this flag tells DoubleWeakMap so.
var doubleWeakMapCheckSilentFailure = false;
// Check if there is already a good-enough WeakMap implementation, and if so
// exit without replacing it.
if (typeof WeakMap === 'function') {
var HostWeakMap = WeakMap;
// There is a WeakMap -- is it good enough?
if (typeof navigator !== 'undefined' &&
/Firefox/.test(navigator.userAgent)) {
// We're now *assuming not*, because as of this writing (2013-05-06)
// Firefox's WeakMaps have a miscellany of objects they won't accept, and
// we don't want to make an exhaustive list, and testing for just one
// will be a problem if that one is fixed alone (as they did for Event).
// If there is a platform that we *can* reliably test on, here's how to
// do it:
// var problematic = ... ;
// var testHostMap = new HostWeakMap();
// try {
// testHostMap.set(problematic, 1); // Firefox 20 will throw here
// if (testHostMap.get(problematic) === 1) {
// return;
// }
// } catch (e) {}
} else {
// IE 11 bug: WeakMaps silently fail to store frozen objects.
var testMap = new HostWeakMap();
var testObject = Object.freeze({});
testMap.set(testObject, 1);
if (testMap.get(testObject) !== 1) {
doubleWeakMapCheckSilentFailure = true;
// Fall through to installing our WeakMap.
} else {
module.exports = WeakMap;
return;
}
}
}
var hop = Object.prototype.hasOwnProperty;
var gopn = Object.getOwnPropertyNames;
var defProp = Object.defineProperty;
var isExtensible = Object.isExtensible;
/**
* Security depends on HIDDEN_NAME being both <i>unguessable</i> and
* <i>undiscoverable</i> by untrusted code.
*
* <p>Given the known weaknesses of Math.random() on existing
* browsers, it does not generate unguessability we can be confident
* of.
*
* <p>It is the monkey patching logic in this file that is intended
* to ensure undiscoverability. The basic idea is that there are
* three fundamental means of discovering properties of an object:
* The for/in loop, Object.keys(), and Object.getOwnPropertyNames(),
* as well as some proposed ES6 extensions that appear on our
* whitelist. The first two only discover enumerable properties, and
* we only use HIDDEN_NAME to name a non-enumerable property, so the
* only remaining threat should be getOwnPropertyNames and some
* proposed ES6 extensions that appear on our whitelist. We monkey
* patch them to remove HIDDEN_NAME from the list of properties they
* returns.
*
* <p>TODO(erights): On a platform with built-in Proxies, proxies
* could be used to trap and thereby discover the HIDDEN_NAME, so we
* need to monkey patch Proxy.create, Proxy.createFunction, etc, in
* order to wrap the provided handler with the real handler which
* filters out all traps using HIDDEN_NAME.
*
* <p>TODO(erights): Revisit Mike Stay's suggestion that we use an
* encapsulated function at a not-necessarily-secret name, which
* uses the Stiegler shared-state rights amplification pattern to
* reveal the associated value only to the WeakMap in which this key
* is associated with that value. Since only the key retains the
* function, the function can also remember the key without causing
* leakage of the key, so this doesn't violate our general gc
* goals. In addition, because the name need not be a guarded
* secret, we could efficiently handle cross-frame frozen keys.
*/
var HIDDEN_NAME_PREFIX = 'weakmap:';
var HIDDEN_NAME = HIDDEN_NAME_PREFIX + 'ident:' + Math.random() + '___';
if (typeof crypto !== 'undefined' &&
typeof crypto.getRandomValues === 'function' &&
typeof ArrayBuffer === 'function' &&
typeof Uint8Array === 'function') {
var ab = new ArrayBuffer(25);
var u8s = new Uint8Array(ab);
crypto.getRandomValues(u8s);
HIDDEN_NAME = HIDDEN_NAME_PREFIX + 'rand:' +
Array.prototype.map.call(u8s, function(u8) {
return (u8 % 36).toString(36);
}).join('') + '___';
}
function isNotHiddenName(name) {
return !(
name.substr(0, HIDDEN_NAME_PREFIX.length) == HIDDEN_NAME_PREFIX &&
name.substr(name.length - 3) === '___');
}
/**
* Monkey patch getOwnPropertyNames to avoid revealing the
* HIDDEN_NAME.
*
* <p>The ES5.1 spec requires each name to appear only once, but as
* of this writing, this requirement is controversial for ES6, so we
* made this code robust against this case. If the resulting extra
* search turns out to be expensive, we can probably relax this once
* ES6 is adequately supported on all major browsers, iff no browser
* versions we support at that time have relaxed this constraint
* without providing built-in ES6 WeakMaps.
*/
defProp(Object, 'getOwnPropertyNames', {
value: function fakeGetOwnPropertyNames(obj) {
return gopn(obj).filter(isNotHiddenName);
}
});
/**
* getPropertyNames is not in ES5 but it is proposed for ES6 and
* does appear in our whitelist, so we need to clean it too.
*/
if ('getPropertyNames' in Object) {
var originalGetPropertyNames = Object.getPropertyNames;
defProp(Object, 'getPropertyNames', {
value: function fakeGetPropertyNames(obj) {
return originalGetPropertyNames(obj).filter(isNotHiddenName);
}
});
}
/**
* <p>To treat objects as identity-keys with reasonable efficiency
* on ES5 by itself (i.e., without any object-keyed collections), we
* need to add a hidden property to such key objects when we
* can. This raises several issues:
* <ul>
* <li>Arranging to add this property to objects before we lose the
* chance, and
* <li>Hiding the existence of this new property from most
* JavaScript code.
* <li>Preventing <i>certification theft</i>, where one object is
* created falsely claiming to be the key of an association
* actually keyed by another object.
* <li>Preventing <i>value theft</i>, where untrusted code with
* access to a key object but not a weak map nevertheless
* obtains access to the value associated with that key in that
* weak map.
* </ul>
* We do so by
* <ul>
* <li>Making the name of the hidden property unguessable, so "[]"
* indexing, which we cannot intercept, cannot be used to access
* a property without knowing the name.
* <li>Making the hidden property non-enumerable, so we need not
* worry about for-in loops or {@code Object.keys},
* <li>monkey patching those reflective methods that would
* prevent extensions, to add this hidden property first,
* <li>monkey patching those methods that would reveal this
* hidden property.
* </ul>
* Unfortunately, because of same-origin iframes, we cannot reliably
* add this hidden property before an object becomes
* non-extensible. Instead, if we encounter a non-extensible object
* without a hidden record that we can detect (whether or not it has
* a hidden record stored under a name secret to us), then we just
* use the key object itself to represent its identity in a brute
* force leaky map stored in the weak map, losing all the advantages
* of weakness for these.
*/
function getHiddenRecord(key) {
if (key !== Object(key)) {
throw new TypeError('Not an object: ' + key);
}
var hiddenRecord = key[HIDDEN_NAME];
if (hiddenRecord && hiddenRecord.key === key) { return hiddenRecord; }
if (!isExtensible(key)) {
// Weak map must brute force, as explained in doc-comment above.
return void 0;
}
// The hiddenRecord and the key point directly at each other, via
// the "key" and HIDDEN_NAME properties respectively. The key
// field is for quickly verifying that this hidden record is an
// own property, not a hidden record from up the prototype chain.
//
// NOTE: Because this WeakMap emulation is meant only for systems like
// SES where Object.prototype is frozen without any numeric
// properties, it is ok to use an object literal for the hiddenRecord.
// This has two advantages:
// * It is much faster in a performance critical place
// * It avoids relying on Object.create(null), which had been
// problematic on Chrome 28.0.1480.0. See
// https://code.google.com/p/google-caja/issues/detail?id=1687
hiddenRecord = { key: key };
// When using this WeakMap emulation on platforms where
// Object.prototype might not be frozen and Object.create(null) is
// reliable, use the following two commented out lines instead.
// hiddenRecord = Object.create(null);
// hiddenRecord.key = key;
// Please contact us if you need this to work on platforms where
// Object.prototype might not be frozen and
// Object.create(null) might not be reliable.
try {
defProp(key, HIDDEN_NAME, {
value: hiddenRecord,
writable: false,
enumerable: false,
configurable: false
});
return hiddenRecord;
} catch (error) {
// Under some circumstances, isExtensible seems to misreport whether
// the HIDDEN_NAME can be defined.
// The circumstances have not been isolated, but at least affect
// Node.js v0.10.26 on TravisCI / Linux, but not the same version of
// Node.js on OS X.
return void 0;
}
}
/**
* Monkey patch operations that would make their argument
* non-extensible.
*
* <p>The monkey patched versions throw a TypeError if their
* argument is not an object, so it should only be done to functions
* that should throw a TypeError anyway if their argument is not an
* object.
*/
(function(){
var oldFreeze = Object.freeze;
defProp(Object, 'freeze', {
value: function identifyingFreeze(obj) {
getHiddenRecord(obj);
return oldFreeze(obj);
}
});
var oldSeal = Object.seal;
defProp(Object, 'seal', {
value: function identifyingSeal(obj) {
getHiddenRecord(obj);
return oldSeal(obj);
}
});
var oldPreventExtensions = Object.preventExtensions;
defProp(Object, 'preventExtensions', {
value: function identifyingPreventExtensions(obj) {
getHiddenRecord(obj);
return oldPreventExtensions(obj);
}
});
})();
function constFunc(func) {
func.prototype = null;
return Object.freeze(func);
}
var calledAsFunctionWarningDone = false;
function calledAsFunctionWarning() {
// Future ES6 WeakMap is currently (2013-09-10) expected to reject WeakMap()
// but we used to permit it and do it ourselves, so warn only.
if (!calledAsFunctionWarningDone && typeof console !== 'undefined') {
calledAsFunctionWarningDone = true;
console.warn('WeakMap should be invoked as new WeakMap(), not ' +
'WeakMap(). This will be an error in the future.');
}
}
var nextId = 0;
var OurWeakMap = function() {
if (!(this instanceof OurWeakMap)) { // approximate test for new ...()
calledAsFunctionWarning();
}
// We are currently (12/25/2012) never encountering any prematurely
// non-extensible keys.
var keys = []; // brute force for prematurely non-extensible keys.
var values = []; // brute force for corresponding values.
var id = nextId++;
function get___(key, opt_default) {
var index;
var hiddenRecord = getHiddenRecord(key);
if (hiddenRecord) {
return id in hiddenRecord ? hiddenRecord[id] : opt_default;
} else {
index = keys.indexOf(key);
return index >= 0 ? values[index] : opt_default;
}
}
function has___(key) {
var hiddenRecord = getHiddenRecord(key);
if (hiddenRecord) {
return id in hiddenRecord;
} else {
return keys.indexOf(key) >= 0;
}
}
function set___(key, value) {
var index;
var hiddenRecord = getHiddenRecord(key);
if (hiddenRecord) {
hiddenRecord[id] = value;
} else {
index = keys.indexOf(key);
if (index >= 0) {
values[index] = value;
} else {
// Since some browsers preemptively terminate slow turns but
// then continue computing with presumably corrupted heap
// state, we here defensively get keys.length first and then
// use it to update both the values and keys arrays, keeping
// them in sync.
index = keys.length;
values[index] = value;
// If we crash here, values will be one longer than keys.
keys[index] = key;
}
}
return this;
}
function delete___(key) {
var hiddenRecord = getHiddenRecord(key);
var index, lastIndex;
if (hiddenRecord) {
return id in hiddenRecord && delete hiddenRecord[id];
} else {
index = keys.indexOf(key);
if (index < 0) {
return false;
}
// Since some browsers preemptively terminate slow turns but
// then continue computing with potentially corrupted heap
// state, we here defensively get keys.length first and then use
// it to update both the keys and the values array, keeping
// them in sync. We update the two with an order of assignments,
// such that any prefix of these assignments will preserve the
// key/value correspondence, either before or after the delete.
// Note that this needs to work correctly when index === lastIndex.
lastIndex = keys.length - 1;
keys[index] = void 0;
// If we crash here, there's a void 0 in the keys array, but
// no operation will cause a "keys.indexOf(void 0)", since
// getHiddenRecord(void 0) will always throw an error first.
values[index] = values[lastIndex];
// If we crash here, values[index] cannot be found here,
// because keys[index] is void 0.
keys[index] = keys[lastIndex];
// If index === lastIndex and we crash here, then keys[index]
// is still void 0, since the aliasing killed the previous key.
keys.length = lastIndex;
// If we crash here, keys will be one shorter than values.
values.length = lastIndex;
return true;
}
}
return Object.create(OurWeakMap.prototype, {
get___: { value: constFunc(get___) },
has___: { value: constFunc(has___) },
set___: { value: constFunc(set___) },
delete___: { value: constFunc(delete___) }
});
};
OurWeakMap.prototype = Object.create(Object.prototype, {
get: {
/**
* Return the value most recently associated with key, or
* opt_default if none.
*/
value: function get(key, opt_default) {
return this.get___(key, opt_default);
},
writable: true,
configurable: true
},
has: {
/**
* Is there a value associated with key in this WeakMap?
*/
value: function has(key) {
return this.has___(key);
},
writable: true,
configurable: true
},
set: {
/**
* Associate value with key in this WeakMap, overwriting any
* previous association if present.
*/
value: function set(key, value) {
return this.set___(key, value);
},
writable: true,
configurable: true
},
'delete': {
/**
* Remove any association for key in this WeakMap, returning
* whether there was one.
*
* <p>Note that the boolean return here does not work like the
* {@code delete} operator. The {@code delete} operator returns
* whether the deletion succeeds at bringing about a state in
* which the deleted property is absent. The {@code delete}
* operator therefore returns true if the property was already
* absent, whereas this {@code delete} method returns false if
* the association was already absent.
*/
value: function remove(key) {
return this.delete___(key);
},
writable: true,
configurable: true
}
});
if (typeof HostWeakMap === 'function') {
(function() {
// If we got here, then the platform has a WeakMap but we are concerned
// that it may refuse to store some key types. Therefore, make a map
// implementation which makes use of both as possible.
// In this mode we are always using double maps, so we are not proxy-safe.
// This combination does not occur in any known browser, but we had best
// be safe.
if (doubleWeakMapCheckSilentFailure && typeof Proxy !== 'undefined') {
Proxy = undefined;
}
function DoubleWeakMap() {
if (!(this instanceof OurWeakMap)) { // approximate test for new ...()
calledAsFunctionWarning();
}
// Preferable, truly weak map.
var hmap = new HostWeakMap();
// Our hidden-property-based pseudo-weak-map. Lazily initialized in the
// 'set' implementation; thus we can avoid performing extra lookups if
// we know all entries actually stored are entered in 'hmap'.
var omap = undefined;
// Hidden-property maps are not compatible with proxies because proxies
// can observe the hidden name and either accidentally expose it or fail
// to allow the hidden property to be set. Therefore, we do not allow
// arbitrary WeakMaps to switch to using hidden properties, but only
// those which need the ability, and unprivileged code is not allowed
// to set the flag.
//
// (Except in doubleWeakMapCheckSilentFailure mode in which case we
// disable proxies.)
var enableSwitching = false;
function dget(key, opt_default) {
if (omap) {
return hmap.has(key) ? hmap.get(key)
: omap.get___(key, opt_default);
} else {
return hmap.get(key, opt_default);
}
}
function dhas(key) {
return hmap.has(key) || (omap ? omap.has___(key) : false);
}
var dset;
if (doubleWeakMapCheckSilentFailure) {
dset = function(key, value) {
hmap.set(key, value);
if (!hmap.has(key)) {
if (!omap) { omap = new OurWeakMap(); }
omap.set(key, value);
}
return this;
};
} else {
dset = function(key, value) {
if (enableSwitching) {
try {
hmap.set(key, value);
} catch (e) {
if (!omap) { omap = new OurWeakMap(); }
omap.set___(key, value);
}
} else {
hmap.set(key, value);
}
return this;
};
}
function ddelete(key) {
var result = !!hmap['delete'](key);
if (omap) { return omap.delete___(key) || result; }
return result;
}
return Object.create(OurWeakMap.prototype, {
get___: { value: constFunc(dget) },
has___: { value: constFunc(dhas) },
set___: { value: constFunc(dset) },
delete___: { value: constFunc(ddelete) },
permitHostObjects___: { value: constFunc(function(token) {
if (token === weakMapPermitHostObjects) {
enableSwitching = true;
} else {
throw new Error('bogus call to permitHostObjects___');
}
})}
});
}
DoubleWeakMap.prototype = OurWeakMap.prototype;
module.exports = DoubleWeakMap;
// define .constructor to hide OurWeakMap ctor
Object.defineProperty(WeakMap.prototype, 'constructor', {
value: WeakMap,
enumerable: false, // as default .constructor is
configurable: true,
writable: true
});
})();
} else {
// There is no host WeakMap, so we must use the emulation.
// Emulated WeakMaps are incompatible with native proxies (because proxies
// can observe the hidden name), so we must disable Proxy usage (in
// ArrayLike and Domado, currently).
if (typeof Proxy !== 'undefined') {
Proxy = undefined;
}
module.exports = OurWeakMap;
}
})();