Inconsistent results of `List.join` under concurrent modification

[rakudrama]

When the toString() method of an element of list modifies the list, results of list.join() are inconsistent.
Admittedly, this is an unlikely scenario.

• Sometimes a RangeError is thrown.
• Sometimes an added element is included sometimes not (VM.NAC vs VM.NAZ),
• Sometimes there is nothing after a separator (dart2js.NPC)

I think it would be preferable if all of these caused a ConcurrentModificationError to be thrown.
This is what happens for a list length change when the implementation of join is inherited from ListBase or Iterable.
The optimized versions should be optimizing this behaviour instead of changing it.

VM results:

NAC:       "1, 2, Add(5), 3, 666"
SAC:       "1, 2, Add(5), 3, 666"
NAZ:       "12Add(5)3"
SAZ:       "12Add(5)3"
NPC:       "1, 2, Pop(3)"
SPC:       "1, 2, Pop(3)"
NPZ:       RangeError (length): Invalid value: Not in inclusive range 0..2: 3
SPZ:       RangeError (length): Invalid value: Not in inclusive range 0..2: 3
NALC:      "1, 2, Add(4), 666"
SALC:      "1, 2, Add(4), 666"
NALZ:      "12Add(4)"
SALZ:      "12Add(4)"
NPLC:      "1, 2, Pop(2)"
SPLC:      "1, 2, Pop(2)"
NPLZ:      "12Pop(2)"
SPLZ:      "12Pop(2)"
NAWC:      Concurrent modification during iteration: Instance(length:5) of '_GrowableList'.
SPWC:      Concurrent modification during iteration: Instance(length:3) of '_GrowableList'.
NALWZ:     Concurrent modification during iteration: Instance(length:4) of '_GrowableList'.
SPLWZ:     Concurrent modification during iteration: Instance(length:2) of '_GrowableList'.
NPDC:      Concurrent modification during iteration: Instance of 'DelegatedList<Object>'.
SALDC:     Concurrent modification during iteration: Instance of 'DelegatedList<Object>'.
NPLDZ:     Concurrent modification during iteration: Instance of 'DelegatedList<Object>'.

dart2js results:

NAC:       RangeError (index): Index out of range: index should be less than 4: 4
SAC:       RangeError (index): Index out of range: index should be less than 4: 4
NAZ:       RangeError (index): Index out of range: index should be less than 4: 4
SAZ:       RangeError (index): Index out of range: index should be less than 4: 4
NPC:       "1, 2, Pop(3), "
SPC:       "1, 2, Pop(3), "
NPZ:       "12Pop(3)"
SPZ:       "12Pop(3)"
NALC:      RangeError (index): Index out of range: index should be less than 3: 3
SALC:      RangeError (index): Index out of range: index should be less than 3: 3
NALZ:      RangeError (index): Index out of range: index should be less than 3: 3
SALZ:      RangeError (index): Index out of range: index should be less than 3: 3
NPLC:      "1, 2, Pop(2)"
SPLC:      "1, 2, Pop(2)"
NPLZ:      "12Pop(2)"
SPLZ:      "12Pop(2)"
NAWC:      Concurrent modification during iteration: Instance of 'JSArray<Object>'.
SPWC:      Concurrent modification during iteration: Instance of 'JSArray<Object>'.
NALWZ:     Concurrent modification during iteration: Instance of 'JSArray<Object>'.
SPLWZ:     Concurrent modification during iteration: Instance of 'JSArray<Object>'.
NPDC:      Concurrent modification during iteration: Instance of 'DelegatedList<Object>'.
SALDC:     Concurrent modification during iteration: Instance of 'DelegatedList<Object>'.
NPLDZ:     Concurrent modification during iteration: Instance of 'DelegatedList<Object>'.

import 'dart:collection';

class Add {
  final List<Object> list;
  Add(this.list);

  String toString() {
    list.add(666);
    return 'Add(${list.length})';
  }
}

class Pop {
  final List<Object> list;
  Pop(this.list);

  String toString() {
    list.removeLast();
    return 'Pop(${list.length})';
  }
}

