import sys

from testutils import assert_raises

x = [1, 2, 3]
assert x[0] == 1
assert x[1] == 2
# assert x[7]

y = [2, *x]
assert y == [2, 1, 2, 3]

y.extend(x)
assert y == [2, 1, 2, 3, 1, 2, 3]

a = []
a.extend((1, 2, 3, 4))
assert a == [1, 2, 3, 4]

a.extend("abcdefg")
assert a == [1, 2, 3, 4, "a", "b", "c", "d", "e", "f", "g"]

a.extend(range(10))
assert a == [
    1,
    2,
    3,
    4,
    "a",
    "b",
    "c",
    "d",
    "e",
    "f",
    "g",
    0,
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
]

a = []
a.extend({1, 2, 3, 4})
assert a == [1, 2, 3, 4]

a.extend({"a": 1, "b": 2, "z": 51})
assert a == [1, 2, 3, 4, "a", "b", "z"]


class Iter:
    def __iter__(self):
        yield 12
        yield 28


a.extend(Iter())
assert a == [1, 2, 3, 4, "a", "b", "z", 12, 28]

a.extend(bytes(b"hello world"))
assert a == [
    1,
    2,
    3,
    4,
    "a",
    "b",
    "z",
    12,
    28,
    104,
    101,
    108,
    108,
    111,
    32,
    119,
    111,
    114,
    108,
    100,
]


class Next:
    def __next__(self):
        yield 12
        yield 28


assert_raises(TypeError, lambda: [].extend(3))
assert_raises(TypeError, lambda: [].extend(slice(0, 10, 1)))

assert x * 0 == [], "list __mul__ by 0 failed"
assert x * -1 == [], "list __mul__ by -1 failed"
assert x * 2 == [1, 2, 3, 1, 2, 3], "list __mul__ by 2 failed"
y = x
x *= 2
assert y is x
assert x == [1, 2, 3] * 2

# index()
assert ["a", "b", "c"].index("b") == 1
assert [5, 6, 7].index(7) == 2
assert_raises(ValueError, lambda: ["a", "b", "c"].index("z"))

x = [[1, 0, -3], "a", 1]
y = [[3, 2, 1], "z", 2]
assert x < y, "list __lt__ failed"

x = [5, 13, 31]
y = [1, 10, 29]
assert x > y, "list __gt__ failed"


x = [0, 1, 2]
assert x.pop() == 2
assert x == [0, 1]


def test_pop(lst, idx, value, new_lst):
    assert lst.pop(idx) == value
    assert lst == new_lst


test_pop([0, 1, 2], -1, 2, [0, 1])
test_pop([0, 1, 2], 0, 0, [1, 2])
test_pop([0, 1, 2], 1, 1, [0, 2])
test_pop([0, 1, 2], 2, 2, [0, 1])
assert_raises(IndexError, lambda: [].pop())
assert_raises(IndexError, lambda: [].pop(0))
assert_raises(IndexError, lambda: [].pop(-1))
assert_raises(IndexError, lambda: [0].pop(1))
assert_raises(IndexError, lambda: [0].pop(-2))

recursive = []
recursive.append(recursive)
assert repr(recursive) == "[[...]]"


def test_repr_mutation():
    class ReplaceNext:
        def __repr__(self):
            values[1] = 42
            return "item"

    values = [ReplaceNext(), 0]
    assert repr(values) == "[item, 42]"

    class AppendNext:
        def __repr__(self):
            values.append(42)
            return "item"

    values = [AppendNext()]
    assert repr(values) == "[item, 42]"

    class RemoveSelf:
        def __repr__(self):
            values.pop(0)
            return "item"

        def __del__(self):
            values.append(42)

    values = [RemoveSelf(), 0]
    assert repr(values) == "[item, 42]"


test_repr_mutation()

# insert()
x = ["a", "b", "c"]
x.insert(0, "z")  # insert is in-place, no return value
assert x == ["z", "a", "b", "c"]

x = ["a", "b", "c"]
x.insert(100, "z")
assert x == ["a", "b", "c", "z"]

x = ["a", "b", "c"]
x.insert(-1, "z")
assert x == ["a", "b", "z", "c"]

x = ["a", "b", "c"]
x.insert(-100, "z")
assert x == ["z", "a", "b", "c"]

assert_raises(OverflowError, lambda: x.insert(100000000000000000000, "z"))

x = [[], 2, {}]
y = x.copy()
assert x is not y
assert x == y
assert all(a is b for a, b in zip(x, y))
y.append(4)
assert x != y

a = [1, 2, 3]
assert len(a) == 3
a.remove(1)
assert len(a) == 2
assert not 1 in a

