IndexError: pop from an empty deque on tree.get_state()

[ganguera]

Hi @fmerg,

Thanks for sharing this cool project.

I'm currently working on stress testing my application, and I've encountered an issue that I believe is related to the codebase. During the stress test, I'm intermittently receiving an "IndexError: pop from an empty deque" error coming from "tree.get_state()".

Under normal circumstances it seems to be functioning correctly, however under stress conditions with many clients, this error is triggered. I've reviewed the code and I've seen you already profiled that particular section of code which made me think maybe is a known issue.

I'm reaching out to see if you or anyone else has encountered a similar issue or if you have any insights into what might be causing this error. Your expertise in this matter would be greatly appreciated.

Thank you in advance for your help. Please let me know if you need more information or if you'd like to discuss this further.

Best regards,
Guillem

def add_record(count, payload):
    leaf_index = tree.append_entry(payload)
    leaf_hash = tree.get_leaf(leaf_index)
    tree_state = tree.get_state(leaf_index)
    tree_index = tree.append_log(leaf_id=leaf_index, digest=tree_state)
    return leaf_index, leaf_hash, tree_index, tree_state

Traceback (most recent call last):
    File "/app/app/controllers/tree.py", line 85, in add_record
        tree_state = tree.get_state(leaf_index)
                     ^^^^^^^^^^^^^^^^^^^^^^^^^^
    File "/usr/local/lib/python3.11/site-packages/pymerkle/core.py", line 146, in get_state
        return self._get_root(0, size)
               ^^^^^^^^^^^^^^^^^^^^^^^
    File "/usr/local/lib/python3.11/site-packages/pymerkle/core.py", line 379, in _get_root
        node = _get_subroot(offset, width)
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^
    File "/usr/local/lib/python3.11/site-packages/pymerkle/core.py", line 304, in _get_subroot
        return self._get_subroot_uncached(offset, width)
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    File "/usr/local/lib/python3.11/site-packages/pymerkle/core.py", line 348, in _get_subroot_uncached
        rnode = popleft()
                ^^^^^^^^^
IndexError: pop from an empty deque

[fmerg]

Can you trace the values passed to _get_subroot_unached?

[ganguera]

There you go!

Traceback (most recent call last):
  File "/REDACTED/stress.py", line 14, in add_record
    tree_state = tree.get_state(leaf_index)
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^
    count = 91666
    ex = IndexError('pop from an empty deque')
    leaf_hash = b'\x12\x93\x95\xc8\xf8i\x86Q\xf1\x15\x10v*k"\xfdA5\'R\xfb\xc0"\x87\xf4\x89\xc5\xd1\x0f\x88\x83m'
    leaf_index = 445627
    payload = {'key': 'REDACTED DICT'}
  File "/REDACTED/.env/lib/python3.11/site-packages/pymerkle/core.py", line 146, in get_state
    return self._get_root(0, size)
           ^^^^^^^^^^^^^^^^^^^^^^^
    self = <sqlalchemytree.SqlAlchemyTree object at 0x1053902d0>
    size = 445627
  File "/REDACTED/.env/lib/python3.11/site-packages/pymerkle/core.py", line 379, in _get_root
    node = _get_subroot(offset, width)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^
    _get_subroot = <bound method BaseMerkleTree._get_subroot of <sqlalchemytree.SqlAlchemyTree object at 0x1053902d0>>
    append = <built-in method append of collections.deque object at 0x1089e22f0>
    exponents = [0, 1, 3, 4, 5, 7, 10, 11, 14, 15, 17, 18]
    limit = 445626
    node = b'\x12\x93\x95\xc8\xf8i\x86Q\xf1\x15\x10v*k"\xfdA5\'R\xfb\xc0"\x87\xf4\x89\xc5\xd1\x0f\x88\x83m'
    offset = 445624
    p = 1
    pop = <built-in method pop of collections.deque object at 0x1089e22f0>
    prepend = <built-in method appendleft of collections.deque object at 0x1089e22f0>
    self = <sqlalchemytree.SqlAlchemyTree object at 0x1053902d0>
    start = 0
    subroots = deque([b'\x12\x93\x95\xc8\xf8i\x86Q\xf1\x15\x10v*k"\xfdA5\'R\xfb\xc0"\x87\xf4\x89\xc5\xd1\x0f\x88\x83m'])
    width = 2
  File "/REDACTED/.env/lib/python3.11/site-packages/pymerkle/core.py", line 304, in _get_subroot
    return self._get_subroot_uncached(offset, width)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    offset = 445624
    self = <sqlalchemytree.SqlAlchemyTree object at 0x1053902d0>
    width = 2
  File "/REDACTED/.env/lib/python3.11/site-packages/pymerkle/core.py", line 348, in _get_subroot_uncached
    rnode = popleft()
            ^^^^^^^^^
    append = <built-in method append of collections.deque object at 0x1089e2110>
    count = 0
    hashfunc = <built-in function openssl_sha256>
    level = deque([])
    lnode = b'\x0c\x86\x96\x19\xd8 &L\xf8\x02\xda9\xe9\xd2\xae~\xf13\xabM\xca\xc7_B\xfe\x8as\xad\xb6\x8b\xbc\xf6'
    offset = 445624
    popleft = <built-in method popleft of collections.deque object at 0x1089e2110>
    prefx01 = b'\x01'
    self = <sqlalchemytree.SqlAlchemyTree object at 0x1053902d0>
    width = 2
IndexError: pop from an empty deque