Files
2023-08-01 13:49:46 +02:00

526 lines
26 KiB
JavaScript

"use strict";
Object.defineProperty(exports, "__esModule", {
value: true
});
exports.WidenImplementation = undefined;
var _slicedToArray = function () { function sliceIterator(arr, i) { var _arr = []; var _n = true; var _d = false; var _e = undefined; try { for (var _i = arr[Symbol.iterator](), _s; !(_n = (_s = _i.next()).done); _n = true) { _arr.push(_s.value); if (i && _arr.length === i) break; } } catch (err) { _d = true; _e = err; } finally { try { if (!_n && _i["return"]) _i["return"](); } finally { if (_d) throw _e; } } return _arr; } return function (arr, i) { if (Array.isArray(arr)) { return arr; } else if (Symbol.iterator in Object(arr)) { return sliceIterator(arr, i); } else { throw new TypeError("Invalid attempt to destructure non-iterable instance"); } }; }();
var _createClass = function () { function defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } } return function (Constructor, protoProps, staticProps) { if (protoProps) defineProperties(Constructor.prototype, protoProps); if (staticProps) defineProperties(Constructor, staticProps); return Constructor; }; }(); /**
* Copyright (c) 2017-present, Facebook, Inc.
* All rights reserved.
*
* This source code is licensed under the BSD-style license found in the
* LICENSE file in the root directory of this source tree. An additional grant
* of patent rights can be found in the PATENTS file in the same directory.
*/
var _errors = require("../errors.js");
var _completions = require("../completions.js");
var _environment = require("../environment.js");
var _index = require("../methods/index.js");
var _generator = require("../utils/generator.js");
var _index2 = require("../values/index.js");
var _invariant = require("../invariant.js");
var _invariant2 = _interopRequireDefault(_invariant);
var _babelTypes = require("babel-types");
var t = _interopRequireWildcard(_babelTypes);
function _interopRequireWildcard(obj) { if (obj && obj.__esModule) { return obj; } else { var newObj = {}; if (obj != null) { for (var key in obj) { if (Object.prototype.hasOwnProperty.call(obj, key)) newObj[key] = obj[key]; } } newObj.default = obj; return newObj; } }
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }
function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }
var WidenImplementation = exports.WidenImplementation = function () {
function WidenImplementation() {
_classCallCheck(this, WidenImplementation);
}
_createClass(WidenImplementation, [{
key: "_widenArrays",
value: function _widenArrays(realm, v1, v2) {
var e = v1 && v1[0] || v2 && v2[0];
if (e instanceof _index2.Value) return this._widenArraysOfValues(realm, v1, v2);else return this._widenArrayOfsMapEntries(realm, v1, v2);
}
}, {
key: "_widenArrayOfsMapEntries",
value: function _widenArrayOfsMapEntries(realm, a1, a2) {
var empty = realm.intrinsics.empty;
var n = Math.max(a1 && a1.length || 0, a2 && a2.length || 0);
var result = [];
for (var i = 0; i < n; i++) {
var _ref = a1 && a1[i] || { $Key: empty, $Value: empty },
key1 = _ref.$Key,
val1 = _ref.$Value;
var _ref2 = a2 && a2[i] || { $Key: empty, $Value: empty },
key2 = _ref2.$Key,
val2 = _ref2.$Value;
if (key1 === undefined && key2 === undefined) {
result[i] = { $Key: undefined, $Value: undefined };
} else {
var key3 = this.widenValues(realm, key1, key2);
(0, _invariant2.default)(key3 instanceof _index2.Value);
var val3 = this.widenValues(realm, val1, val2);
(0, _invariant2.default)(val3 === undefined || val3 instanceof _index2.Value);
result[i] = { $Key: key3, $Value: val3 };
}
}
return result;
}
}, {
key: "_widenArraysOfValues",
value: function _widenArraysOfValues(realm, a1, a2) {
var n = Math.max(a1 && a1.length || 0, a2 && a2.length || 0);
var result = [];
for (var i = 0; i < n; i++) {
var wv = this.widenValues(realm, a1 && a1[i] || undefined, a2 && a2[i] || undefined);
(0, _invariant2.default)(wv === undefined || wv instanceof _index2.Value);
result[i] = wv;
}
return result;
}
// Returns a new effects summary that includes both e1 and e2.
}, {
key: "widenEffects",
value: function widenEffects(realm, e1, e2) {
var _e = _slicedToArray(e1, 5),
result1 = _e[0],
bindings1 = _e[2],
properties1 = _e[3],
createdObj1 = _e[4];
var _e2 = _slicedToArray(e2, 5),
result2 = _e2[0],
bindings2 = _e2[2],
properties2 = _e2[3],
createdObj2 = _e2[4];
var result = this.widenResults(realm, result1, result2);
var bindings = this.widenBindings(realm, bindings1, bindings2);
var properties = this.widenPropertyBindings(realm, properties1, properties2, createdObj1, createdObj2);
var createdObjects = new Set(); // Top, since the empty set knows nothing. There is no other choice for widen.
var generator = new _generator.Generator(realm, "widen"); // code subject to widening will be generated somewhere else
return [result, generator, bindings, properties, createdObjects];
}
}, {
key: "widenResults",
value: function widenResults(realm, result1, result2) {
(0, _invariant2.default)(!(result1 instanceof _environment.Reference || result2 instanceof _environment.Reference), "loop bodies should not result in refs");
(0, _invariant2.default)(!(result1 instanceof _completions.AbruptCompletion || result2 instanceof _completions.AbruptCompletion), "if a loop iteration ends abruptly, there is no need for fixed point computation");
if (result1 instanceof _index2.Value && result2 instanceof _index2.Value) {
var val = this.widenValues(realm, result1, result2);
(0, _invariant2.default)(val instanceof _index2.Value);
return val;
}
if (result1 instanceof _completions.PossiblyNormalCompletion || result2 instanceof _completions.PossiblyNormalCompletion) {
//todo: #1174 figure out how to deal with loops that have embedded conditional exits
// widen join pathConditions
// widen normal result and Effects
// use abrupt part of result2, depend stability to make this safe. See below.
throw new _errors.FatalError();
}
(0, _invariant2.default)(false);
}
}, {
key: "widenMaps",
value: function widenMaps(m1, m2, widen) {
var m3 = new Map();
m1.forEach(function (val1, key, map1) {
var val2 = m2.get(key);
var val3 = widen(key, val1, val2);
m3.set(key, val3);
});
m2.forEach(function (val2, key, map2) {
if (!m1.has(key)) {
m3.set(key, widen(key, undefined, val2));
}
});
return m3;
}
}, {
key: "widenBindings",
value: function widenBindings(realm, m1, m2) {
var _this = this;
var widen = function widen(b, b1, b2) {
var l1 = b1 === undefined ? b.hasLeaked : b1.hasLeaked;
var l2 = b2 === undefined ? b.hasLeaked : b2.hasLeaked;
var hasLeaked = l1 || l2; // If either has leaked, then this binding has leaked.
var v1 = b1 === undefined || b1.value === undefined ? b.value : b1.value;
(0, _invariant2.default)(b2 !== undefined); // Local variables are not going to get deleted as a result of widening
var v2 = b2.value;
(0, _invariant2.default)(v2 !== undefined);
var result = _this.widenValues(realm, v1, v2);
if (result instanceof _index2.AbstractValue && result.kind === "widened") {
var phiNode = b.phiNode;
if (phiNode === undefined) {
// Create a temporal location for binding
var generator = realm.generator;
(0, _invariant2.default)(generator !== undefined);
phiNode = generator.derive(result.types, result.values, [b.value || realm.intrinsics.undefined], function (_ref3) {
var _ref4 = _slicedToArray(_ref3, 1),
n = _ref4[0];
return n;
}, {
skipInvariant: true
});
b.phiNode = phiNode;
}
// Let the widened value be a reference to the phiNode of the binding
(0, _invariant2.default)(phiNode.intrinsicName !== undefined);
var phiName = phiNode.intrinsicName;
result.intrinsicName = phiName;
result._buildNode = function (args) {
return t.identifier(phiName);
};
}
(0, _invariant2.default)(result instanceof _index2.Value);
return { hasLeaked: hasLeaked, value: result };
};
return this.widenMaps(m1, m2, widen);
}
// Returns an abstract value that includes both v1 and v2 as potential values.
}, {
key: "widenValues",
value: function widenValues(realm, v1, v2) {
if (Array.isArray(v1) || Array.isArray(v2)) {
(0, _invariant2.default)(v1 === undefined || Array.isArray(v1));
(0, _invariant2.default)(v2 === undefined || Array.isArray(v2));
return this._widenArrays(realm, v1, v2);
}
(0, _invariant2.default)(v1 === undefined || v1 instanceof _index2.Value);
(0, _invariant2.default)(v2 === undefined || v2 instanceof _index2.Value);
if (v1 !== undefined && v2 !== undefined && !(v1 instanceof _index2.AbstractValue) && !(v2 instanceof _index2.AbstractValue) && (0, _index.StrictEqualityComparison)(realm, v1.throwIfNotConcrete(), v2.throwIfNotConcrete())) {
return v1; // no need to widen a loop invariant value
} else {
return _index2.AbstractValue.createFromWidening(realm, v1 || realm.intrinsics.empty, v2 || realm.intrinsics.undefined);
}
}
}, {
key: "widenPropertyBindings",
value: function widenPropertyBindings(realm, m1, m2, c1, c2) {
var _this2 = this;
var widen = function widen(b, d1, d2) {
if (d1 === undefined && d2 === undefined) return undefined;
// If the PropertyBinding object has been freshly allocated do not widen (that happens in AbstractObjectValue)
if (d1 === undefined) {
if (b.object instanceof _index2.ObjectValue && c2.has(b.object)) return d2; // no widen
if (b.descriptor !== undefined && m1.has(b)) {
// property was present in (n-1)th iteration and deleted in nth iteration
d1 = (0, _index.cloneDescriptor)(b.descriptor);
(0, _invariant2.default)(d1 !== undefined);
d1.value = realm.intrinsics.empty;
} else {
// no write to property in nth iteration, use the value from the (n-1)th iteration
d1 = b.descriptor;
if (d1 === undefined) {
d1 = (0, _index.cloneDescriptor)(d2);
(0, _invariant2.default)(d1 !== undefined);
d1.value = realm.intrinsics.empty;
}
}
}
if (d2 === undefined) {
if (b.object instanceof _index2.ObjectValue && c1.has(b.object)) return d1; // no widen
if (m2.has(b)) {
// property was present in nth iteration and deleted in (n+1)th iteration
d2 = (0, _index.cloneDescriptor)(d1);
(0, _invariant2.default)(d2 !== undefined);
d2.value = realm.intrinsics.empty;
} else {
// no write to property in (n+1)th iteration, use the value from the nth iteration
d2 = d1;
}
(0, _invariant2.default)(d2 !== undefined);
}
var result = _this2.widenDescriptors(realm, d1, d2);
if (result && result.value instanceof _index2.AbstractValue && result.value.kind === "widened") {
var rval = result.value;
var pathNode = b.pathNode;
if (pathNode === undefined) {
//Since properties already have mutable storage locations associated with them, we do not
//need phi nodes. What we need is an abstract value with a build node that results in a memberExpression
//that resolves to the storage location of the property.
// For now, we only handle loop invariant properties
//i.e. properties where the member expresssion does not involve any values written to inside the loop.
var key = b.key;
if (typeof key === "string" || !(key.mightNotBeString() && key.mightNotBeNumber())) {
if (typeof key === "string") {
pathNode = _index2.AbstractValue.createFromWidenedProperty(realm, rval, [b.object], function (_ref5) {
var _ref6 = _slicedToArray(_ref5, 1),
o = _ref6[0];
return t.memberExpression(o, t.identifier(key));
});
} else {
pathNode = _index2.AbstractValue.createFromWidenedProperty(realm, rval, [b.object, key], function (_ref7) {
var _ref8 = _slicedToArray(_ref7, 2),
o = _ref8[0],
p = _ref8[1];
return t.memberExpression(o, p, true);
});
}
// The value of the property at the start of the loop needs to be written to the property
// before the loop commences, otherwise the memberExpression will result in an undefined value.
var generator = realm.generator;
(0, _invariant2.default)(generator !== undefined);
var initVal = b.descriptor && b.descriptor.value || realm.intrinsics.empty;
if (!(initVal instanceof _index2.Value)) throw new _errors.FatalError("todo: handle internal properties");
if (!(initVal instanceof _index2.EmptyValue)) {
if (key === "length" && b.object instanceof _index2.ArrayValue) {
// do nothing, the array length will already be initialized
} else if (typeof key === "string") {
generator.emitVoidExpression(rval.types, rval.values, [b.object, initVal], function (_ref9) {
var _ref10 = _slicedToArray(_ref9, 2),
o = _ref10[0],
v = _ref10[1];
return t.assignmentExpression("=", t.memberExpression(o, t.identifier(key)), v);
});
} else {
generator.emitVoidExpression(rval.types, rval.values, [b.object, b.key, initVal], function (_ref11) {
var _ref12 = _slicedToArray(_ref11, 3),
o = _ref12[0],
p = _ref12[1],
v = _ref12[2];
return t.assignmentExpression("=", t.memberExpression(o, p, true), v);
});
}
}
} else {
throw new _errors.FatalError("todo: handle the case where key is an abstract value");
}
b.pathNode = pathNode;
}
result.value = pathNode;
}
return result;
};
return this.widenMaps(m1, m2, widen);
}
}, {
key: "widenDescriptors",
value: function widenDescriptors(realm, d1, d2) {
if (d1 === undefined) {
// d2 is a property written to only in the (n+1)th iteration
if (!(0, _index.IsDataDescriptor)(realm, d2)) return d2; // accessor properties need not be widened.
var dc = (0, _index.cloneDescriptor)(d2);
(0, _invariant2.default)(dc !== undefined);
dc.value = this.widenValues(realm, d2.value, d2.value);
return dc;
} else {
if ((0, _index.equalDescriptors)(d1, d2)) {
if (!(0, _index.IsDataDescriptor)(realm, d1)) return d1; // identical accessor properties need not be widened.
var _dc = (0, _index.cloneDescriptor)(d1);
(0, _invariant2.default)(_dc !== undefined);
_dc.value = this.widenValues(realm, d1.value, d2.value);
return _dc;
}
//todo: #1174 if we get here, the loop body contains a call to create a property and different iterations
// create them differently. That seems beyond what a fixpoint computation can reasonably handle without
// losing precision. Report an error here.
throw new _errors.FatalError();
}
}
// If e2 is the result of a loop iteration starting with effects e1 and it has a subset of elements of e1,
// then we have reached a fixed point and no further calls to widen are needed. e1/e2 represent a general
// summary of the loop, regardless of how many iterations will be performed at runtime.
}, {
key: "containsEffects",
value: function containsEffects(e1, e2) {
var _e3 = _slicedToArray(e1, 4),
result1 = _e3[0],
bindings1 = _e3[2],
properties1 = _e3[3];
var _e4 = _slicedToArray(e2, 4),
result2 = _e4[0],
bindings2 = _e4[2],
properties2 = _e4[3];
if (!this.containsResults(result1, result2)) return false;
if (!this.containsBindings(bindings1, bindings2)) return false;
if (!this.containsPropertyBindings(properties1, properties2)) return false;
return true;
}
}, {
key: "containsResults",
value: function containsResults(result1, result2) {
if (result1 instanceof _index2.Value && result2 instanceof _index2.Value) return this._containsValues(result1, result2);
return false;
}
}, {
key: "containsMap",
value: function containsMap(m1, m2, f) {
var _iteratorNormalCompletion = true;
var _didIteratorError = false;
var _iteratorError = undefined;
try {
for (var _iterator = m1.entries()[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) {
var _ref13 = _step.value;
var _ref14 = _slicedToArray(_ref13, 2);
var key1 = _ref14[0];
var val1 = _ref14[1];
if (val1 === undefined) continue; // deleted
var val2 = m2.get(key1);
if (val2 === undefined) continue; // A key that disappears has been widened away into the unknown key
if (!f(val1, val2)) return false;
}
} catch (err) {
_didIteratorError = true;
_iteratorError = err;
} finally {
try {
if (!_iteratorNormalCompletion && _iterator.return) {
_iterator.return();
}
} finally {
if (_didIteratorError) {
throw _iteratorError;
}
}
}
var _iteratorNormalCompletion2 = true;
var _didIteratorError2 = false;
var _iteratorError2 = undefined;
try {
for (var _iterator2 = m2.keys()[Symbol.iterator](), _step2; !(_iteratorNormalCompletion2 = (_step2 = _iterator2.next()).done); _iteratorNormalCompletion2 = true) {
var key2 = _step2.value;
if (!m1.has(key2)) return false;
}
} catch (err) {
_didIteratorError2 = true;
_iteratorError2 = err;
} finally {
try {
if (!_iteratorNormalCompletion2 && _iterator2.return) {
_iterator2.return();
}
} finally {
if (_didIteratorError2) {
throw _iteratorError2;
}
}
}
return true;
}
}, {
key: "containsBindings",
value: function containsBindings(m1, m2) {
var _this3 = this;
var containsBinding = function containsBinding(b1, b2) {
if (b1 === undefined || b2 === undefined || b1.value === undefined || b2.value === undefined || !_this3._containsValues(b1.value, b2.value) || b1.hasLeaked !== b2.hasLeaked) {
return false;
}
return true;
};
return this.containsMap(m1, m2, containsBinding);
}
}, {
key: "containsPropertyBindings",
value: function containsPropertyBindings(m1, m2) {
var _this4 = this;
var containsPropertyBinding = function containsPropertyBinding(d1, d2) {
var v1 = d1 && d1.value,
v2 = d2 && d2.value;
if (v1 === undefined) return v2 === undefined;
if (v1 instanceof _index2.Value && v2 instanceof _index2.Value) return _this4._containsValues(v1, v2);
if (Array.isArray(v1) && Array.isArray(v2)) {
return _this4._containsArray(v1, v2);
}
return v2 === undefined;
};
return this.containsMap(m1, m2, containsPropertyBinding);
}
}, {
key: "_containsArray",
value: function _containsArray(v1, v2) {
var e = v1 && v1[0] || v2 && v2[0];
if (e instanceof _index2.Value) return this._containsArraysOfValue(v1, v2);else return this._containsArrayOfsMapEntries(v1, v2);
}
}, {
key: "_containsArraysOfValue",
value: function _containsArraysOfValue(realm, a1, a2) {
var empty = realm.intrinsics.empty;
var n = Math.max(a1 && a1.length || 0, a2 && a2.length || 0);
for (var i = 0; i < n; i++) {
var _ref15 = a1 && a1[i] || { $Key: empty, $Value: empty },
key1 = _ref15.$Key,
val1 = _ref15.$Value;
var _ref16 = a2 && a2[i] || { $Key: empty, $Value: empty },
key2 = _ref16.$Key,
val2 = _ref16.$Value;
if (key1 === undefined) {
if (key2 !== undefined) return false;
} else {
if (key1 instanceof _index2.Value && key2 instanceof _index2.Value && key1.equals(key2)) {
if (val1 instanceof _index2.Value && val2 instanceof _index2.Value && this._containsValues(val1, val2)) continue;
}
return false;
}
}
return true;
}
}, {
key: "_containsArrayOfsMapEntries",
value: function _containsArrayOfsMapEntries(realm, a1, a2) {
var n = Math.max(a1 && a1.length || 0, a2 && a2.length || 0);
for (var i = 0; i < n; i++) {
var val1 = a1 && a1[i],
val2 = a2 && a2[i];
if (val1 instanceof _index2.Value && val2 instanceof _index2.Value && !this._containsValues(val1, val2)) return false;
}
return false;
}
}, {
key: "_containsValues",
value: function _containsValues(val1, val2) {
if (val1 instanceof _index2.AbstractValue) {
if (!_index2.Value.isTypeCompatibleWith(val2.getType(), val1.getType())) return false;
return val1.values.containsValue(val2);
}
return val1.equals(val2);
}
}]);
return WidenImplementation;
}();
//# sourceMappingURL=widen.js.map