Exercise 3 solution

    import struct

    HEADER = struct.Struct("<BH")
    FOLDER, FILE, NAME, SIZE = 0x10, 0x11, 1, 2
    CONTAINERS = {FOLDER}
    MAX_DEPTH = 4


    def pack_tlv(t, value):
        return HEADER.pack(t, len(value)) + value


    def iter_tlv(buf):
        pos = 0
        while pos < len(buf):
            if len(buf) - pos < HEADER.size:
                raise ValueError(f"truncated header at offset {pos}")
            t, n = HEADER.unpack_from(buf, pos)
            start = pos + HEADER.size
            if start + n > len(buf):
                raise ValueError(f"record at {pos} wants {n} bytes, {len(buf) - start} left")
            yield t, buf[start:start + n]
            pos = start + n


    def build(node):
        if node["kind"] == "file":
            body = pack_tlv(NAME, node["name"].encode()) + pack_tlv(SIZE, struct.pack("<I", node["size"]))
            return pack_tlv(FILE, body)
        body = pack_tlv(NAME, node["name"].encode())
        for child in node["children"]:
            body += build(child)
        return pack_tlv(FOLDER, body)


    def parse(buf, depth=0):
        if depth > MAX_DEPTH:
            raise ValueError("nested too deeply")
        nodes = []
        for t, v in iter_tlv(buf):
            if t == FILE:
                node = {"kind": "file", "name": None, "size": None}
                for ct, cv in iter_tlv(v):
                    if ct == NAME:
                        node["name"] = cv.decode()
                    elif ct == SIZE:
                        (node["size"],) = struct.unpack("<I", cv)
            elif t == FOLDER:
                node = {"kind": "folder", "name": None, "children": []}
                for ct, cv in iter_tlv(v):
                    if ct == NAME:
                        node["name"] = cv.decode()
                    elif ct in (FILE, FOLDER):
                        node["children"] += parse(pack_tlv(ct, cv), depth + 1)
            else:
                continue
            nodes.append(node)
        return nodes


    def show(nodes, indent=0):
        for n in nodes:
            if n["kind"] == "file":
                print("  " * indent + f"{n['name']} ({n['size']} bytes)")
            else:
                print("  " * indent + f"{n['name']}/")
                show(n["children"], indent + 1)


    tree = {"kind": "folder", "name": "root", "children": [
        {"kind": "file", "name": "a.txt", "size": 10},
        {"kind": "folder", "name": "docs", "children": [
            {"kind": "file", "name": "b.md", "size": 2048},
            {"kind": "folder", "name": "empty", "children": []},
        ]},
    ]}
    blob = build(tree)
    print(len(blob))
    back = parse(blob)
    show(back)
    print(back == [tree])

    deep = {"kind": "file", "name": "f", "size": 1}
    for i in range(7):
        deep = {"kind": "folder", "name": f"d{i}", "children": [deep]}
    try:
        parse(build(deep))
    except ValueError as e:
        print("deep ->", e)

    inner = pack_tlv(NAME, b"x") + HEADER.pack(FILE, 500) + b"abc"
    bad = pack_tlv(FOLDER, inner)
    try:
        parse(bad)
    except ValueError as e:
        print("overrun ->", e)

    try:
        parse(blob[:-1])
    except ValueError as e:
        print("cut ->", e)

    # 66
    # root/
    #   a.txt (10 bytes)
    #   docs/
    #     b.md (2048 bytes)
    #     empty/
    # True
    # deep -> nested too deeply
    # overrun -> record at 4 wants 500 bytes, 3 left
    # cut -> record at 0 wants 63 bytes, 62 left

(Run as written; the output matched the comments.)

Explanation: A folder's value is itself a run of records: its own name followed by its
children. parse reads that value with the same iterator, so a child can never read past its
parent, because the child sees only the parent's value bytes. That is why an inner length of
500 inside a 14-byte folder is caught as an overrun. The depth limit stops hostile input from
nesting records until the program runs out of stack.