Storing objects inside Record & Tuple with Box?

[rickbutton]

Introduction

Record and Tuple are immutable data structures comprised of other primitives, forming "compound primitives". These data structures are deeply immutable; all nested values are also deeply immutable. This makes interactions with Record and Tuple easier to reason about, and is one of the main drivers of the proposal.

However, there are cases where the programmer might need to store additional "mutable" information with a Record or Tuple. While it is possible to deliver mutable data externally (for example, via returning two values from a function, a Record or Tuple, and a separate object containing mutable data), this is not as ergonomic as simply nesting the mutable data inside the object, especially if the mutable data is associated with a specific part of a Record or Tuple.

An alternative to keeping mutable data outside of a Record or Tuple is to associate said mutable data with a Record or Tuple via mapping, where the Record or Tuple contains a primitive (like a number, or a symbol) that when combined with a mapping, can represent an object, without needing to physically exist inside the Record. The Symbols as WeakMap Keys proposal attempts to provide a method of doing this using a shared WeakMap.

Box

A Box value is a value that "boxes" another value, and provides a method to "unbox" it. For example:

const thing = { number: 42 };
const box = Box(thing);
assert(thing === box.unbox());

Boxes can be stored inside a Record or Tuple, which means that you can use a Box to store objects inside Records:

const object = {
    method() {
        console.log("method!");
    },
};

const rec = #{
    object: Box(object),
};

rec.object.unbox().method();

This preserves the "integrity" of the Record, because you must explicitly "unbox" the object in order to use it, you can't accidentally switch to the "mutable world"; you must know that a Box exists and opt into unboxing it.

Previously, the champion group considered Box to be non-viable (after conversations with SES) because it was thought to violate "membrane guarantees". Specifically, membranes would need to traverse the Record in order to discover nested boxes, which was not initially acceptable. After further discussion with SES, it became clear that since this work is also required for objects (because you need to traverse the object for shadow-target construction) it seems reasonable to allow this work to happen for Records too. A check like Box.containsBox or similar can be used to eliminate unneeded work where the Record does not contain any boxes.

@nicolo-ribaudo opened this PR: #197 adding Box to this proposal. We'd like to continue investigating this avenue, and gather feedback it.

Open Questions:

Should this approach be taken?

Should you be required to "unbox" a Box inside a Record or Tuple, or should it be "automatic" in some way?

Previous discussions

There is an ongoing discussion in #31 about whether Records and Tuples should be allowed to contain objects, and if so, by what method.

[gibson042]

with SES, it became clear that since this work is also required for objects (because you need to traverse the object for shadow-target construction)

Can you explain this claim? I thought SES functioned by wrapping objects with Proxies that lazily repeat the process upon access, but this seems to require eager traversal.

[nicolo-ribaudo]

@gibson042 When you have a frozen object, you have to copy and wrap all its properties into a new frozen object. This is because, due to proxies' invariants, you cannot "simulate" a property on a frozen target (or shadow target).
If you have a frozen object recursively containing frozen objects, you'll have to deeply eagerly wrap them anyway.

[gibson042]

@nicolo-ribaudo Can you provide code demonstrating what you mean? It seems to me that lazy object graph traversal is always possible, but perhaps I'm misunderstanding the scenario.

// Demonstrate failure of writing within a transitively-frozen object.
var obj = freezeDeep({L1: {L2: {frozen: "frozen"}, L2x: {}}, L1x: {}});
obj.L1.L2.frozen = "not-frozen";
console.log("got", obj.L1.L2.frozen);
// got frozen