assert_raises(ValueError, lambda: a.remove(10), _msg="Remove not exist element")

foo = bar = [1]
foo += [2]
assert (foo, bar) == ([1, 2], [1, 2])


x = [1]
x.append(x)
assert x in x
assert x.index(x) == 1
assert x.count(x) == 1
x.remove(x)
assert x not in x


class Foo(object):
    def __eq__(self, x):
        return False


foo = Foo()
foo1 = Foo()
x = [1, foo, 2, foo, []]
assert x == x
assert foo in x
assert 2 in x
assert x.index(foo) == 1
assert x.count(foo) == 2
assert x.index(2) == 2
assert [] in x
assert x.index([]) == 4
assert foo1 not in x
x.remove(foo)
assert x.index(foo) == 2
assert x.count(foo) == 1

x = []
x.append(x)
assert x == x

a = [1, 2, 3]
b = [1, 2, 3]
c = [a, b]
a.append(c)
b.append(c)

assert a == b

assert [foo] == [foo]

for size in [1, 2, 3, 4, 5, 8, 10, 100, 1000]:
    lst = list(range(size))
    orig = lst[:]
    lst.sort()
    assert lst == orig
    assert sorted(lst) == orig
    assert_raises(ZeroDivisionError, sorted, lst, key=lambda x: 1 / x)
    lst.reverse()
    assert sorted(lst) == orig
    assert sorted(lst, reverse=True) == lst
    assert sorted(lst, key=lambda x: -x) == lst
    assert sorted(lst, key=lambda x: -x, reverse=True) == orig

assert sorted([(1, 2, 3), (0, 3, 6)]) == [(0, 3, 6), (1, 2, 3)]
assert sorted([(1, 2, 3), (0, 3, 6)], key=lambda x: x[0]) == [(0, 3, 6), (1, 2, 3)]
assert sorted([(1, 2, 3), (0, 3, 6)], key=lambda x: x[1]) == [(1, 2, 3), (0, 3, 6)]
assert sorted([(1, 2), (), (5,)], key=len) == [(), (5,), (1, 2)]

assert sorted(["b", "a", "é", "z\U0001f600", "z"]) == [
    "a",
    "b",
    "z",
    "z\U0001f600",
    "é",
]
assert sorted([10**30, -(10**30), 5, 0]) == [-(10**30), 0, 5, 10**30]
assert sorted([True, False, True]) == [False, True, True]


class IntSub(int):
    pass


assert sorted([IntSub(2), 3, IntSub(1)]) == [1, 2, 3]
assert sorted([2.5, 1, 3.0, 2]) == [1, 2, 2.5, 3.0]
assert_raises(TypeError, sorted, [1, "a"])
nan = float("nan")
assert repr(sorted([nan, 1.0, 2.0])) == "[nan, 1.0, 2.0]"
assert sorted([b"b", b"a", b"c"]) == [b"a", b"b", b"c"]
assert sorted([(2, 9), (1, 5), (2, 1)]) == [(1, 5), (2, 1), (2, 9)]
assert sorted([(1, "b"), (1, "a")]) == [(1, "a"), (1, "b")]
assert sorted([(1,), (1, 2), ()]) == [(), (1,), (1, 2)]
assert sorted([((2,), "x"), ((1,), "y")]) == [((1,), "y"), ((2,), "x")]
assert sorted([(1, "a"), (2.5, "b"), (0, "c")]) == [(0, "c"), (1, "a"), (2.5, "b")]

lst = [3, 1, 5, 2, 4]


class C:
    def __init__(self, x):
        self.x = x

    def __lt__(self, other):
        return self.x < other.x


lst.sort(key=C)
assert lst == [1, 2, 3, 4, 5]

lst = [3, 1, 5, 2, 4]


class C:
    def __init__(self, x):
        self.x = x

    def __gt__(self, other):
        return self.x > other.x


lst.sort(key=C)
assert lst == [1, 2, 3, 4, 5]


# Test that sorted() uses __lt__ (not __gt__) for comparisons.
# Track which comparison method is actually called during sort.
class TrackComparison:
    lt_calls = 0
    gt_calls = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        TrackComparison.lt_calls += 1
        return self.value < other.value

    def __gt__(self, other):
        TrackComparison.gt_calls += 1
        return self.value > other.value


# Reset and test sorted()
TrackComparison.lt_calls = 0
TrackComparison.gt_calls = 0
items = [TrackComparison(3), TrackComparison(1), TrackComparison(2)]
sorted(items)
assert TrackComparison.lt_calls > 0, "sorted() should call __lt__"
assert TrackComparison.gt_calls == 0, (
    f"sorted() should not call __gt__, but it was called {TrackComparison.gt_calls} times"
)

