private const int INITIAL_SIZE = 20;

internal int _size;

internal volatile object?[] _data;

#region Python Constructors and Initializers

public void __init__() {

_data = new object[8];

_size = 0;

}

public void __init__([NotNone] IEnumerable enumerable) {

__init__();

foreach (object? o in enumerable) {

AddNoLock(o);

}

}

public void __init__([NotNone] ICollection sequence) {

_data = new object[sequence.Count];

int i = 0;

foreach (object? item in sequence) {

_data[i++] = item;

}

_size = i;

}

public void __init__([NotNone] SetCollection sequence) {

PythonList list = sequence._items.GetItems();

_size = list._size;

_data = list._data;

}

public void __init__([NotNone] FrozenSetCollection sequence) {

PythonList list = sequence._items.GetItems();

_size = list._size;

_data = list._data;

}

public void __init__([NotNone] PythonList sequence) {

if (this == sequence) {

// list.__init__(l, l) resets l

_size = 0;

return;

}

// Only initialize from using _data if we have an exact list

if (sequence.GetType() != typeof(PythonList)) {

__init__((IEnumerable)sequence);

return;

}

_data = new object[sequence._size];

Array.Copy(sequence._data, 0, _data, 0, _data.Length);

_size = _data.Length;

}

public void __init__([NotNone] string sequence) {

_data = new object[sequence.Length];

_size = sequence.Length;

for (int i = 0; i < sequence.Length; i++) {

_data[i] = ScriptingRuntimeHelpers.CharToString(sequence[i]);

}

}

public void __init__(CodeContext context, object? sequence) {

int len;

try {

if (!PythonOps.TryInvokeLengthHint(context, sequence, out len)) {

len = INITIAL_SIZE;

}

} catch (MissingMemberException) {

len = INITIAL_SIZE;

}

_data = new object[len];

_size = 0;

ExtendNoLengthCheck(context, sequence);

}

public static object __new__(CodeContext/*!*/ context, [NotNone] PythonType cls) {

if (cls == TypeCache.PythonList) {

return new PythonList();

}

return cls.CreateInstance(context);

}

public static object __new__(CodeContext/*!*/ context, [NotNone] PythonType cls, object? arg)

=> __new__(context, cls);

public static object __new__(CodeContext/*!*/ context, [NotNone] PythonType cls, [NotNone] params object[] args\u00F8)

=> __new__(context, cls);

public static object __new__(CodeContext/*!*/ context, [NotNone] PythonType cls, [ParamDictionary, NotNone] IDictionary<object, object> kwArgs\u00F8, [NotNone] params object[] args\u00F8)

=> __new__(context, cls);

#endregion

#region C# Constructors and Factories

public PythonList()

: this(0) {

}

public PythonList(CodeContext context, [NotNone] object sequence) {

if (sequence is ICollection items) {

_data = new object[items.Count];

int i = 0;

foreach (object? item in items) {

_data[i++] = item;

}

_size = i;

} else {

if (!PythonOps.TryInvokeLengthHint(context, sequence, out int len)) {

len = INITIAL_SIZE;

}

_data = new object[len];

ExtendNoLengthCheck(context, sequence);

}

}

internal PythonList(int capacity) {

if (capacity == 0) {

_data = ArrayUtils.EmptyObjects;

} else {

_data = new object[capacity];

}

}

internal PythonList(ICollection items)

: this(items.Count) {

int i = 0;

foreach (object? item in items) {

_data[i++] = item;

}

_size = i;

}

private PythonList(object?[] items) {

_data = items;

_size = _data.Length;

}

private PythonList(IEnumerator e)

: this(10) {

while (e.MoveNext()) AddNoLock(e.Current);

}

#if ALLOC_DEBUG

private static int total, totalSize, cnt, growthCnt, growthSize;