// Demonstrate lazy recursive wrapping that presents an unfrozen view of the same object.
obj = getUnfrozenView(obj);
obj.L1.L2.frozen = "not-frozen";
// get L1 of { L1: { L2: { frozen: 'frozen' }, L2x: {} }, L1x: {} }
// get L2 of { L2: { frozen: 'frozen' }, L2x: {}, lazy: 1 }
// set frozen not-frozen of { frozen: 'frozen', lazy: 2 }
console.log("got", obj.L1.L2.frozen);
// get L1 of { L1: { L2: { frozen: 'not-frozen', lazy: 2 }, L2x: {}, lazy: 1 }, L1x: {} }
// get L2 of { L2: { frozen: 'not-frozen', lazy: 2 }, L2x: {}, lazy: 1 }
// get frozen of { frozen: 'not-frozen', lazy: 2 }
// got not-frozen



let lazyIndex = 0;
function getUnfrozenView(val) {
  if ( isPrimitive(val) ) return val;
  var wrappedProperties = new WeakMap();
  return new Proxy(cloneUnfrozen(val), {
    get(unfrozenView, prop) {
      console.warn("get", prop, "of", unfrozenView);

      var val = unfrozenView[prop];
      if ( isPrimitive(val) ) return val;

      // avoid rewrapping an unchanged value
      if ( wrappedProperties.get(val) === prop ) return /*already wrapped*/ val;

      // overwrite with a recursive wrap
      var wrapped = unfrozenView[prop] = getUnfrozenView(cloneUnfrozen(val, {lazy: ++lazyIndex}));
      wrappedProperties.set(wrapped, prop);
      return wrapped;
    },
    set(unfrozenView, prop, val) {
      console.warn("set", prop, val, "of", unfrozenView);
      unfrozenView[prop] = val;
      return true;
    },
  });
}
function cloneUnfrozen(val, ...extensions) {
  if ( isPrimitive(val) ) return val;
  var clone = Object.defineProperties({},
    Object.fromEntries(Object.entries( Object.getOwnPropertyDescriptors(val) ).map(
      ([name, desc]) => [name, {...desc, configurable: true, writable: true}]
    ))
  );
  return Object.assign(clone, ...extensions);
}
function freezeDeep(val){
  if ( isPrimitive(val) ) return val;
  Object.entries(Object.getOwnPropertyDescriptors(val)).forEach(
    ([name]) => freezeDeep(val[name])
  );
  return Object.freeze(val);
}
function isPrimitive(val) {
  return val == null || typeof val !== "object" && typeof val !== "function";
}

[jridgewell]

@gibson042: The issue is that the membrane-wrapped value should be frozen if the original is frozen. And in order to do that properly, you have to traverse the object eagerly and compute the membrane-wrapped values of each property.

[littledan]

The reason for what @jridgewell indicates is the Proxy invariants, which requires that a preventExtensions Proxy have a target which is also preventExtensions. This property (together with similar invariants for non-configurable properties) has a ripple effect forcing frozen Proxies to be entirely represented in their target.

[gibson042]

It still seems that what you're describing can be lazy, evaluated at each level upon externally-observable access. Can someone provide code demonstrating why eager traversal is necessary? I can believe I'm just missing something, so please help me see it.

[jridgewell]

const obj = Object.freeze({
  __proto__: null,
  key: Object.freeze({
    __proto__: null,
  }),
});

const wrapped = wrap(obj);

// Wrapped obj must be a proxy wrapper around obj
assert.notStrictEqual(wrapped, obj);

// Wrapped obj must report as frozen if obj is frozen.
assert.equal(Object.isFrozen(wrapped), true);

// Wrapped obj's values must be wrapped objects themselves
assert.notStrictEqual(wrapped.key, obj.key);

These assertions must pass, else you've not performed a proper membrane wrapping. You can technically make it lazy until the object's frozenness is observed. But once you observe that, it must eagerly evaluate.

In order for a proxy to report that it is frozen, the target must itself be frozen. And once you freeze target, you can no longer add properties. And once the target is frozen, further Object.getOwnPropertyDescriptor on the proxy have additional requirements: properties that exist on target must return a frozen descriptors and properties that do not exist on target must return undefined descriptors. And because each value of obj must be wrapped themselves, you have to iterate all keys of obj and wrap them eagerly, store those as frozen descriptors on target, then freeze the target.