# Reset and test list.sort()
TrackComparison.lt_calls = 0
TrackComparison.gt_calls = 0
items = [TrackComparison(3), TrackComparison(1), TrackComparison(2)]
items.sort()
assert TrackComparison.lt_calls > 0, "list.sort() should call __lt__"
assert TrackComparison.gt_calls == 0, (
    f"list.sort() should not call __gt__, but it was called {TrackComparison.gt_calls} times"
)

# Reset and test sorted(reverse=True) - should still use __lt__, not __gt__
TrackComparison.lt_calls = 0
TrackComparison.gt_calls = 0
items = [TrackComparison(3), TrackComparison(1), TrackComparison(2)]
sorted(items, reverse=True)
assert TrackComparison.lt_calls > 0, "sorted(reverse=True) should call __lt__"
assert TrackComparison.gt_calls == 0, (
    f"sorted(reverse=True) should not call __gt__, but it was called {TrackComparison.gt_calls} times"
)

lst = [5, 1, 2, 3, 4]


def f(x):
    lst.append(1)
    return x


assert_raises(ValueError, lambda: lst.sort(key=f))  # "list modified during sort"
assert lst == [1, 2, 3, 4, 5]

# __delitem__
x = ["a", "b", "c"]
del x[0]
assert x == ["b", "c"]

x = ["a", "b", "c"]
del x[-1]
assert x == ["a", "b"]

x = y = [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15]
del x[2:14:3]
assert x == y
assert x == [1, 2, 4, 5, 7, 8, 11, 12, 14, 15]
assert y == [1, 2, 4, 5, 7, 8, 11, 12, 14, 15]

x = [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15]
del x[-5:]
assert x == [1, 2, 3, 4, 5, 6, 7, 8, 10]

x = list(range(12))
del x[10:2:-2]
assert x == [0, 1, 2, 3, 5, 7, 9, 11]


def bad_del_1():
    del ["a", "b"]["a"]


assert_raises(TypeError, bad_del_1)


def bad_del_2():
    del ["a", "b"][2]


assert_raises(IndexError, bad_del_2)

# __setitem__

# simple index
x = [1, 2, 3, 4, 5]
x[0] = "a"
assert x == ["a", 2, 3, 4, 5]
x[-1] = "b"
assert x == ["a", 2, 3, 4, "b"]
# make sure references are assigned correctly
y = []
x[1] = y
y.append(100)
assert x[1] == y
assert x[1] == [100]


# index bounds
def set_index_out_of_bounds_high():
    x = [0, 1, 2, 3, 4]
    x[5] = "a"


def set_index_out_of_bounds_low():
    x = [0, 1, 2, 3, 4]
    x[-6] = "a"


assert_raises(IndexError, set_index_out_of_bounds_high)
assert_raises(IndexError, set_index_out_of_bounds_low)

# non stepped slice index
a = list(range(10))
x = a[:]
y = a[:]
assert x == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# replace whole list
x[:] = ["a", "b", "c"]
y[::1] = ["a", "b", "c"]
assert x == ["a", "b", "c"]
assert x == y
# splice list start
x = a[:]
y = a[:]
z = a[:]
zz = a[:]
x[:1] = ["a", "b", "c"]
y[0:1] = ["a", "b", "c"]
z[:1:1] = ["a", "b", "c"]
zz[0:1:1] = ["a", "b", "c"]
assert x == ["a", "b", "c", 1, 2, 3, 4, 5, 6, 7, 8, 9]
assert x == y
assert x == z
assert x == zz
# splice list end
x = a[:]
y = a[:]
z = a[:]
zz = a[:]
x[5:] = ["a", "b", "c"]
y[5::1] = ["a", "b", "c"]
z[5:10] = ["a", "b", "c"]
zz[5:10:1] = ["a", "b", "c"]
assert x == [0, 1, 2, 3, 4, "a", "b", "c"]
assert x == y
assert x == z
assert x == zz


# A huge length hint is a MemoryError, not an aborted process
class HugeLen:
    def __len__(self):
        return 2**62

    def __getitem__(self, i):
        if i >= 3:
            raise IndexError
        return i


slice_target = [3, 1, 2]
with assert_raises(MemoryError):
    slice_target[1::-1] = HugeLen()


class ShortLen(HugeLen):
    def __len__(self):
        return 1


slice_target[::-1] = ShortLen()
assert slice_target == [2, 1, 0]


def fails_during_iteration():
    yield 9
    raise MemoryError


