On array mutability

[Chriscbr]

Summary:

• Separate types for mutable and immutable arrays help prevent some bugs.
• Unneeded copy() operations are sometimes required to change from MutArray to Array.
• One proposed solution is to use casting.
• A second proposed solution is to use dedicated builder types.

---

Wing distinguishes between immutable and mutable arrays. Here's an example of how this distinction helps catch bugs. I've made a class that stores an array of numbers, and we provide a public accessor that gives others a read-only view of the contents when they called the view() method. When class mutates its internal array, the read-only view is left unchanged.

class MyClass {
  _data: MutArray<num>;
  init() {
    this._data = MutArray<num>[1, 2, 3];
  }
  pub mutate() {
    this._data.push(4);
  }
  pub view(): Array<num> {
    return this._data;
  }
}

let a = new MyClass();

let data = a.view();
a.mutate();

assert(data.length == 1);

The implementation above has a bug: readonlyView() returns this._data which is type MutArray, not Array. Since the internal array is being returned, the mutation would change the view, causing the assertion to fail.

The Wing compiler throws an error today to tell you this. To fix the bug, you can return a copy of this._data instead:

class MyClass {
  // snip
  pub readonlyView(): Array<num> {
    return this._data.copy(); // fixed
  }
}

Our code now works. 👍

---

Unfortunately, sometimes the need to copy data is overly restrictive. Consider a class that calculates some data using a mutable array, and intends to return it immutably to the user:

class Helper {
  pub makeData(): Array<num> {
    let arr = MutArray<num>[];
    for i in 0..10 {
      arr.push(i);
    }
    return arr;
  }
}

Once arr is returned, it's not possible for it to be mutated, since it was defined as a local variable inside of the function. So, it should be safe to return arr and implicitly convert MutArray<num> to Array<num> in this scenario. Unfortunately, this is hard for a compiler to know for sure, because even a small change to the program makes it unsafe:

class Helper {
  _secret: MutArray<MutArray<num>>;
  init() {
    this._secret = MutArray<MutArray<num>>[];
  }
  pub makeData(): Array<num> {
    let arr = MutArray<num>[];
    for i in 0..10 {
      arr.push(i);
    }
    this._secret.push(arr);
    return arr;
  }
}

Here, I've pushed the mutable array arr inside another data structure (this._secret), so it's possible to continue mutating it after makeData has returned. So return arr; would not be safe in this context.

As a solution, the user could return arr.copy(), but then all of the data has to be copied, which could be an expensive operation if the array is large. How can we address this use case better?

---

Here are the current solutions we have for these situations:

Casting

Casting can be a useful tool for situations where you want to assert to the compiler that a value is a stronger type than the compiler can guarantee. In our example above, the solution might look like this:

class Helper {
  pub makeData(): Array<num> {
    let arr = MutArray<num>[];
    for i in 0..10 {
      arr.push(i);
    }
    return unsafeCast<Array<num>>(arr);
  }
}

The compiler would check that arr's type, MutArray<num>, is "compatible" with the target type, Array<num> (for example, we're not just casting an array into a string), and then the value is passed through, without any runtime cost.

Open question: are there situations where it makes sense to allow casting immutable arrays into mutable arrays?

Builder pattern

Essentially the idea with this solution is we would like a way to say "within some context, we are going to allow mutation to this array -- and afterwards, it's no longer allowed". We can accomplish this using a dedicated builder class:

class ArrayBuilder {
  _arr: MutArray<num>;
  var _done: bool;
  init() {
    this._arr = MutArray<num>[];
    this._done = false;
  }
  pub push(value: num) {
    assert(!this._done);
    this._arr.push(value);
  }
  pub pop(): num {
    assert(!this._done);
    return this._arr.pop();
  }
  pub build(): Array<num> {
    this._done = true;
    return unsafeCast(this._arr);
  }
}

class Helper {
  pub makeData(): Array<num> {
    let arr = new ArrayBuilder();
    for i in 0..10 {
      arr.push(i);
    }
    return arr.build();
  }
}

ArrayBuilder provides a safe way to create an immutable Array<T>. It allows mutation to its contents for a time (without exposing its internal array), and once build() is called, no further mutations are allowed.

Perhaps we could add ArrayBuilder<T>, SetBuilder<T>, and MapBuilder<T> as built-in types in the Wing standard library?

[eladb]

What about "copy on write"?

Basically copy() returns a reference to the original array and it will only be copied to a new array if one of the mutation methods is invoked on the original one.

[Chriscbr]

This is a pretty interesting idea.

Maybe it could be achieved using Proxy objects in JavaScript?


I think the main challenge would be trying to get this to behave consistently / with minimal surprises when Array and MutArray values are passed to JSII libraries or to extern functions, or even over the wire (once the Wing simulator supports calling inflight methods across different processes).

[eladb]

Yes, implementation would be fun!

It's a rather popular technique to achieve this type of optimization.