[Jack-Works]

Just a fact check.

#{ item: Box(alert) } === #{ item: Box(confirm) }

Should be true right? Boxes are treated as identical discarding what it contains otherwise the VDOM case is not working

[jridgewell]

Boxes are treated as identical discarding what it contains otherwise the VDOM case is not working

VDOM can actually do either approach. If contents are strictly compared, then we'd need to place a marker in each box (eg, a number) and store the actual data out-of-band. If the contents are ignored when compared, then we can just leave the data in the box.

[gibson042]

In order for a proxy to report that it is frozen, the target must itself be frozen. And once you freeze target, you can no longer add properties. And once the target is frozen, further Object.getOwnPropertyDescriptor on the proxy have additional requirements: properties that exist on target must return a frozen descriptors and properties that do not exist on target must return undefined descriptors. And because each value of obj must be wrapped themselves, you have to iterate all keys of obj and wrap them eagerly, store those as frozen descriptors on target, then freeze the target.

@jridgewell The above is true, but iteration at one level is not the same as eager traversal of the entire object graph—remember, we're having this discussion in the context of nested deeply-positioned boxes. It's entirely possible to lazily construct the proxies at each level without eager descent, as I think you were alluding to with "lazy until the object's frozenness is observed". And doesn't that disprove the "membranes must traverse objects anyway" claim that is being used as a (partial?) justification here?

https://plnkr.co/edit/QKB47fDFjOoCikJU?open=lib%2Fscript.js

function wrap(val) {
  if ( isPrimitive(val) ) return val;

  // Intentionally ignore functions in this proof of concept.
  let dupe = {};

  let wrappedProperties = new WeakMap();
  function wrapProp(prop, propVal) {
    if ( isPrimitive(propVal) ) return propVal;
    if ( !wrappedProperties.has(propVal) ) {
      console.warn(`wrapping [${prop}]`);
      wrappedProperties.set(propVal, wrap(propVal));
    }
    return wrappedProperties.get(propVal);
  }

  let isSealed = false;
  function syncIntegrityLevel() {
    if ( !isSealed && Object.isSealed(val) ) {
      for ( let key of Reflect.ownKeys(val) ) {
        let desc = Reflect.getOwnPropertyDescriptor(val, key);
        // Intentionally ignore accessors in this proof of concept.
        desc.value = wrapProp(key, desc.value);
        Reflect.defineProperty(dupe, key, desc);
      }
      Reflect.preventExtensions(dupe);
      isSealed = true;
    }
  }

  return new Proxy(dupe, {
    isExtensible() {
      syncIntegrityLevel();
      return !isSealed;
    },
    getOwnPropertyDescriptor(dupe, prop) {
      syncIntegrityLevel();

      let desc = Reflect.getOwnPropertyDescriptor(val, prop);
      if ( !desc ) return desc;
      // Intentionally ignore accessors in this proof of concept.
      desc.value = wrapProp(prop, desc.value);
      return desc;
    },
    get(dupe, prop) {
      syncIntegrityLevel();

      return wrapProp(prop, val[prop]);
    }
  });
}

function isPrimitive(val) {
  return val == null || typeof val !== "object" && typeof val !== "function";
}

[littledan]

Maybe @caridy @kriskowal or @erights could clarify the membrane constraints.

[caridy]

Ok It is not really about deep freeze per se!

If you're building a membrane around a record, and you want the proxy of the record to be considered a record as well (which means its "shadow target" MUST be a record), in order for you to create such shadow target (a record), you have to go eager deep traversal to replicate the original record because you can't mutate a record later on. I'm assuming here that you can recognize that something is a record (typeof or something else).

Since the membrane must provide alternative boxes (to wrap the value when accessed), that part can still be lazy, but the deep traversal of the records/tuples up to the boxes, is needed.

