Occasional AST constructor depth mismatch

[cpcloud]

• a detailed description of the bug or problem you are having

In some of our CI runs in the ibis project we occasionally see failures around AST depths mismmatching.

It's hard for me to reproduce locally.

• output of pip list from the virtual environment you are using

The number of transitive dependencies for ibis is large. I'm happy to list them here, but it may require a bit of discussion/help to get someone setup to reproduce this

• pytest and operating system versions

pytest: 7.2.2
os: linux 6.1.2 (NixOS)

• [ ] minimal example if possible

I don't know exactly what is minimal here, I'm having trouble reproducing it locally.

[RonnyPfannschmidt]

As is, this looks like a nightmare to debug

I believe as a starting point we ought to catch the error and raise a new one with more context

[cpcloud]

Happy to help move it closer to a neutral dream state if there's anything on the ibis side we can do or information you need to help debug it.

[cpcloud]

We're starting to see this failure much more often now (https://github.com/ibis-project/ibis/actions/runs/5602258994/jobs/10247421549).

[nicoddemus]

One thing I can think of to reproduce the problem is to use a pytest fork which uses a try/except block around the ast.parse call:

INTERNALERROR>   File "/home/runner/.virtualenvs/.venv/lib/python3.11/site-packages/_pytest/_code/source.py", line 185, in getstatementrange_ast
INTERNALERROR>     astnode = ast.parse(content, "source", "exec")

When that raises a SystemError, dump content to a file. Hopefully then you can use that content to create a smaller reproducer.

[RonnyPfannschmidt]

actually no fork needed, just ensure the conftest monkeypatches ast.parse with a wrapper that helps debug

[cpcloud]

Findings:

• Long SQLAlchemy/mako thread with the issue (though a different manifestation): Sporadic SyntaxException w/ Python3.11 sqlalchemy/mako#378
• Related CPython issue: AST constructor can stack overflow when compiling some deep trees python/cpython#95185
• Fix for AST constructor can stack overflow when compiling some deep trees python/cpython#95185 which introduced this error: python/cpython@86eb500

[cpcloud]

I was able to trigger the exception and get the source that was failing to compile.

Some notes:

• Running with

  pytest -m impala --snapshot-update --allow-snapshot-deletion -x --randomly-seed=3887795760
  

• Single process tests, no use of pytest-xdist (though it is installed)

Source

from __future__ import annotations

import functools
import weakref
from collections import Counter, defaultdict
from typing import TYPE_CHECKING, Any, Callable, MutableMapping

from bidict import bidict

from ibis.common.collections import FrozenDict
from ibis.common.exceptions import IbisError

if TYPE_CHECKING:
    from collections.abc import Iterator


def memoize(func: Callable) -> Callable:
    """Memoize a function."""
    cache = {}

    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        key = (args, FrozenDict(kwargs))
        try:
            return cache[key]
        except KeyError:
            result = func(*args, **kwargs)
            cache[key] = result
            return result

    return wrapper


class WeakCache(MutableMapping):
    __slots__ = ('_data',)

    def __init__(self):
        object.__setattr__(self, '_data', {})

    def __setattr__(self, name, value):
        raise TypeError(f"can't set {name}")

    def __len__(self) -> int:
        return len(self._data)

    def __iter__(self) -> Iterator[Any]:
        return iter(self._data)

    def __setitem__(self, key, value) -> None:
        # construct an alternative representation of the key using the id()
        # of the key's components, this prevents infinite recursions
        identifiers = tuple(id(item) for item in key)

        # create a function which removes the key from the cache
        def callback(ref_):
            return self._data.pop(identifiers, None)

        # create weak references for the key's components with the callback
        # to remove the cache entry if any of the key's components gets
        # garbage collected
        refs = tuple(weakref.ref(item, callback) for item in key)

        self._data[identifiers] = (value, refs)

    def __getitem__(self, key):
        identifiers = tuple(id(item) for item in key)
        value, _ = self._data[identifiers]
        return value

    def __delitem__(self, key):
        identifiers = tuple(id(item) for item in key)
        del self._data[identifiers]

    def __repr__(self):
        return f"{self.__class__.__name__}({self._data})"