with assert_raises(MemoryError):
    slice_target[:] = fails_during_iteration()
assert slice_target == [2, 1, 0]


# insert sec
x = a[:]
y = a[:]
z = a[:]
zz = a[:]
x[1:1] = ["a", "b", "c"]
y[1:0] = ["a", "b", "c"]
z[1:1:1] = ["a", "b", "c"]
zz[1:0:1] = ["a", "b", "c"]
assert x == [0, "a", "b", "c", 1, 2, 3, 4, 5, 6, 7, 8, 9]
assert x == y
assert x == z
assert x == zz
# same but negative indexes?
x = a[:]
y = a[:]
z = a[:]
zz = a[:]
x[-1:-1] = ["a", "b", "c"]
y[-1:9] = ["a", "b", "c"]
z[-1:-1:1] = ["a", "b", "c"]
zz[-1:9:1] = ["a", "b", "c"]
assert x == [0, 1, 2, 3, 4, 5, 6, 7, 8, "a", "b", "c", 9]
assert x == y
assert x == z
assert x == zz
# splice mid
x = a[:]
y = a[:]
x[3:5] = ["a", "b", "c", "d", "e"]
y[3:5:1] = ["a", "b", "c", "d", "e"]
assert x == [0, 1, 2, "a", "b", "c", "d", "e", 5, 6, 7, 8, 9]
assert x == y
x = a[:]
x[3:5] = ["a"]
assert x == [0, 1, 2, "a", 5, 6, 7, 8, 9]
# assign empty to non stepped empty slice does nothing
x = a[:]
y = a[:]
x[5:2] = []
y[5:2:1] = []
assert x == a
assert y == a
# assign empty to non stepped slice removes elems
x = a[:]
y = a[:]
x[2:8] = []
y[2:8:1] = []
assert x == [0, 1, 8, 9]
assert x == y
# make sure references are assigned correctly
yy = []
x = a[:]
y = a[:]
x[3:5] = ["a", "b", "c", "d", yy]
y[3:5:1] = ["a", "b", "c", "d", yy]
assert x == [0, 1, 2, "a", "b", "c", "d", [], 5, 6, 7, 8, 9]
assert x == y
yy.append(100)
assert x == [0, 1, 2, "a", "b", "c", "d", [100], 5, 6, 7, 8, 9]
assert x == y
assert x[7] == yy
assert x[7] == [100]
assert y[7] == yy
assert y[7] == [100]


# no zero step
def no_zero_step_set():
    x = [1, 2, 3, 4, 5]
    x[0:4:0] = [11, 12, 13, 14, 15]


assert_raises(ValueError, no_zero_step_set)

# stepped slice index
# forward slice
x = a[:]
x[2:8:2] = ["a", "b", "c"]
assert x == [0, 1, "a", 3, "b", 5, "c", 7, 8, 9]
x = a[:]
y = a[:]
z = a[:]
zz = a[:]
c = ["a", "b", "c", "d", "e"]
x[::2] = c
y[-10::2] = c
z[0:10:2] = c
zz[-13:13:2] = c  # slice indexes will be truncated to bounds
assert x == ["a", 1, "b", 3, "c", 5, "d", 7, "e", 9]
assert x == y
assert x == z
assert x == zz
# backward slice
x = a[:]
x[8:2:-2] = ["a", "b", "c"]
assert x == [0, 1, 2, 3, "c", 5, "b", 7, "a", 9]
x = a[:]
y = a[:]
z = a[:]
zz = a[:]
c = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
x[::-1] = c
y[9:-11:-1] = c
z[9::-1] = c
zz[11:-13:-1] = c  # slice indexes will be truncated to bounds
assert x == ["j", "i", "h", "g", "f", "e", "d", "c", "b", "a"]
assert x == y
assert x == z
assert x == zz
# step size bigger than len
x = a[:]
x[::200] = ["a"]
assert x == ["a", 1, 2, 3, 4, 5, 6, 7, 8, 9]
x = a[:]
x[5::200] = ["a"]
assert x == [0, 1, 2, 3, 4, "a", 6, 7, 8, 9]


# bad stepped slices
def stepped_slice_assign_too_big():
    x = [0, 1, 2, 3, 4]
    x[::2] = ["a", "b", "c", "d"]


assert_raises(ValueError, stepped_slice_assign_too_big)


def stepped_slice_assign_too_small():
    x = [0, 1, 2, 3, 4]
    x[::2] = ["a", "b"]


assert_raises(ValueError, stepped_slice_assign_too_small)


# must assign iter t0 slice
def must_assign_iter_to_slice():
    x = [0, 1, 2, 3, 4]
    x[::2] = 42