~PythonList() {

total += _data.Length;

totalSize += _size;

cnt++;

Console.Error.WriteLine("PythonList: allocated {0} used {1} total wasted {2} - grand total wasted {3}", _data.Length, _size, total-totalSize, growthSize + total - totalSize);

Console.Error.WriteLine(" Growing {0} {1} avg {2}", growthCnt, growthSize, growthSize / growthCnt);

}

#endif

internal static PythonList FromGenericCollection<T>(ICollection<T> items) {

var list = new PythonList(items.Count);

int i = 0;

foreach (object? item in items) {

list._data[i++] = item;

}

list._size = i;

return list;

}

internal static PythonList FromEnumerable(IEnumerable items) {

var enumerator = items.GetEnumerator();

try {

return new PythonList(enumerator);

} finally {

(enumerator as IDisposable)?.Dispose();

}

}

/// <summary>

/// Creates a new list with the data in the array and a size

/// the same as the length of the array. The array is held

/// onto and may be mutated in the future by the list.

/// </summary>

/// <param name="data">params array to use for lists storage</param>

internal static PythonList FromArrayNoCopy(params object[] data)

=> new PythonList(data);

#endregion

internal object?[] GetObjectArray() {

lock (this) {

return ArrayOps.CopyArray(_data, _size);

}

}

#region binary operators

public static PythonList operator +([NotNone] PythonList l1, [NotNone] PythonList l2) {

object?[] ret;

int size;

lock (l1) {

ret = ArrayOps.CopyArray(l1._data, GetAddSize(l1._size, l2._size));

size = l1._size;

}

lock (l2) {

if (l2._size + size > ret.Length) {

ret = ArrayOps.CopyArray(ret, GetAddSize(size, l2._size));

}

Array.Copy(l2._data, 0, ret, size, l2._size);

PythonList lret = new PythonList(ret);

lret._size = size + l2._size;

return lret;

}

}

public static PythonList operator +([NotNone] PythonList self, object? other) {

if (other is PythonList l) return self + l;

throw PythonOps.TypeError($"can only concatenate list (not \"{PythonOps.GetPythonTypeName(other)}\") to list");

}

/// <summary>

/// Gets a reasonable size for the addition of two arrays. We round

/// to a power of two so that we usually have some extra space if

/// the resulting array gets added to.

/// </summary>

private static int GetAddSize(int s1, int s2) {

int length = s1 + s2;

return GetNewSize(length);

}

private static int GetNewSize(int length) {

if (length > 256) {

return length + (128 - 1) & ~(128 - 1);

}

return length + (16 - 1) & ~(16 - 1);

}

public static PythonList operator *([NotNone] PythonList self, int count)

=> MultiplyWorker(self, count);

public static PythonList operator *(int count, [NotNone] PythonList self)

=> MultiplyWorker(self, count);

public static object operator *([NotNone] PythonList self, [NotNone] Index count)

=> PythonOps.MultiplySequence<PythonList>(MultiplyWorker, self, count, true);

public static object operator *([NotNone] Index count, [NotNone] PythonList self)

=> PythonOps.MultiplySequence<PythonList>(MultiplyWorker, self, count, false);

public static object operator *([NotNone] PythonList self, object? count) {

if (Converter.TryConvertToIndex(count, out int index)) {

return self * index;

}

throw PythonOps.TypeErrorForUnIndexableObject(count);

}

public static object operator *(object? count, [NotNone] PythonList self) {

if (Converter.TryConvertToIndex(count, out int index)) {

return index * self;

}

throw PythonOps.TypeErrorForUnIndexableObject(count);

}

private static PythonList MultiplyWorker(PythonList self, int count) {

if (count <= 0) return new PythonList(0);

int n, newCount;

object?[] ret;

lock (self) {

n = self._size;

//??? is this useful optimization

//???if (n == 1) return new PythonList(Array.ArrayList.Repeat(this[0], count));

try {

newCount = checked(n * count);

} catch (OverflowException) {

throw PythonOps.MemoryError();

}

ret = ArrayOps.CopyArray(self._data, newCount);

}

// this should be extremely fast for large count as it uses the same algoithim as efficient integer powers

// ??? need to test to see how large count and n need to be for this to be fastest approach

int block = n;

int pos = n;

while (pos < newCount) {

Array.Copy(ret, 0, ret, pos, Math.Min(block, newCount - pos));

pos += block;

block *= 2;

}

return new PythonList(ret);

}

