Add Up Nested Sizes, Counting Each Object Once

Write deep_sizeof, which adds up the size of an object and everything it holds, and counts each object once:

def deep_sizeof(
    obj: object,
    sizer: Callable[[object], int],
    seen: set[int] | None = None,
) -> int: ...

sizer returns one object's shallow size. In real code you would pass sys.getsizeof. The tests pass fake_size, so that the numbers are the same on every platform.

What to write

Visit objects with a loop and a list used as a stack of objects still to visit, not with recursion. One test nests 5,000 lists, which is deeper than Python's recursion limit. For each object you take from the stack:

• If its id is already in seen, skip it. It adds nothing, and you do not visit its contents again.
• Otherwise, add its id to seen, call sizer on it once, and add the result to the total.

Then use the first rule that matches:

1. For a str, bytes or bytearray, stop there.
2. For a collections.abc.Mapping, visit its keys and its values.
3. For a collections.abc.Sequence or collections.abc.Set, visit its items.
4. For anything else, stop there.

Check the abstract classes from collections.abc, not list or dict, so other collections follow the same rules. Do not look at an object's attributes, and do not loop over generators or other iterables.

This gives the results the tests check:

• An object that appears twice counts once.
• Equal but separate objects each count.
• A list that contains itself does not loop forever.

When seen is None, start a new empty set. When the caller passes a set, even an empty one, add to that same set. The caller can then measure several roots without counting a shared object twice. That works only while the objects stay alive, because Python can reuse the id of a freed object.

The order in which you visit objects does not matter. You can assume the data does not change while you measure it.

The supplied sizes and scenarios

Keep fake_size, build and solve as they are. fake_size uses made-up sizes:

A size of 0 does not stop the visit. A set has size 0 here, but you still visit its items.

build(scenario, n) makes the test data, and solve returns {"deep": deep_sizeof(root, fake_size), "shallow": fake_size(root)}. n is never negative, and it is at most 256 for the dictionary. The cyclic, alias, two_blobs and strings scenarios ignore n.

assert solve("shared", 3) == {"deep": 168, "shallow": 80}
assert solve("distinct", 3) == {"deep": 344, "shallow": 80}
assert solve("cyclic", 0) == {"deep": 160, "shallow": 72}

Your code must pass mypy --strict.