assert_raises(TypeError, must_assign_iter_to_slice)

# other iterables?
a = list(range(10))

# string
x = a[:]
x[3:8] = "abcdefghi"
assert x == [0, 1, 2, "a", "b", "c", "d", "e", "f", "g", "h", "i", 8, 9]

# tuple
x = a[:]
x[3:8] = (11, 12, 13, 14, 15)
assert x == [0, 1, 2, 11, 12, 13, 14, 15, 8, 9]


# class
# __next__
class CIterNext:
    def __init__(self, sec=(1, 2, 3)):
        self.sec = sec
        self.index = 0

    def __iter__(self):
        return self

    def __next__(self):
        if self.index >= len(self.sec):
            raise StopIteration
        v = self.sec[self.index]
        self.index += 1
        return v


x = list(range(10))
x[3:8] = CIterNext()
assert x == [0, 1, 2, 1, 2, 3, 8, 9]


# __iter__ yield
class CIter:
    def __init__(self, sec=(1, 2, 3)):
        self.sec = sec

    def __iter__(self):
        for n in self.sec:
            yield n


x = list(range(10))
x[3:8] = CIter()
assert x == [0, 1, 2, 1, 2, 3, 8, 9]


# __getitem but no __iter__ sequence
class CGetItem:
    def __init__(self, sec=(1, 2, 3)):
        self.sec = sec

    def __getitem__(self, sub):
        return self.sec[sub]


x = list(range(10))
x[3:8] = CGetItem()
assert x == [0, 1, 2, 1, 2, 3, 8, 9]


# iter raises error
class CIterError:
    def __iter__(self):
        for i in range(10):
            if i > 5:
                raise RuntimeError
            yield i


def bad_iter_assign():
    x = list(range(10))
    x[3:8] = CIterError()


assert_raises(RuntimeError, bad_iter_assign)

# slice assign when step or stop is -1
a = list(range(10))
x = a[:]
x[-1:-5:-1] = ["a", "b", "c", "d"]
assert x == [0, 1, 2, 3, 4, 5, "d", "c", "b", "a"]
x = a[:]
x[-5:-1:-1] = []
assert x == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# is step != 1 and start or stop of slice == -1
x = list(range(10))
del x[-1:-5:-1]
assert x == [0, 1, 2, 3, 4, 5]
x = list(range(10))
del x[-5:-1:-1]

assert [1, 2].__ne__([])
assert [2, 1].__ne__([1, 2])
assert not [1, 2].__ne__([1, 2])
assert [1, 2].__ne__(1) == NotImplemented

# list gt, ge, lt, le
assert_raises(TypeError, lambda: [0, []] < [0, 0])
assert_raises(TypeError, lambda: [0, []] <= [0, 0])
assert_raises(TypeError, lambda: [0, []] > [0, 0])
assert_raises(TypeError, lambda: [0, []] >= [0, 0])

assert_raises(TypeError, lambda: [0, 0] < [0, []])
assert_raises(TypeError, lambda: [0, 0] <= [0, []])
assert_raises(TypeError, lambda: [0, 0] > [0, []])
assert_raises(TypeError, lambda: [0, 0] >= [0, []])

assert [0, 0] < [1, -1]
assert [0, 0] < [0, 0, 1]
assert [0, 0] < [0, 0, -1]
assert [0, 0] <= [0, 0, -1]
assert not [0, 0, 0, 0] <= [0, -1]

assert [0, 0] > [-1, 1]
assert [0, 0] >= [-1, 1]
assert [0, 0, 0] >= [-1, 1]

assert [0, 0] <= [0, 1]
assert [0, 0] <= [0, 0]
assert [0, 0] <= [0, 0]
assert not [0, 0] > [0, 0]
assert not [0, 0] < [0, 0]

assert not [float("nan"), float("nan")] <= [float("nan"), 1]
assert not [float("nan"), float("nan")] <= [float("nan"), float("nan")]
assert not [float("nan"), float("nan")] >= [float("nan"), float("nan")]
assert not [float("nan"), float("nan")] < [float("nan"), float("nan")]
assert not [float("nan"), float("nan")] > [float("nan"), float("nan")]

assert [float("inf"), float("inf")] >= [float("inf"), 1]
assert [float("inf"), float("inf")] <= [float("inf"), float("inf")]
assert [float("inf"), float("inf")] >= [float("inf"), float("inf")]
assert not [float("inf"), float("inf")] < [float("inf"), float("inf")]
assert not [float("inf"), float("inf")] > [float("inf"), float("inf")]