class RefCountedCache:
    """A cache with reference-counted keys.

    We could implement `MutableMapping`, but the `__setitem__` implementation
    doesn't make sense and the `len` and `__iter__` methods aren't used.

    We can implement that interface if and when we need to.
    """

    def __init__(
        self,
        *,
        populate: Callable[[str, Any], None],
        lookup: Callable[[str], Any],
        finalize: Callable[[Any], None],
        generate_name: Callable[[], str],
        key: Callable[[Any], Any],
    ) -> None:
        self.cache = bidict()
        self.refs = Counter()
        self.populate = populate
        self.lookup = lookup
        self.finalize = finalize
        self.names = defaultdict(generate_name)
        self.key = key or (lambda x: x)

    def get(self, key, default=None):
        try:
            return self[key]
        except KeyError:
            return default

    def __getitem__(self, key):
        result = self.cache[key]
        self.refs[key] += 1
        return result

    def store(self, input) -> None:
        """Compute and store a reference to `key`."""
        key = self.key(input)
        name = self.names[key]
        self.populate(name, input)
        self.cache[key] = self.lookup(name)
        # nothing outside of this instance has referenced this key yet, so the
        # refcount is zero
        #
        # in theory it's possible to call store -> delitem which would raise an
        # exception, but in practice this doesn't happen because the only call
        # to store is immediately followed by a call to getitem.
        self.refs[key] = 0

    def __delitem__(self, key) -> None:
        # we need to remove the expression representing the computed physical
        # table as well as the expression that was used to create that table
        #
        # bidict automatically handles this for us; without it we'd have to do
        # to the bookkeeping ourselves with two dicts
        if (inv_key := self.cache.inverse.get(key)) is None:
            raise IbisError(
                "Key has already been released. Did you call "
                "`.release()` twice on the same expression?"
            )

        self.refs[inv_key] -= 1
        assert self.refs[inv_key] >= 0, f"refcount is negative: {self.refs[inv_key]:d}"

        if not self.refs[inv_key]:
            del self.cache[inv_key], self.refs[inv_key]
            self.finalize(key)

[nicoddemus]

Thanks @cpcloud!

Seems like this is an upstream issue fixed in python/cpython#95208, should we close this then?

[cpcloud]

Hm, isn't that the change that introduced the problem I'm seeing?

In particular these lines: https://github.com/python/cpython/pull/95208/files#diff-c4dd13901c011c278fe5b6d175fdd23ed94e51568fe6b2ee4215d5ab376be9a8R1403-R1405

[nicoddemus]

Ahh my bad, I did not read things thoroughly and thought this was fixed by that PR.

Hmm bummer, I cannot reproduce this on Windows (Python 3.11.3):

import ast
from pathlib import Path

content = Path("problem.py").read_text()
astnode = ast.parse(content, "source", "exec")

(With problem.py containing the source code from #10874 (comment)).

Can you see if you can reproduce the problem @cpcloud?

[cpcloud]

I tried reproducing it by creating a bunch of threads as well, no luck.

[cpcloud]

I don't think this has anything to do with the particular source code that's being parsed. I can reproduce this (but only when pytest is in the mix) and there are different files for which the problem is observed.

[cpcloud]

@nicoddemus Any chance I can help you get set up enough to reproduce this locally? I can only reproduce the issue when running pytest with our impala backend.

We have spent a ton of time making this kind of setup relatively easy to get started with. I'd even be happy to pair with you on it!

[nicoddemus]

Hi @cpcloud, I appreciate the offer but TBH I don't think I can spare the time to work on this, sorry. 😕

[cpcloud]

No worries, I understand!

[bluetech]

Seems like python/cpython#113035 should fix it which means the next Python point releases - 3.11.8, 3.12.2, 3.13. If this still happens with these releases, we can reopen.