| // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| // part of "core_patch.dart"; |
| |
| @pragma("vm:entry-point") |
| class _GrowableList<T> extends ListBase<T> { |
| void insert(int index, T element) { |
| if ((index < 0) || (index > length)) { |
| throw new RangeError.range(index, 0, length); |
| } |
| int oldLength = this.length; |
| add(element); |
| if (index == oldLength) { |
| return; |
| } |
| Lists.copy(this, index, this, index + 1, oldLength - index); |
| this[index] = element; |
| } |
| |
| T removeAt(int index) { |
| var result = this[index]; |
| int newLength = this.length - 1; |
| if (index < newLength) { |
| Lists.copy(this, index + 1, this, index, newLength - index); |
| } |
| this.length = newLength; |
| return result; |
| } |
| |
| bool remove(Object? element) { |
| for (int i = 0; i < this.length; i++) { |
| if (this[i] == element) { |
| removeAt(i); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| void insertAll(int index, Iterable<T> iterable) { |
| if (index < 0 || index > length) { |
| throw new RangeError.range(index, 0, length); |
| } |
| // TODO(floitsch): we can probably detect more cases. |
| if (iterable is! List && iterable is! Set && iterable is! SubListIterable) { |
| iterable = iterable.toList(); |
| } |
| int insertionLength = iterable.length; |
| // There might be errors after the length change, in which case the list |
| // will end up being modified but the operation not complete. Unless we |
| // always go through a "toList" we can't really avoid that. |
| int capacity = _capacity; |
| int newLength = length + insertionLength; |
| if (newLength > capacity) { |
| do { |
| capacity = _nextCapacity(capacity); |
| } while (newLength > capacity); |
| _grow(capacity); |
| } |
| _setLength(newLength); |
| setRange(index + insertionLength, this.length, this, index); |
| setAll(index, iterable); |
| } |
| |
| void setAll(int index, Iterable<T> iterable) { |
| if (iterable is List) { |
| setRange(index, index + iterable.length, iterable); |
| } else { |
| for (T element in iterable) { |
| this[index++] = element; |
| } |
| } |
| } |
| |
| void removeRange(int start, int end) { |
| RangeError.checkValidRange(start, end, this.length); |
| Lists.copy(this, end, this, start, this.length - end); |
| this.length = this.length - (end - start); |
| } |
| |
| List<T> sublist(int start, [int? end]) { |
| final int actualEnd = RangeError.checkValidRange(start, end, this.length); |
| int length = actualEnd - start; |
| if (length == 0) return <T>[]; |
| final list = new _List(length); |
| for (int i = 0; i < length; i++) { |
| list[i] = this[start + i]; |
| } |
| final result = new _GrowableList<T>._withData(list); |
| result._setLength(length); |
| return result; |
| } |
| |
| factory _GrowableList(int length) { |
| var data = _allocateData(length); |
| var result = new _GrowableList<T>._withData(data); |
| if (length > 0) { |
| result._setLength(length); |
| } |
| return result; |
| } |
| |
| factory _GrowableList.withCapacity(int capacity) { |
| var data = _allocateData(capacity); |
| return new _GrowableList<T>._withData(data); |
| } |
| |
| // Specialization of List.empty constructor for growable == true. |
| // Used by pkg/vm/lib/transformations/list_factory_specializer.dart. |
| @pragma("vm:prefer-inline") |
| factory _GrowableList.empty() { |
| // Specialization of `return _GrowableList(0);`. |
| return _GrowableList<T>._withData(_emptyList); |
| } |
| |
| // Specialization of List.filled constructor for growable == true. |
| // Used by pkg/vm/lib/transformations/list_factory_specializer.dart. |
| factory _GrowableList.filled(int length, T fill) { |
| final result = _GrowableList<T>(length); |
| if (fill != null) { |
| for (int i = 0; i < result.length; i++) { |
| result[i] = fill; |
| } |
| } |
| return result; |
| } |
| |
| // Specialization of List.generate constructor for growable == true. |
| // Used by pkg/vm/lib/transformations/list_factory_specializer.dart. |
| @pragma("vm:prefer-inline") |
| factory _GrowableList.generate(int length, T generator(int index)) { |
| final result = _GrowableList<T>(length); |
| for (int i = 0; i < result.length; ++i) { |
| result[i] = generator(i); |
| } |
| return result; |
| } |
| |
| // Specialization of List.of constructor for growable == true. |
| factory _GrowableList.of(Iterable<T> elements) { |
| if (elements is _GrowableList) { |
| return _GrowableList._ofGrowableList(unsafeCast(elements)); |
| } |
| if (elements is _Array) { |
| return _GrowableList._ofArray(unsafeCast(elements)); |
| } |
| if (elements is EfficientLengthIterable) { |
| return _GrowableList._ofEfficientLengthIterable(unsafeCast(elements)); |
| } |
| return _GrowableList._ofOther(elements); |
| } |
| |
| factory _GrowableList._ofArray(_Array<T> elements) { |
| final int length = elements.length; |
| if (length > 0) { |
| final data = _List(_adjustedCapacity(length)); |
| for (int i = 0; i < length; i++) { |
| data[i] = elements[i]; |
| } |
| final list = _GrowableList<T>._withData(data); |
| list._setLength(length); |
| return list; |
| } |
| return _GrowableList<T>.empty(); |
| } |
| |
| factory _GrowableList._ofGrowableList(_GrowableList<T> elements) { |
| final int length = elements.length; |
| if (length > 0) { |
| final data = _List(_adjustedCapacity(length)); |
| for (int i = 0; i < length; i++) { |
| data[i] = elements[i]; |
| } |
| final list = _GrowableList<T>._withData(data); |
| list._setLength(length); |
| return list; |
| } |
| return _GrowableList<T>.empty(); |
| } |
| |
| factory _GrowableList._ofEfficientLengthIterable( |
| EfficientLengthIterable<T> elements) { |
| final int length = elements.length; |
| if (length > 0) { |
| final data = _List(_adjustedCapacity(length)); |
| int i = 0; |
| for (var element in elements) { |
| data[i++] = element; |
| } |
| if (i != length) throw ConcurrentModificationError(elements); |
| final list = _GrowableList<T>._withData(data); |
| list._setLength(length); |
| return list; |
| } |
| return _GrowableList<T>.empty(); |
| } |
| |
| factory _GrowableList._ofOther(Iterable<T> elements) { |
| final list = _GrowableList<T>(0); |
| for (var elements in elements) { |
| list.add(elements); |
| } |
| return list; |
| } |
| |
| @pragma("vm:recognized", "other") |
| @pragma("vm:exact-result-type", |
| <dynamic>[_GrowableList, "result-type-uses-passed-type-arguments"]) |
| @pragma("vm:external-name", "GrowableList_allocate") |
| external factory _GrowableList._withData(_List data); |
| |
| @pragma("vm:recognized", "graph-intrinsic") |
| @pragma("vm:exact-result-type", "dart:core#_Smi") |
| @pragma("vm:prefer-inline") |
| @pragma("vm:external-name", "GrowableList_getCapacity") |
| external int get _capacity; |
| |
| @pragma("vm:recognized", "graph-intrinsic") |
| @pragma("vm:exact-result-type", "dart:core#_Smi") |
| @pragma("vm:prefer-inline") |
| @pragma("vm:external-name", "GrowableList_getLength") |
| external int get length; |
| |
| void set length(int new_length) { |
| if (new_length > length) { |
| // Verify that element type is nullable. |
| null as T; |
| if (new_length > _capacity) { |
| _grow(new_length); |
| } |
| _setLength(new_length); |
| return; |
| } |
| final int new_capacity = new_length; |
| // We are shrinking. Pick the method which has fewer writes. |
| // In the shrink-to-fit path, we write |new_capacity + new_length| words |
| // (null init + copy). |
| // In the non-shrink-to-fit path, we write |length - new_length| words |
| // (null overwrite). |
| final bool shouldShrinkToFit = |
| (new_capacity + new_length) < (length - new_length); |
| if (shouldShrinkToFit) { |
| _shrink(new_capacity, new_length); |
| } else { |
| for (int i = new_length; i < length; i++) { |
| _setIndexed(i, null); |
| } |
| } |
| _setLength(new_length); |
| } |
| |
| @pragma("vm:recognized", "graph-intrinsic") |
| @pragma("vm:external-name", "GrowableList_setLength") |
| external void _setLength(int new_length); |
| |
| @pragma("vm:recognized", "graph-intrinsic") |
| @pragma("vm:external-name", "GrowableList_setData") |
| external void _setData(_List array); |
| |
| @pragma("vm:recognized", "graph-intrinsic") |
| @pragma("vm:external-name", "GrowableList_getIndexed") |
| external T operator [](int index); |
| |
| @pragma("vm:recognized", "other") |
| void operator []=(int index, T value) { |
| _setIndexed(index, value); |
| } |
| |
| @pragma("vm:recognized", "graph-intrinsic") |
| @pragma("vm:external-name", "GrowableList_setIndexed") |
| external void _setIndexed(int index, T? value); |
| |
| @pragma("vm:entry-point", "call") |
| @pragma("vm:prefer-inline") |
| void add(T value) { |
| var len = length; |
| if (len == _capacity) { |
| _growToNextCapacity(); |
| } |
| _setLength(len + 1); |
| this[len] = value; |
| } |
| |
| void addAll(Iterable<T> iterable) { |
| var len = length; |
| final cid = ClassID.getID(iterable); |
| final isVMList = (cid == ClassID.cidArray) || |
| (cid == ClassID.cidGrowableObjectArray) || |
| (cid == ClassID.cidImmutableArray); |
| if (isVMList || (iterable is EfficientLengthIterable)) { |
| var cap = _capacity; |
| // Pregrow if we know iterable.length. |
| var iterLen = iterable.length; |
| if (iterLen == 0) { |
| return; |
| } |
| var newLen = len + iterLen; |
| if (newLen > cap) { |
| do { |
| cap = _nextCapacity(cap); |
| } while (newLen > cap); |
| _grow(cap); |
| } |
| if (isVMList) { |
| if (identical(iterable, this)) { |
| throw new ConcurrentModificationError(this); |
| } |
| this._setLength(newLen); |
| final ListBase<T> iterableAsList = iterable as ListBase<T>; |
| for (int i = 0; i < iterLen; i++) { |
| this[len++] = iterableAsList[i]; |
| } |
| return; |
| } |
| } |
| Iterator it = iterable.iterator; |
| if (!it.moveNext()) return; |
| do { |
| while (len < _capacity) { |
| int newLen = len + 1; |
| this._setLength(newLen); |
| this[len] = it.current; |
| if (!it.moveNext()) return; |
| if (this.length != newLen) throw new ConcurrentModificationError(this); |
| len = newLen; |
| } |
| _growToNextCapacity(); |
| } while (true); |
| } |
| |
| @pragma("vm:prefer-inline") |
| T removeLast() { |
| var len = length - 1; |
| var elem = this[len]; |
| this.length = len; |
| return elem; |
| } |
| |
| T get first { |
| if (length > 0) return this[0]; |
| throw IterableElementError.noElement(); |
| } |
| |
| T get last { |
| if (length > 0) return this[length - 1]; |
| throw IterableElementError.noElement(); |
| } |
| |
| T get single { |
| if (length == 1) return this[0]; |
| if (length == 0) throw IterableElementError.noElement(); |
| throw IterableElementError.tooMany(); |
| } |
| |
| // Shared array used as backing for new empty growable arrays. |
| static final _List _emptyList = new _List(0); |
| |
| static _List _allocateData(int capacity) { |
| if (capacity == 0) { |
| // Use shared empty list as backing. |
| return _emptyList; |
| } |
| return _List(_adjustedCapacity(capacity)); |
| } |
| |
| // Round up size to the next odd number, since this is free |
| // because of alignment requirements of the GC. |
| static int _adjustedCapacity(int capacity) => capacity | 1; |
| |
| // Grow from 0 to 3, and then double + 1. |
| int _nextCapacity(int old_capacity) => (old_capacity * 2) | 3; |
| |
| void _grow(int new_capacity) { |
| var newData = _allocateData(new_capacity); |
| // This is a work-around for dartbug.com/30090: array-bound-check |
| // generalization causes excessive deoptimizations because it |
| // hoists CheckArrayBound(i, ...) out of the loop below and turns it |
| // into CheckArrayBound(length - 1, ...). Which deoptimizes |
| // if length == 0. However the loop itself does not execute |
| // if length == 0. |
| if (length > 0) { |
| for (int i = 0; i < length; i++) { |
| newData[i] = this[i]; |
| } |
| } |
| _setData(newData); |
| } |
| |
| // This method is marked as never-inline to conserve code size. |
| // It is called in rare cases, but used in the add() which is |
| // used very often and always inlined. |
| @pragma("vm:never-inline") |
| void _growToNextCapacity() { |
| _grow(_nextCapacity(_capacity)); |
| } |
| |
| void _shrink(int new_capacity, int new_length) { |
| var newData = _allocateData(new_capacity); |
| // This is a work-around for dartbug.com/30090. See the comment in _grow. |
| if (new_length > 0) { |
| for (int i = 0; i < new_length; i++) { |
| newData[i] = this[i]; |
| } |
| } |
| _setData(newData); |
| } |
| |
| // Iterable interface. |
| |
| @pragma("vm:prefer-inline") |
| void forEach(f(T element)) { |
| int initialLength = length; |
| for (int i = 0; i < length; i++) { |
| f(this[i]); |
| if (length != initialLength) throw new ConcurrentModificationError(this); |
| } |
| } |
| |
| String join([String separator = ""]) { |
| final int length = this.length; |
| if (length == 0) return ""; |
| if (length == 1) return "${this[0]}"; |
| if (separator.isNotEmpty) return _joinWithSeparator(separator); |
| var i = 0; |
| var codeUnitCount = 0; |
| while (i < length) { |
| final element = this[i]; |
| // While list contains one-byte strings. |
| if (element is _OneByteString) { |
| codeUnitCount += element.length; |
| i++; |
| // Loop back while strings are one-byte strings. |
| continue; |
| } |
| // Otherwise, never loop back to the outer loop, and |
| // handle the remaining strings below. |
| |
| // Loop while elements are strings, |
| final int firstNonOneByteStringLimit = i; |
| var nextElement = element; |
| while (nextElement is String) { |
| i++; |
| if (i == length) { |
| return _StringBase._concatRangeNative(this, 0, length); |
| } |
| nextElement = this[i]; |
| } |
| |
| // Not all elements are strings, so allocate a new backing array. |
| final list = new _List(length); |
| for (int copyIndex = 0; copyIndex < i; copyIndex++) { |
| list[copyIndex] = this[copyIndex]; |
| } |
| // Is non-zero if list contains a non-onebyte string. |
| var onebyteCanary = i - firstNonOneByteStringLimit; |
| while (true) { |
| final String elementString = "$nextElement"; |
| onebyteCanary |= |
| (ClassID.getID(elementString) ^ ClassID.cidOneByteString); |
| list[i] = elementString; |
| codeUnitCount += elementString.length; |
| i++; |
| if (i == length) break; |
| nextElement = this[i]; |
| } |
| if (onebyteCanary == 0) { |
| // All elements returned a one-byte string from toString. |
| return _OneByteString._concatAll(list, codeUnitCount); |
| } |
| return _StringBase._concatRangeNative(list, 0, length); |
| } |
| // All elements were one-byte strings. |
| return _OneByteString._concatAll(this, codeUnitCount); |
| } |
| |
| String _joinWithSeparator(String separator) { |
| StringBuffer buffer = new StringBuffer(); |
| buffer.write(this[0]); |
| for (int i = 1; i < this.length; i++) { |
| buffer.write(separator); |
| buffer.write(this[i]); |
| } |
| return buffer.toString(); |
| } |
| |
| T elementAt(int index) { |
| return this[index]; |
| } |
| |
| bool get isEmpty { |
| return this.length == 0; |
| } |
| |
| bool get isNotEmpty => !isEmpty; |
| |
| void clear() { |
| this.length = 0; |
| } |
| |
| String toString() => ListBase.listToString(this); |
| |
| @pragma("vm:prefer-inline") |
| Iterator<T> get iterator { |
| return new ListIterator<T>(this); |
| } |
| |
| List<T> toList({bool growable: true}) { |
| // TODO(sra): We should be able to replace the following with: |
| // |
| // return growable |
| // ? _GrowableList<T>._ofGrowableList(this) |
| // : _List<T>._ofGrowableList(this); |
| // |
| // However, the extra call causes a 5% regression in `ListCopy.toList.2`. |
| |
| final length = this.length; |
| if (growable) { |
| if (length > 0) { |
| final data = new _List(_adjustedCapacity(length)); |
| for (int i = 0; i < length; i++) { |
| data[i] = this[i]; |
| } |
| final result = new _GrowableList<T>._withData(data); |
| result._setLength(length); |
| return result; |
| } |
| return <T>[]; |
| } else { |
| if (length > 0) { |
| final list = new _List<T>(length); |
| for (int i = 0; i < length; i++) { |
| list[i] = this[i]; |
| } |
| return list; |
| } |
| return List<T>.empty(growable: false); |
| } |
| } |
| |
| Set<T> toSet() { |
| return new Set<T>.of(this); |
| } |
| |
| // Factory constructing a mutable List from a parser generated List literal. |
| // [elements] contains elements that are already type checked. |
| @pragma("vm:entry-point", "call") |
| factory _GrowableList._literal(_List elements) { |
| final result = new _GrowableList<T>._withData(elements); |
| result._setLength(elements.length); |
| return result; |
| } |
| |
| // Specialized list literal constructors. |
| // Used by pkg/vm/lib/transformations/list_literals_lowering.dart. |
| factory _GrowableList._literal1(T e0) { |
| _List elements = _List(1); |
| elements[0] = e0; |
| final result = new _GrowableList<T>._withData(elements); |
| result._setLength(1); |
| return result; |
| } |
| |
| factory _GrowableList._literal2(T e0, T e1) { |
| _List elements = _List(2); |
| elements[0] = e0; |
| elements[1] = e1; |
| final result = new _GrowableList<T>._withData(elements); |
| result._setLength(2); |
| return result; |
| } |
| |
| factory _GrowableList._literal3(T e0, T e1, T e2) { |
| _List elements = _List(3); |
| elements[0] = e0; |
| elements[1] = e1; |
| elements[2] = e2; |
| final result = new _GrowableList<T>._withData(elements); |
| result._setLength(3); |
| return result; |
| } |
| |
| factory _GrowableList._literal4(T e0, T e1, T e2, T e3) { |
| _List elements = _List(4); |
| elements[0] = e0; |
| elements[1] = e1; |
| elements[2] = e2; |
| elements[3] = e3; |
| final result = new _GrowableList<T>._withData(elements); |
| result._setLength(4); |
| return result; |
| } |
| |
| factory _GrowableList._literal5(T e0, T e1, T e2, T e3, T e4) { |
| _List elements = _List(5); |
| elements[0] = e0; |
| elements[1] = e1; |
| elements[2] = e2; |
| elements[3] = e3; |
| elements[4] = e4; |
| final result = new _GrowableList<T>._withData(elements); |
| result._setLength(5); |
| return result; |
| } |
| |
| factory _GrowableList._literal6(T e0, T e1, T e2, T e3, T e4, T e5) { |
| _List elements = _List(6); |
| elements[0] = e0; |
| elements[1] = e1; |
| elements[2] = e2; |
| elements[3] = e3; |
| elements[4] = e4; |
| elements[5] = e5; |
| final result = new _GrowableList<T>._withData(elements); |
| result._setLength(6); |
| return result; |
| } |
| |
| factory _GrowableList._literal7(T e0, T e1, T e2, T e3, T e4, T e5, T e6) { |
| _List elements = _List(7); |
| elements[0] = e0; |
| elements[1] = e1; |
| elements[2] = e2; |
| elements[3] = e3; |
| elements[4] = e4; |
| elements[5] = e5; |
| elements[6] = e6; |
| final result = new _GrowableList<T>._withData(elements); |
| result._setLength(7); |
| return result; |
| } |
| |
| factory _GrowableList._literal8( |
| T e0, T e1, T e2, T e3, T e4, T e5, T e6, T e7) { |
| _List elements = _List(8); |
| elements[0] = e0; |
| elements[1] = e1; |
| elements[2] = e2; |
| elements[3] = e3; |
| elements[4] = e4; |
| elements[5] = e5; |
| elements[6] = e6; |
| elements[7] = e7; |
| final result = new _GrowableList<T>._withData(elements); |
| result._setLength(8); |
| return result; |
| } |
| } |