# list __iadd__
a = []
a += [1, 2, 3]
assert a == [1, 2, 3]

a = []
a += (1, 2, 3, 4)
assert a == [1, 2, 3, 4]

a += "abcdefg"
assert a == [1, 2, 3, 4, "a", "b", "c", "d", "e", "f", "g"]

a += range(10)
assert a == [
    1,
    2,
    3,
    4,
    "a",
    "b",
    "c",
    "d",
    "e",
    "f",
    "g",
    0,
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
]

a = []
a += {1, 2, 3, 4}
assert a == [1, 2, 3, 4]

a += {"a": 1, "b": 2, "z": 51}
assert a == [1, 2, 3, 4, "a", "b", "z"]


class Iter:
    def __iter__(self):
        yield 12
        yield 28


a += Iter()
assert a == [1, 2, 3, 4, "a", "b", "z", 12, 28]

a += bytes(b"hello world")
assert a == [
    1,
    2,
    3,
    4,
    "a",
    "b",
    "z",
    12,
    28,
    104,
    101,
    108,
    108,
    111,
    32,
    119,
    111,
    114,
    108,
    100,
]


class Next:
    def __next__(self):
        yield 12
        yield 28


def iadd_int():
    a = []
    a += 3


def iadd_slice():
    a = []
    a += slice(0, 10, 1)


assert_raises(TypeError, iadd_int)
assert_raises(TypeError, iadd_slice)


it = iter([1, 2, 3, 4])
assert it.__length_hint__() == 4
assert next(it) == 1
assert it.__length_hint__() == 3
assert list(it) == [2, 3, 4]
assert it.__length_hint__() == 0

it = reversed([1, 2, 3, 4])
assert it.__length_hint__() == 4
assert next(it) == 4
assert it.__length_hint__() == 3
assert list(it) == [3, 2, 1]
assert it.__length_hint__() == 0

a = [*[1, 2], 3, *[4, 5]]
assert a == [1, 2, 3, 4, 5]

# Test for list unpacking evaluation order (https://github.com/RustPython/RustPython/issues/5566)
a = [1, 2]
b = [a.append(3), *a, a.append(4), *a]
assert a == [1, 2, 3, 4]
assert b == [None, 1, 2, 3, None, 1, 2, 3, 4]

for base in object, list, tuple:
    # do not assume that a type inherited from some sequence type behaves like
    # that sequence type
    class C(base):
        def __iter__(self):
            a.append(2)

            def inner():
                yield 3
                a.append(4)

            return inner()

    a = [1]
    b = [*a, *C(), *a.copy()]
    assert b == [1, 3, 1, 2, 4]


# Test for list entering daedlock or not (https://github.com/RustPython/RustPython/pull/2933)
class MutatingCompare:
    def __eq__(self, other):
        self.list.pop()
        return True


m = MutatingCompare()

l = [1, 2, 3, m, 4]
m.list = l
assert l.count(4) == 1

l = [1, 2, 3, m, 4]
m.list = l
assert l.index(4) == 3

l = [1, 2, 3, m, 4]
m.list = l
l.remove(4)
assert_raises(ValueError, lambda: l.index(4))  # element 4 must not be in the list


# Test no panic occurred when list elements was deleted in __eq__
class rewrite_list_eq(list):
    pass


class poc:
    def __eq__(self, other):
        list1.clear()
        return self


list1 = rewrite_list_eq([poc()])
list1.remove(list1)
assert list1 == []

# The repeat count is multiplied by the element size; a count that overflows
# that product must raise instead of wrapping into a short allocation.
with assert_raises(MemoryError):
    [1] * sys.maxsize

# 64-bit only: on 32-bit targets 10**17 does not fit in an index so the
# repeat raises OverflowError before any allocation is attempted
if sys.maxsize > 2**32:
    assert_raises(MemoryError, lambda: [1, 2, 3] * (10**17))

    def imul_no_memory():
        x = [1, 2, 3]
        x *= 10**17

    assert_raises(MemoryError, imul_no_memory)


# A list takes the length an iterable reports before reading it, so one that
# reports more than can be held says so instead of filling memory.
class Reports:
    def __init__(self, hint):
        self.hint = hint

    def __iter__(self):
        return iter([1, 2, 3])

    def __length_hint__(self):
        return self.hint


with assert_raises(MemoryError):
    list(Reports(sys.maxsize))
with assert_raises(MemoryError):
    [].extend(Reports(sys.maxsize))
with assert_raises(MemoryError):
    empty = []
    empty += Reports(sys.maxsize)

