`PbList.addAll` traverses the iterable twice, causes side effects to run twice

[osa1]

Reported by an internal user.

protobuf.dart/protobuf/lib/src/protobuf/pb_list.dart

Lines 41 to 46 in 87135ba

	@override
	void addAll(Iterable<E> iterable) {
	_checkModifiable('addAll');
	iterable.forEach(_check);
	_wrappedList.addAll(iterable);
	}

The line iterable.forEach(_check) traverses the iterable once. If the iterable has side effects, those will be run for the first time here.

Then the next line _wrappedList.addAll(iterable) will again traverse the iterable, causing the side effects to run again.

I don't know if we should call this a bug, but I think it's fair to say that it's a bit unexpected.

Two possible fixes:

1. Copy iterable elements to a list, then traverse the list many times:

   void addAll(Iterable<E> iterable) {
     _checkModifiable('addAll');
     List<E> list = iterable is List ? iterable : iterable.toList();
     list.forEach(_check);
     _wrappedList.addAll(list);
   }

   The downside is the function will now require allocating an intermediate list, and the list may be large in some uses.

2. Check as we add elements to the wrapped list:

   void addAll(Iterable<E> iterable) {
     _checkModifiable('addAll');
     for (final e in iterable) {
       _check(e);
       _wrappedList.add(e);
     }
   }

   The downside is if a check fails the list will be updated. To avoid that, we could do:

   void addAll(Iterable<E> iterable) {
     _checkModifiable('addAll');
     var added = 0;
     for (final e in iterable) {
       try {
         _check(e);
       } catch (_) {
         _wrappedList.removeRange(_wrappedList.length - added, _wrappedList.length);
         rethrow;
       }
       _wrappedList.add(e);
       added += 1;
     }
   }

[osa1]

Other methods that do the same: insertAll, setAll, setRange, replaceRange.

[sigurdm]

I think option 2 sounds ok. Checks should not fail (ie. we throw an ArgumentError, not an Exception) So I think it is acceptable if the list is in a broken state afterwards.

[osa1]

Ugh.. I came across this issue again, and looking at my "fixes" for addAll above, they're almost embarrassingly bad.

I think this would be the best for setAll:

  void addAll(Iterable<E> iterable) {
    _checkModifiable('addAll');
    final lengthBefore = length;
    try {
      for (final element in iterable) {
        _check(element);
        _wrappedList.add(element);
      }
    } catch (e) {
      _wrappedList.length = lengthBefore;
      rethrow;
    }
  }

In my work in dart2wasm what I found is entering a try is almost free in the common case of no exceptions thrown. So this version can even be faster than the current (incorrect) version, because the current version iterates twice.

For insertAll, setAll, setRange, replaceRange, I don't think we can avoid allocating an intermediate list in the worst case, but I think we can add a fast path. Currently these are the _check functions we use:

protobuf.dart/protobuf/lib/src/protobuf/field_error.dart

Lines 75 to 107 in bb19774

	CheckFunc getCheckFunction(int fieldType) {
	switch (fieldType & ~0x7) {
	case PbFieldType._BOOL_BIT:
	case PbFieldType._BYTES_BIT:
	case PbFieldType._STRING_BIT:
	case PbFieldType._DOUBLE_BIT:
	case PbFieldType._ENUM_BIT:
	case PbFieldType._GROUP_BIT:
	case PbFieldType._MESSAGE_BIT:
	case PbFieldType._INT64_BIT:
	case PbFieldType._SINT64_BIT:
	case PbFieldType._SFIXED64_BIT:
	case PbFieldType._UINT64_BIT:
	case PbFieldType._FIXED64_BIT:
	// We always use the full range of the same Dart type.
	// It's up to the caller to treat the Int64 as signed or unsigned.
	// See: https://github.com/google/protobuf.dart/issues/44
	return _checkNotNull;
	case PbFieldType._FLOAT_BIT:
	return _checkFloat;
	case PbFieldType._INT32_BIT:
	case PbFieldType._SINT32_BIT:
	case PbFieldType._SFIXED32_BIT:
	return _checkSigned32;
	case PbFieldType._UINT32_BIT:
	case PbFieldType._FIXED32_BIT:
	return _checkUnsigned32;
	}
	throw ArgumentError('check function not implemented: $fieldType');
	}

The _checkNotNull function isn't doing anything in sound-null-safe Dart, so that can be represented as null. insertAll, setAll etc. can then have a fast path when _check is null.

[sigurdm]

I still think we don't have to cater to the case where an Error is thrown. That should never happen, and point to an error in user code. I don't think we have to promise any behavior in that case.

[rakudrama]

1. Copy iterable elements to a list, then traverse the list many times

void addAll(Iterable<E> iterable) {
 _checkModifiable('addAll');
 List<E> list = iterable is List ? iterable : iterable.toList();
 list.forEach(_check);
 _wrappedList.addAll(list);
}

The downside is the function will now require allocating an intermediate list, and the list may be large in some uses.

At least the list is ephemeral, though that does still add to GC pressure.
forEach and addAll are fast when used like this - the big cost for forEach on small lists is usually creating the closure, but we have it at hand. For the system list(s), addAll has an accelerated path.

I might be tempted to always copy to a list to ensure the copy is a system list and not something expensive like CastList, and to copy with List.of to avoid weird toList implementations. I wish we had a constructor List<E>.ensureSystem(list) that returns list if it is the system list, otherwise returns List<E>.of(list).

In my work in dart2wasm what I found is entering a try is almost free in the common case of no exceptions thrown.

This is not as true for dart2js since try-catch inhibits some dart2js optimizations (via SSA conversion being incomplete when there are exception handling regions.)

The _checkNotNull function isn't doing anything in sound-null-safe Dart, so that can be represented as null. insertAll, setAll etc. can then have a fast path when _check is null.

I like this idea. Why iterate to do nothing?

I still think we don't have to cater to the case where an Error is thrown. That should never happen, and point to an error in user code. I don't think we have to promise any behavior in that case.

I don't think we promise atomicity, but we don't mention errors either, and that might be surprising given the constraints can't be expressed in the type system.