void runProtected(String name, String test()) {
  final tag = '$name:'.padRight(10, ' ');
  try {
    print('$tag "${test()}"');
  } catch (e) {
    print('$tag $e');
  }
}

class DelegatedList<E> extends ListBase<E> {
  final List<E> _delegate;
  DelegatedList(this._delegate);

  int get length => _delegate.length;
  void set length(int length) => _delegate.length = length;
  E operator [](int i) => _delegate[i];
  void operator []=(int i, E v) => _delegate[i] = v;
}

bool isTrue(_) => true;

void run({
  required bool number, // Number or String.
  required bool add, // Add or Pop
  required bool last, // Add/Pop at last position?
  bool delegate = false, // Wrap list in a DelegatedList to test ListBase.
  bool where = false, // Add `.where(isTrue)`.
  required bool comma, // Use `.join(', ')` or `.join()`.
}) {
  final List<Object> list = [];
  list.add(number ? 1 : '1');
  list.add(number ? 2 : '2');
  list.add(add ? Add(list) : Pop(list));
  if (!last) list.add(number ? 3 : '3');

  Iterable<Object> iterable = delegate ? DelegatedList(list) : list;
  if (where) iterable = iterable.where(isTrue);

  final test = () => comma ? iterable.join(', ') : iterable.join();

  // {Number,String}{Add,Pop}{,Last}{,Delegate}{,Where}{Comma,Zero}
  final name =
      (number ? 'N' : 'S') +
      (add ? 'A' : 'P') +
      (last ? 'L' : '') +
      (delegate ? 'D' : '') +
      (where ? 'W' : '') +
      (comma ? 'C' : 'Z');

  runProtected(name, test);
}

main() {
  for (final last in [false, true]) {
    for (final add in [true, false]) {
      for (final comma in [true, false]) {
        for (final number in [true, false]) {
          run(number: number, add: add, comma: comma, last: last);
        }
      }
    }
  }

  // These all have Concurrent modification errors. Take a sample.
  int i = 0;
  for (final where in [true, false]) {
    final delegate = !where;
    for (final last in [false, true]) {
      for (final add in [true, false]) {
        for (final comma in [true, false]) {
          for (final number in [true, false]) {
            if (i++ % 5 != 0) continue;
            run(
              number: number,
              add: add,
              comma: comma,
              last: last,
              where: where,
              delegate: delegate,
            );
          }
        }
      }
    }
  }
}

[lrhn]

We have deliberately removed concurrent modification checks in the inner loops for performance reasons. I don't know if we have retained them as asserts or not. Each platform chooses it's own optimizations.

There are no guarantees what happens on concurrent modification. It's an error to modify a container while it's being iterated.

Best case it's detected and a ConcurrentModificationError is thrown.
Detection is "best effort".

Next best case it loops until you get an out of memory error.

Worst case, it silently gives you an inconsistent result.

If your toString method has visible side effects, ... you deserve whatever pain that causes. Just don't.

[rakudrama]

Can the optimizer replace one 'best effort' with another 'best effort' with different behaviour for error cases?

Specifically, I was wondering if dart2js could (in certain circumstances) replace calling the defined SystemList.join with JavaScript's version. If the defined version detected CME, then one might say it is acceptable for the compiler to change the behaviour under -O4, since the the 'optimized' code produces the same result as the original when the original has no errors.

Now if the original does not detect CME, then the transformation is breaking the contract of -O4, which is to maintain the same behaviour for programs that do not encounter errors.

We have deliberately removed concurrent modification checks in the inner loops for performance reasons.

Not here. The VM implementation never had these checks. The last change, 11 years ago, is mostly concerned with detecting that the elements are already strings, potentially being able to construct the result without intermediate allocations. No CME checks would be needed on that path since the elements are already strings.

[lrhn]

Dart2js is free to change the behavior within the documented requirements, and since concurrent modification is unspecified behavior, I won't complain of that changes behavior. "A program without errors" isn't necessarily the same as "a program which doesn't throw an error". Not all errors are necessarily detected, they're still errors if they are documented as such.

I have no opinion on what -O4 guarantees or should guarantee. Whatever the user can accept when they opt in to it.

(See also: #30477)