# A report that leaves no room for what the list already holds cannot be true,
# so it is passed over rather than refused.
held = [1, 2, 3, 4]
held.extend(Reports(sys.maxsize))
assert held == [1, 2, 3, 4, 1, 2, 3]


# Reporting runs the iterable's own code, so what the list holds is counted
# after the report rather than before it.
grew = []


class Grows:
    def __iter__(self):
        return iter([7])

    def __length_hint__(self):
        grew.extend([0] * 100)
        return sys.maxsize - 50


grew.extend(Grows())
assert len(grew) == 101 and grew[-1] == 7, grew[-3:]

shrunk = [1] * 100


class Shrinks:
    def __iter__(self):
        return iter([])

    def __length_hint__(self):
        shrunk.clear()
        return sys.maxsize


with assert_raises(MemoryError):
    shrunk.extend(Shrinks())


# Only the callers that take the room ask at all, which is why an iterable whose
# __len__ raises reaches tuple() but not list().
class Lazy:
    def __len__(self):
        raise NotImplementedError

    def __iter__(self):
        return iter([1, 2, 3])


assert tuple(Lazy()) == (1, 2, 3)
assert (lambda *a: a)(*Lazy()) == (1, 2, 3)
assert min(Lazy()) == 1
with assert_raises(NotImplementedError):
    list(Lazy())
with assert_raises(NotImplementedError):
    sorted(Lazy())
with assert_raises(NotImplementedError):
    [].extend(Lazy())
with assert_raises(NotImplementedError):
    [*Lazy()]


# Nothing asks the iterator, so what it would have answered never runs.
class LoudIterator:
    def __init__(self):
        self.i = iter([1, 2, 3])

    def __iter__(self):
        return self

    def __next__(self):
        return next(self.i)

    def __length_hint__(self):
        raise NotImplementedError


class HandsOutLoud:
    def __iter__(self):
        return LoudIterator()


assert tuple(HandsOutLoud()) == (1, 2, 3)
assert (lambda *a: a)(*HandsOutLoud()) == (1, 2, 3)
assert min(HandsOutLoud()) == 1
assert max(HandsOutLoud()) == 3
assert list(HandsOutLoud()) == [1, 2, 3]
assert sorted(HandsOutLoud()) == [1, 2, 3]
assert bytearray(HandsOutLoud()) == bytearray(b"\x01\x02\x03")
held = [0]
held.extend(HandsOutLoud())
assert held == [0, 1, 2, 3]


# A report the list can act on is acted on.
assert list(Reports(3)) == [1, 2, 3]
assert list(Reports(0)) == [1, 2, 3]

# Repeating an empty list by a huge count returns at once
empty = []
empty *= sys.maxsize
assert empty == []
assert [] * sys.maxsize == []


def test_incremental_list_updates():
    def iadd(target, source):
        target += source

    for update in (list.extend, iadd, list.__init__):
        target = [0]
        initial = [] if update is list.__init__ else [0]

        def source():
            assert target == initial
            yield 7
            assert target == initial + [7]
            yield 8
            raise RuntimeError("source failed")

        with assert_raises(RuntimeError):
            update(target, source())
        assert target == initial + [7, 8]

    class ListSubclass(list):
        def __iter__(self):
            raise AssertionError("self-extension must use stored elements")

        def __len__(self):
            raise AssertionError("self-extension must use stored length")

    for update in (list.extend, iadd):
        target = ListSubclass([1, 2])
        update(target, target)
        assert target == [1, 2, 1, 2]
    target[::-1] = target
    assert target == [2, 1, 2, 1]
    target.__init__(target)
    assert target == []


test_incremental_list_updates()


def test_extend_length_hint_capacity():
    class Source:
        def __init__(self, values, hint):
            self.values = values
            self.hint = hint

        def __iter__(self):
            return iter(self.values)

        def __length_hint__(self):
            return self.hint

    for values in ((), (1, 2, 3)):
        target = []
        target.extend(Source(values, 4096))
        assert target == list(values)
        if values:
            assert target.__sizeof__() <= ([None] * 16).__sizeof__()
        else:
            assert target.__sizeof__() == [].__sizeof__()

    # Small extensions must retain the spare capacity from ordinary growth.
    target = list(range(32))
    target.extend(Source((32,), 0))
    size = target.__sizeof__()
    target.extend(Source((33,), 0))
    assert target.__sizeof__() == size
    assert target == list(range(34))

    # Iteration errors preserve both the accepted prefix and its reservation.
    sizes = []
    target = []

    def failing():
        yield 1
        sizes.append(target.__sizeof__())
        raise RuntimeError("source failed")

    with assert_raises(RuntimeError):
        target.extend(Source(failing(), 4096))
    assert target == [1]
    assert target.__sizeof__() == sizes[0]


