"""Ёмкость списка: по какой формуле она растёт и от чего зависит запас.

ЗАЧЕМ ЭТОТ СКРИПТ. У списка два числа длины, и путают их постоянно: `len(L)` —
сколько элементов сейчас, `allocated` — сколько мест под указатели уже
выделено. Второе из Python не видно ни одним публичным именем, и именно оно
объясняет, почему `append` в среднем дёшев, почему один и тот же список из
десяти элементов занимает разное место в зависимости от того, как его
построили, и почему `sys.getsizeof` меняется скачками, а не по одному.

КАК ЧИТАЕТСЯ `allocated` БЕЗ ctypes. `list.__sizeof__` в CPython считает
`_PyObject_SIZE(Py_TYPE(self)) + allocated * sizeof(void*)` — то есть по
`allocated`, а НЕ по длине. Значит,

    allocated = (sys.getsizeof(L) - sys.getsizeof([])) // struct.calcsize("P")

Делитель — размер указателя, а не восьмёрка: на 64-битной сборке это 8, но
писать 8 значит зашивать разрядность в формулу. Способ опирается только на
публичный `getsizeof`, поэтому работает и в свободнопоточной сборке, где
ctypes-адресация полей объекта уже неверна: блок 1 печатает рядом ctypes-чтение
и СРАВНИВАЕТ два числа, а не объявляет, что они совпали. На сборке без GIL
ob_size по этому смещению читается как 0 — это и видно в записи прогона.

Сам способ — деталь реализации CPython: `list.__sizeof__` считает по
`allocated` потому, что так написано в `Objects/listobject.c`, а не потому, что
это обещано языком.

ЧТО ЗДЕСЬ НЕ МЕРЯЕТСЯ. Время. Байты и ёмкость — раскладка объекта, их между
версиями сравнивать можно; время между версиями не сравнивается вовсе
(bench/README.md), и его меряет `ops.py` отдельно.

ЗАПУСК:

    for v in 3.12 3.13 3.14; do python$v bench/lists/growth.py; done
"""

import ctypes
import platform
import struct
import sys

PTR = struct.calcsize("P")
EMPTY = sys.getsizeof([])


def allocated(seq: list) -> int:
    """Ёмкость списка — из getsizeof, потому что getsizeof считает именно её."""
    return (sys.getsizeof(seq) - EMPTY) // PTR


def allocated_ctypes(seq: list) -> int:
    """То же число, прочитанное из поля структуры. Только для сверки."""
    # PyObject_VAR_HEAD: ob_refcnt, ob_type, ob_size; затем ob_item, allocated.
    return ctypes.c_ssize_t.from_address(id(seq) + PTR * 4).value


def ob_size_ctypes(seq: list) -> int:
    return ctypes.c_ssize_t.from_address(id(seq) + PTR * 2).value


def item_ptr(seq: list) -> int:
    """Адрес самого массива указателей — поле ob_item. Только на сборках с GIL."""
    return ctypes.c_ssize_t.from_address(id(seq) + PTR * 3).value


def head(n: int, title: str) -> None:
    line = f"{n}. {title}"
    print(f"\n{line}\n{'-' * len(line)}")