#endregion

public virtual int __len__() => _size;

public virtual IEnumerator __iter__() {

// return type is strongly typed to IEnumerator so that

// we can call it w/o requiring an explicit conversion. If the

// user overrides this we'll place a conversion in the wrapper

// helper

return new PythonListIterator(this);

}

public virtual IEnumerator __reversed__()

=> new PythonListReverseIterator(this);

public virtual bool __contains__(object? value)

=> ContainsWorker(value);

internal bool ContainsWorker(object? value) {

bool lockTaken = false;

try {

MonitorUtils.Enter(this, ref lockTaken);

for (int i = 0; i < _size; i++) {

object? thisIndex = _data[i];

// release the lock while we may call user code...

MonitorUtils.Exit(this, ref lockTaken);

try {

if (PythonOps.IsOrEqualsRetBool(thisIndex, value))

return true;

} finally {

MonitorUtils.Enter(this, ref lockTaken);

}

}

} finally {

if (lockTaken) {

Monitor.Exit(this);

}

}

return false;

}

#region ISequence Members

internal void AddRange<T>(ICollection<T> otherList) {

foreach (object? o in otherList) append(o);

}

[SpecialName]

public virtual object InPlaceAdd(object? other) {

if (ReferenceEquals(this, other)) {

InPlaceMultiply(2);

} else {

IEnumerator e = PythonOps.GetEnumerator(other);

while (e.MoveNext()) {

append(e.Current);

}

}

return this;

}

[SpecialName]

public PythonList InPlaceMultiply(int count) {

lock (this) {

int n = _size;

int newCount;

try {

newCount = checked(n * count);

} catch (OverflowException) {

throw PythonOps.MemoryError();

}

EnsureSize(newCount);

int block = n;

int pos = n;

while (pos < newCount) {

Array.Copy(_data, 0, _data, pos, Math.Min(block, newCount - pos));

pos += block;

block *= 2;

}

_size = newCount;

}

return this;

}

[SpecialName]

public object InPlaceMultiply([NotNone] Index count)

=> PythonOps.MultiplySequence<PythonList>(InPlaceMultiplyWorker, this, count, true);

[SpecialName]

public object InPlaceMultiply(object? count) {

int index;

if (Converter.TryConvertToIndex(count, out index)) {

return InPlaceMultiply(index);

}

throw PythonOps.TypeErrorForUnIndexableObject(count);

}

private static PythonList InPlaceMultiplyWorker(PythonList self, int count)

=> self.InPlaceMultiply(count);

internal object?[] GetSliceAsArray(int start, int stop) {

if (start < 0) start = 0;

if (stop > Count) stop = Count;

lock (this) return ArrayOps.GetSlice(_data, start, stop);

}

private static readonly object _boxedOne = ScriptingRuntimeHelpers.Int32ToObject(1);

[System.Diagnostics.CodeAnalysis.NotNull]

public virtual object? this[[NotNone] Slice slice] {

get {

int start, stop, step, count;

slice.GetIndicesAndCount(_size, out start, out stop, out step, out count);

if ((step > 0 && start >= stop) || (step < 0 && start <= stop)) return new PythonList();

if (step == 1) {

object?[] ret;

lock (this) ret = ArrayOps.GetSlice(_data, start, stop);

return new PythonList(ret);

} else {

object?[] ret = new object[count];

lock (this) {

int ri = 0;

for (int i = 0, index = start; i < count; i++, index += step) {

ret[ri++] = _data[index];

}

}

return new PythonList(ret);

}

}

set {

if (slice.step != null && (!(slice.step is int) || !slice.step.Equals(_boxedOne))) {

// try to assign back to self: make a copy first

if (this == value) value = new PythonList((ICollection)value);

if (ValueRequiresNoLocks(value)) {

// we don't need to worry about lock ordering of accesses to the

// RHS & ourselves. We can lock once and avoid repeatedly locking/unlocking

// on each assign.

lock (this) {

slice.DoSliceAssign(SliceAssignNoLock, _size, value);

}

} else {

slice.DoSliceAssign(SliceAssign, _size, value);

}

} else {

slice.Indices(_size, out int start, out int stop, out int step);

if (value is PythonList lstVal) {

SliceNoStep(start, stop, lstVal);

} else {

SliceNoStep(start, stop, value);

}

}

}

}