test_extend_length_hint_capacity()


def test_extend_resizes_before_iterator_cleanup():
    target = []
    empty_size = target.__sizeof__()
    sizes = []

    class Iterator:
        def __iter__(self):
            return self

        def __next__(self):
            raise StopIteration

        def __del__(self):
            sizes.append(target.__sizeof__())
            target.append(1)

    class Source:
        def __iter__(self):
            return Iterator()

        def __length_hint__(self):
            return 4096

    target.extend(Source())
    assert sizes == [empty_size]
    assert target == [1]


test_extend_resizes_before_iterator_cleanup()


def test_slice_assignment_iterator_hint():
    class Rows:
        def __iter__(self):
            return iter([7, 8])

        def __len__(self):
            raise AssertionError("slice assignment must ask the iterator")

    target = [0]
    target[:] = Rows()
    assert target == [7, 8]


test_slice_assignment_iterator_hint()


# A failing iterator hint aborts slice assignment without changing the list.
target = [0]
with assert_raises(NotImplementedError):
    target[:] = LoudIterator()
assert target == [0]


def test_list_mutation_finalizers():
    cases = (
        (lambda a: a.__setitem__(0, 99), [99, 1, 2, 3], [0]),
        (lambda a: a.__delitem__(0), [1, 2, 3], [0]),
        (lambda a: a.__imul__(0), [], [3, 2, 1, 0]),
        (list.clear, [], [3, 2, 1, 0]),
        (lambda a: a.__setitem__(slice(1, 3), [10, 11]), [0, 10, 11, 3], [2, 1]),
        (lambda a: a.__delitem__(slice(1, 3)), [0, 3], [2, 1]),
        (
            lambda a: a.__setitem__(slice(None, None, 2), [10, 11]),
            [10, 1, 11, 3],
            [0, 2],
        ),
        (
            lambda a: a.__setitem__(slice(None, None, -2), [10, 11]),
            [0, 11, 2, 10],
            [3, 1],
        ),
        (lambda a: a.__delitem__(slice(None, None, -2)), [0, 2], [1, 3]),
        (lambda a: a.__delitem__(slice(None, None, -1)), [], [0, 1, 2, 3]),
    )
    for mutate, expected, order in cases:
        target = []
        seen = []

        class Item:
            def __init__(self, value):
                self.value = value

            def __del__(self):
                snapshot = [x.value if isinstance(x, Item) else x for x in target]
                seen.append((self.value, snapshot))
                target.append("released")

        target.extend(Item(i) for i in range(4))
        mutate(target)
        assert seen == [
            (value, expected + ["released"] * i) for i, value in enumerate(order)
        ]
        target.clear()

    target = []

    class Rejected:
        def __del__(self):
            target.append("released")

    with assert_raises(IndexError):
        target[0] = Rejected()
    assert target == ["released"]


test_list_mutation_finalizers()


def test_slice_replacement_lifetime():
    events = []
    target = []

    class Old:
        def __init__(self, value):
            self.value = value

        def __del__(self):
            events.append(("old start", self.value))
            target.clear()
            events.append(("old end", self.value))

    class New:
        def __init__(self, value):
            self.value = value

        def __del__(self):
            events.append(("new", self.value))

    for selection in (slice(None), slice(None, None, -1)):
        events.clear()
        target.extend(Old(i) for i in range(2))
        target[selection] = (New(i) for i in range(2))
        assert events == [
            ("old start", 1),
            ("old end", 1),
            ("old start", 0),
            ("old end", 0),
            ("new", 1),
            ("new", 0),
        ]
        assert target == []

    events.clear()
    target.append(0)
    with assert_raises(ValueError):
        target[::2] = (New(i) for i in range(3))
    assert events == [("new", 2), ("new", 1), ("new", 0)]
    assert target == [0]

    def failing_source():
        yield New(0)
        yield New(1)
        raise RuntimeError("source failed")

    events.clear()
    with assert_raises(RuntimeError):
        target[:] = failing_source()
    assert events == [("new", 1), ("new", 0)]
    assert target == [0]


test_slice_replacement_lifetime()


def test_subscript_typeerror_message():
    def message(index):
        try:
            [0, 1, 2][index]
        except TypeError as err:
            return str(err)
        raise AssertionError("TypeError was not raised")

    assert message("x") == "list indices must be integers or slices, not str"

    Long = type("A" * 250, (), {})
    assert message(Long()) == "list indices must be integers or slices, not {}".format(
        "A" * 200
    )


test_subscript_typeerror_message()