def main() -> None:
    gil = getattr(sys, "_is_gil_enabled", lambda: True)()
    print(f"Python {platform.python_version()} · GIL {'включён' if gil else 'выключен'}")
    print(f"Сборка: {sys.version.split('[')[-1].rstrip('] ')}")
    print("\nЗдесь меряются байты и ёмкость — раскладка объекта, а не время.")
    print("Числа этого файла сравнимы между версиями; время — нет и не меряется.")

    head(1, "ДЛИНА И ЁМКОСТЬ — ЭТО РАЗНЫЕ ЧИСЛА")
    print(f"  размер указателя: struct.calcsize('P') = {PTR} Б")
    print(f"  sys.getsizeof([])                        {EMPTY} Б")
    print("  выражение            len  ёмкость  getsizeof  ctypes: ob_size/ёмкость")
    cap_agree = size_agree = True
    for expr in ("[]", "[0]", "[0]*5", "[0]*100"):
        seq = eval(expr)  # noqa: S307 — выражения свои, не из ввода
        if allocated_ctypes(seq) != allocated(seq):
            cap_agree = False
        if ob_size_ctypes(seq) != len(seq):
            size_agree = False
        print(
            f"  {expr:<18s} {len(seq):>5d} {allocated(seq):>8d} "
            f"{sys.getsizeof(seq):>10d}  {ob_size_ctypes(seq)}/{allocated_ctypes(seq)}"
        )
    # НЕ «совпало», а «вот что вышло». Раньше здесь стояла фраза о совпадении,
    # напечатанная безусловно, — и на сборке без GIL она была прямо неверна:
    # смещения полей там другие, ob_size по нашему читается нулём.
    print(f"\n  ёмкость: getsizeof и ctypes {'совпали' if cap_agree else 'РАСХОДЯТСЯ'}")
    print(f"  ob_size из ctypes {'совпал' if size_agree else 'РАСХОДИТСЯ'} с len")
    if not (cap_agree and size_agree):
        print("  Так и должно быть в этой сборке: ctypes читает поля по смещениям,")
        print("  а раскладка объекта здесь другая. Именно поэтому ёмкость дальше")
        print("  берётся из getsizeof — он не зависит от раскладки.")
    else:
        print("  Два независимых способа дали одно и то же. Дальше ёмкость берётся")
        print("  из getsizeof: он один работает во всех сборках.")

    head(2, "ЧТО ДЕЛАЕТ append: ЁМКОСТЬ РАСТЁТ СКАЧКАМИ")
    seq: list[int] = []
    prev = -1
    jumps = []
    for i in range(600):
        seq.append(i)
        cap = allocated(seq)
        if cap != prev:
            jumps.append((len(seq), cap))
            prev = cap
    print("  скачок происходит на длине, ёмкость становится равной:")
    print("    длина:  " + " ".join(f"{n:>5d}" for n, _ in jumps[:14]))
    print("    ёмкость:" + " ".join(f"{c:>5d}" for _, c in jumps[:14]))
    print(f"  всего скачков на первых 600 append: {len(jumps)}")
    print(f"  после 600 append: длина {len(seq)}, ёмкость {allocated(seq)}, "
          f"запас {allocated(seq) - len(seq)}")

    head(3, "ФОРМУЛА РОСТА И ЕЁ ПРОВЕРКА НА КАЖДОМ СКАЧКЕ")
    print("  new_allocated = (n + (n >> 3) + 6) & ~3, где n — новая длина")
    mismatch = [(n, c) for n, c in jumps if ((n + (n >> 3) + 6) & ~3) != c]
    for n, c in jumps[:8]:
        print(f"    n={n:<5d} формула={(n + (n >> 3) + 6) & ~3:<6d} на самом деле={c}")
    print(f"  совпало на всех {len(jumps)} скачках: {'да' if not mismatch else 'НЕТ'}")
    if mismatch:
        for n, c in mismatch:
            print(f"    РАСХОЖДЕНИЕ n={n}: формула {(n + (n >> 3) + 6) & ~3}, на самом деле {c}")
    print("  запас растёт как одна восьмая длины — то есть доля, а не константа.")

    head(4, "ФОРМА ПОСТРОЕНИЯ РЕШАЕТ, БУДЕТ ЛИ ЗАПАС")
    forms = [
        ("[0,1,2,3,4,5,6,7,8,9]", "литерал"),
        ("[0]*10", "повторение"),
        ("list(range(10))", "конструктор по длине"),
        ("list(x for x in range(10))", "конструктор по генератору"),
        ("[x for x in range(10)]", "списковое включение"),
    ]
    print("  выражение                        len  ёмкость  запас  getsizeof")
    for expr, kind in forms:
        seq = eval(expr)  # noqa: S307
        print(
            f"  {expr:<32s} {len(seq):>4d} {allocated(seq):>8d} "
            f"{allocated(seq) - len(seq):>6d} {sys.getsizeof(seq):>10d}   {kind}"
        )
    print("\n  Запас есть ровно у тех двух форм, которые не знают длину заранее.")
    print("  Остальные три её знают и берут место ровно под неё.")

    head(5, "ОДИН И ТОТ ЖЕ СПИСОК, ДВА СПОСОБА ПОСТРОИТЬ")
    by_append: list[int] = []
    for i in range(1000):
        by_append.append(i)
    exact = list(range(1000))
    print(f"  тысяча append          len={len(by_append):<6d} ёмкость={allocated(by_append):<6d} "
          f"getsizeof={sys.getsizeof(by_append)} Б")
    print(f"  list(range(1000))      len={len(exact):<6d} ёмкость={allocated(exact):<6d} "
          f"getsizeof={sys.getsizeof(exact)} Б")
    diff = sys.getsizeof(by_append) - sys.getsizeof(exact)
    print(f"  разница                {diff} Б на список — это запас, а не элементы")

    head(6, "ПЕРЕЕЗЖАЕТ ЛИ МАССИВ ПРИ РОСТЕ")
    print("  Ходовое объяснение запаса: «массив нельзя удлинить на месте».")
    print("  Проверяется это адресом самого массива: ob_item до скачка ёмкости")
    print("  и после. Если адрес тот же — realloc расширил выделение на месте,")
    print("  ничего не копируя.")
    if not gil:
        print("  В этой сборке проверка не делается: ctypes читает ob_item по")
        print("  смещению, а раскладка объекта здесь другая (см. блок 1).")
    else:
        for total in (600, 20000):
            grow: list[int] = []
            prev_cap = allocated(grow)
            prev_ptr = item_ptr(grow)
            stayed = moved = 0
            for i in range(total):
                grow.append(i)
                cap = allocated(grow)
                if cap == prev_cap:
                    continue
                ptr = item_ptr(grow)
                if ptr == prev_ptr and prev_ptr != 0:
                    stayed += 1
                else:
                    moved += 1
                prev_cap, prev_ptr = cap, ptr
            print(f"  {total:>6d} append: скачков {stayed + moved:>3d}, "
                  f"массив остался на месте {stayed:>3d}, переехал {moved:>3d}")
        print("\n  Оба исхода встречаются, и на длинном списке чаще первый. То есть")
        print("  удлинить массив на месте ИНОГДА можно; чего нельзя — рассчитывать")
        print("  на это: свободного места за концом может не оказаться, и тогда")
        print("  выделение переезжает вместе со всем содержимым. Запас берётся")
        print("  затем, чтобы такие переезды случались реже, а не потому, что")
        print("  расширение невозможно.")
        print("  Как именно поделятся скачки, зависит от состояния аллокатора и")
        print("  истории процесса; утверждается здесь только то, что оба исхода")
        print("  есть, а не пропорция.")


main()