[erights]

Someone on some thread pointed out that, once the shadow target is constructed, often it will do as the representative on that side of the membrane without being wrapped in a proxy. Depends on the distortion, but most distortions won't have anything left to distort between the proxy and its shadow target when the shadow target is immutable. This observation also applies to frozen regular object shadow targets.

I don't know where I saw this observation. If you know its origin, please reply so it is properly attributed.

Attn @ajvincent

[caridy]

This observation also applies to frozen regular object shadow targets.

I don't think that's the case, frozen objects can be wrapped, with distortions, and shadow targets lazily, we do that all the time, and the shadow target is expanded until its state is revealed to the other side of the membrane. Here is a good example of that: https://github.com/caridy/sandboxed-javascript-environment/blob/master/src/blue.ts#L277-L280

The problem is really about that last part, how can you make the proxy look like a record/tuple? if this requires the shadow target to be a record (I suspect this is the only way based on previous conversations), then building such immutable shadow target is the problem, it will have to be built eagerly.

[erights]

I agree that a proxy can only be avoided by eagerly constructing the shadow target, so it is fully formed before releasing it. I also agree that for records and tuples, even if not wrapped by a proxy, there's no other choice --- they must be eagerly constructed in full the moment they are created.

Given that they must be eagerly constructed anyway, there will rarely be anything further gained by wrapping in a proxy, because the remaining distortions possible are rather narrow:

• side effects on other state, like logging accesses
• selectively preventing some access by throwing errors
  • purely pedantic point: or by going into an infinite loop

For frozen objects, there remains the choice of eager or lazy. Current membranes like @caridy's do lazy for good reasons. However, the tradeoffs are interesting and eager will sometimes be the better choice. The eager choice for frozen objects is no worse than the forced eager choice for records and tuples. For both, the opportunities to distort are equally limited, and thus so are the opportunities to avoid wrapping with a proxy.

[caridy]

Excellent. If records and tuples are objects without identity, it seems that a way to go with membranes can be something like this:

1. if O is a record or tuple
  1. return a new record or tuple where only Box references must be remapped, the rest remains the same
1. else, do what you normally do today

While the remapping of a box B is a very simple algo:

1. let v be the unboxed value of B.
1. If v is primitive,
   1. return B
1. else,
    1. return new Box(membrane proxy of v)

This will guarantee a couple of things:

1. A membrane can safety detect records and tuples to prevent leaking values through the membrane
2. The membrane can wrap boxed values with the proxy logic implemented by the membrane
3. If the record or tuple does NOT have a box (deep traversal included), the references from both sides of the membrane will pass the equality check (I'm not sure yet if this is a good thing or a bad thing, just noticing), and this is probably true even when they are records or tuples from different realms.
4. If the record or tuple does have a box (deep traversal included), the equality test will fail, (I'm not sure yet about this, but I believe this makes sense since they are holding different values at that point, it also maps well to the axiom of: "o !== proxy of o").

If these assumptions are correct, maybe we can ask for an API that can facilitate the creation of a remapped records and tuples, something like Record.map that when called with a record/tuple and a function, it will create a new record/tuple by calling the provided function for boxed values only rather than for all records and tuples during the deep traversal phase.

[erights]

In reading this I just realized that for the box invariant to be meaningful, it must apply to the [[Prototype]] reference as well. If the record or tuple inherits from something, that something must either be a record, tuple, primitive value, or a box.

[caridy]

In reading this I just realized that for the box invariant to be meaningful, it must apply to the [[Prototype]] reference as well.

Yes, we discussed that with @littledan extensibly. Just add null to that list as well.

[brad4d]

Just a fact check.

#{ item: Box(alert) } === #{ item: Box(confirm) }

Should be true right? Boxes are treated as identical discarding what it contains otherwise the VDOM case is not working

This isn't what I would expect. Shouldn't every Box you create be unique and !== to every other Box?

const alertBox = Box(alert);
const confirmBox = Box(confirm);
#{ item: alertBox } === #{ item: alertBox } // => true, because records have the same shape and the same content
#{ item: alertBox } === #{ item: confirmBox} // => false, because records have the same shape but not the same content
#{ item: alertBox } === #{ item: Box(alert)} // => false, box identity is not based on its contents

[Jack-Works]

If boxes aren't identical in the comparing, what difference between support mutable value in records and tuples directly?

[rricard]

Boxes are identical if given the same object:

const obj = {};
const obj2 = {};
Box(obj) === Box(obj)
Box(obj) !== Box(obj2)

[Jack-Works]

If so, I think there is no need to introduce the "Box", make tuple and records be able to store mutable objects are the same effect with this approach.

[rricard]

@Jack-Works it is not exactly the case, there are ergonomics tradeoffs discussed in #206. I separated it from this discussion because it is effectively not a semantics discussion but an ergonomic one.

[somethingelseentirely]

I think records and tuples with the ability to nest objects alleviate a lot of existing JS pain points.
There are so many shortcomings with existing standards like Map and Set, that could be solved
by this, like the ability for compound keys.

Even if one only cares about referential equality, having compound keys, e.g. #[string, fn] for event listeners,
would be a big improvement.

So I'm very much in favour of the box equality invariants:

const obj = {};
const obj2 = {};
Box(obj) === Box(obj)
Box(obj) !== Box(obj2)

However, I think this also forces our hand towards explicitness.
Otherwise we'd either have to auto-box Objects everywhere or tuples are no longer injective for ===:

#[Box(obj)] === #[obj]
Box(obj) === obj // ???

If the latter is false we've broken "===" over #[], if it's true, then boxed objects are indistinguishable from non boxed objects, at which point they're an implementation detail that begs the question why it should be exposed to the user.

[justinfagnani]

I want to reiterate the need for the equality @Jack-Works supposes for the vdom case:

#{ item: Box(alert) } === #{ item: Box(confirm) }

Without this we have to jump through hoops to only store markers in boxes and instead of allowing users to directly create and pass around records we need a factory function that adds the markers and returns a wrapper on the record + the marker set. At the point I don't think boxes buy anything over Symbols as WeakMap Keys, since the box content will never change in this case.

It does seem like there are two reasonable equality semantics though, so maybe this can be solved with one behavior for === and another accessible via a utility function.

[Jack-Works]

Though I guess it will be useful for VDom case, I double it might becomes a footgun (easily to forgot to compare the inner content)

[justinfagnani]

Then maybe a utility function is better for the equality-ignoring-boxes case.

[justinfagnani]

Another thing that concerns me regarding the vdom use-case (if that still is a use-case for records) is the need to traverse to get the boxes. Traversing the immutable parts of the tree is exactly the operation you want to avoid when performing updates.

Would it be possible to store the boxes in an array similar to template literals? It could be accessible via something like Box.getBoxes(record).

Then a vdom diff would simplify to something like:

update(newRecord, container) {
  if (Box.equalsIgnoreBoxes(oldRecord, newRecord)) {
    const oldBoxes = Box.getBoxes(oldRecord);
    const newBoxes = Box.getBoxes(newRecord);
    for (let i = 0; i < oldBoxes.length; i++) {
      if (oldBoxes[i] !== newBoxes[i]) {
        // uses a previously stored DOM reference associated with this box position
        updateDynamicPart(i, newBoxes[i], container);
      }
    }
  } else {
    replaceDOM(newRecord, container);
  }
}

[dead-claudia]

I posted a much more detailed series of concerns about virtual DOM vs boxes, which is relevant here as well: #206 (comment)

[nicolo-ribaudo]

We removed boxes from the proposal, since it was stalled because of them. I'm closing this issue, but we'll keep track of it if we'll bring them up again as a follow on proposal.