private static bool ValueRequiresNoLocks(object? value)

=> value is PythonTuple || value is Array || value is FrozenSetCollection;

private void SliceNoStep(int start, int stop, PythonList other) {

// We don't lock other here - instead we read it's object array

// and size therefore having a stable view even if it resizes.

// This means if we had a multithreaded app like:

//

// T1 T2 T3

// l1[:] = [1] * 100 l1[:] = [2] * 100 l3[:] = l1[:]

//

// we can end up with both 1s and 2s in the array. This is the

// same as if our set was implemented on top of get/set item where

// we'd take and release the locks repeatedly.

int otherSize = other._size;

object?[] otherData = other._data;

lock (this) {

if ((stop - start) == otherSize) {

// we are simply replacing values, this is fast...

for (int i = 0; i < otherSize; i++) {

_data[i + start] = otherData[i];

}

} else {

// we are resizing the array (either bigger or smaller), we

// will copy the data array and replace it all at once.

stop = Math.Max(stop, start);

int newSize = _size - (stop - start) + otherSize;

object?[] newData = new object[GetNewSize(newSize)];

for (int i = 0; i < start; i++) {

newData[i] = _data[i];

}

for (int i = 0; i < otherSize; i++) {

newData[i + start] = otherData[i];

}

int writeOffset = otherSize - (stop - start);

for (int i = stop; i < _size; i++) {

newData[i + writeOffset] = _data[i];

}

_size = newSize;

_data = newData;

}

}

}

private void SliceNoStep(int start, int stop, object? value) {

// always copy from a List object, even if it's a copy of some user defined enumerator. This

// makes it easy to hold the lock for the duration fo the copy.

IList<object?> other = value as IList<object?> ?? new PythonList(PythonOps.GetEnumerator(value));

lock (this) {

if ((stop - start) == other.Count) {

// we are simply replacing values, this is fast...

for (int i = 0; i < other.Count; i++) {

_data[i + start] = other[i];

}

} else {

// we are resizing the array (either bigger or smaller), we

// will copy the data array and replace it all at once.

stop = Math.Max(stop, start);

int newSize = _size - (stop - start) + other.Count;

object?[] newData = new object[GetNewSize(newSize)];

for (int i = 0; i < start; i++) {

newData[i] = _data[i];

}

for (int i = 0; i < other.Count; i++) {

newData[i + start] = other[i];

}

int writeOffset = other.Count - (stop - start);

for (int i = stop; i < _size; i++) {

newData[i + writeOffset] = _data[i];

}

_size = newSize;

_data = newData;

}

}

}

private void SliceAssign(int index, object? value)

=> this[index] = value;

private void SliceAssignNoLock(int index, object? value)

=> _data[index] = value;

public virtual void __delitem__(int index) {

lock (this) RawDelete(PythonOps.FixIndex(index, _size));

}

public virtual void __delitem__(object? index) {

if (!Converter.TryConvertToIndex(index, out int idx))

throw PythonOps.TypeError("list indices must be integers or slices, not {0}", PythonOps.GetPythonTypeName(index));

__delitem__(idx);

}

public void __delitem__([NotNone] Slice slice) {

lock (this) {

slice.Indices(_size, out int start, out int stop, out int step);

if (step > 0 && (start >= stop)) return;

if (step < 0 && (start <= stop)) return;

if (step == 1) {

int i = start;

for (int j = stop; j < _size; j++, i++) {

_data[i] = _data[j];

}

_size -= stop - start;

return;

}

if (step == -1) {

int i = stop + 1;

for (int j = start + 1; j < _size; j++, i++) {

_data[i] = _data[j];

}

_size -= start - stop;

return;

}

if (step < 0) {

// find "start" we will skip in the 1,2,3,... order

int i = start;

while (i > stop) {

i += step;

}

i -= step;

// swap start/stop, make step positive

stop = start + 1;

start = i;

step = -step;

}

int curr, skip, move;

// skip: the next position we should skip

// curr: the next position we should fill in data

// move: the next position we will check

curr = skip = move = start;

while (curr < stop && move < stop) {

if (move != skip) {

_data[curr++] = _data[move];

} else

skip += step;

move++;

}

while (stop < _size) {

_data[curr++] = _data[stop++];

}

_size = curr;

}

}

#endregion

private void RawDelete(int index) {

int len = _size - 1;

_size = len;

object?[] tempData = _data;

for (int i = index; i < len; i++) {

tempData[i] = tempData[i + 1];

}

tempData[len] = null;

}

internal void EnsureSize(int needed) {

if (_data.Length >= needed) return;

if (_data.Length == 0) {

// free growth, we wasted nothing

_data = new object[4];

return;

}

int newSize = Math.Max(_size * 3, 10);

while (newSize < needed) newSize *= 2;

#if ALLOC_DEBUG

growthCnt++;

growthSize += _size;

Console.Error.WriteLine("Growing {3} {0} {1} avg {2}", growthCnt, growthSize, growthSize/growthCnt, newSize - _size);

#endif

_data = ArrayOps.CopyArray(_data, newSize);

}

public void append(object? item) {

lock (this) {

AddNoLock(item);

}

}

/// <summary>

/// Non-thread safe adder, should only be used by internal callers that

/// haven't yet exposed their list.

/// </summary>

internal void AddNoLock(object? item) {

EnsureSize(_size + 1);

_data[_size] = item;

_size += 1;

}

internal void AddNoLockNoDups(object? item) {

for (int i = 0; i < _size; i++) {

if (PythonOps.IsOrEqualsRetBool(_data[i], item)) {

return;

}

}

AddNoLock(item);

}

internal void AppendListNoLockNoDups(PythonList list) {

if (list != null) {

foreach (object? item in list) {

AddNoLockNoDups(item);

}

}

}

public void clear() => Clear();

public int count(object? item) {

bool lockTaken = false;

try {

MonitorUtils.Enter(this, ref lockTaken);

int cnt = 0;

for (int i = 0, len = _size; i < len; i++) {

object? val = _data[i];

MonitorUtils.Exit(this, ref lockTaken);

try {

if (PythonOps.IsOrEqualsRetBool(val, item)) cnt++;

} finally {

MonitorUtils.Enter(this, ref lockTaken);

}

}

return cnt;

} finally {

if (lockTaken) {

Monitor.Exit(this);

}

}

}

public void extend([NotNone] PythonList/*!*/ seq) {

using (new OrderedLocker(this, seq)) {

// use the original count for if we're extending this w/ this

int count = seq.Count;

EnsureSize(Count + count);

for (int i = 0; i < count; i++) {

AddNoLock(seq[i]);

}

}

}

public void extend([NotNone] PythonTuple/*!*/ seq) {

lock (this) {

EnsureSize(Count + seq.Count);

for (int i = 0; i < seq.Count; i++) {

AddNoLock(seq[i]);

}

}

}

public void extend(CodeContext context, object? seq) {

if (PythonOps.TryInvokeLengthHint(context, seq, out int len)) {

EnsureSize(len);

}

ExtendNoLengthCheck(context, seq);

}

internal void ExtendNoLock(ICollection seq) {