gc.get_referrers() returns an empty list for an object with references

[ngoldbaum]

Bug report

Bug description:

I bisected and this is a regression that was introduced by 7ccacb2.

Steps to reproduce:

1. Clone numpy and cython repositories
2. Build python main branch with --disable-gil
3. Install numpy dependencies, build numpy, and run the full numpy test suite:

cd /path/to/numpy
python -m pip install setuptools ninja meson-python pytest hypothesis spin /path/to/cython
spin build --clean
spin test -- -x

On my machine, this very quickly exits with the following test failure:

_______________________________________________________________________________ TestArray2String.test_any_text _______________________________________________________________________________

self = <hypothesis.core.StateForActualGivenExecution object at 0x4ecdebabd10>, data = ConjectureData(OVERRUN, 0 bytes, frozen)

        with local_settings(self.settings):
            with deterministic_PRNG():
                with BuildContext(data, is_final=is_final) as context:
                    # providers may throw in per_case_context_fn, and we'd like
                    # `result` to still be set in these cases.
                    result = None
                    with data.provider.per_test_case_context_manager():
                        # Run the test function once, via the executor hook.
                        # In most cases this will delegate straight to `run(data)`.
>                       result = self.test_runner(data, run)

context    = <hypothesis.control.BuildContext object at 0x4ecdeba9910>
data       = ConjectureData(OVERRUN, 0 bytes, frozen)
example_kwargs = None
expected_failure = (HypothesisWarning('It looks like `register_random` was passed an object that could be garbage collected immediately a...a62810>\n\n../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/entropy.py:132: HypothesisWarning\n')
is_final   = True
print_example = True
result     = None
run        = <function StateForActualGivenExecution.execute_once.<locals>.run at 0x4ecdf7042e0>
self       = <hypothesis.core.StateForActualGivenExecution object at 0x4ecdebabd10>
test       = <function TestArray2String.test_any_text at 0x4ecd055f640>
text_repr  = None

../../../../../../hypothesis/hypothesis-python/src/hypothesis/core.py:951:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
../../../../../../hypothesis/hypothesis-python/src/hypothesis/core.py:739: in default_executor
    return function(data)
        data       = ConjectureData(OVERRUN, 0 bytes, frozen)
        function   = <function StateForActualGivenExecution.execute_once.<locals>.run at 0x4ecdf7042e0>
../../../../../../hypothesis/hypothesis-python/src/hypothesis/core.py:862: in run
    kw, argslices = context.prep_args_kwargs_from_strategies(
        args       = ()
        context    = <hypothesis.control.BuildContext object at 0x4ecdeba9910>
        data       = ConjectureData(OVERRUN, 0 bytes, frozen)
        example_kwargs = None
        expected_failure = (HypothesisWarning('It looks like `register_random` was passed an object that could be garbage collected immediately a...a62810>\n\n../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/entropy.py:132: HypothesisWarning\n')
        kwargs     = {'self': <numpy._core.tests.test_arrayprint.TestArray2String object at 0x4ecd0cf0610>}
        print_example = True
        self       = <hypothesis.core.StateForActualGivenExecution object at 0x4ecdebabd10>
        test       = <function TestArray2String.test_any_text at 0x4ecd055f640>
        text_repr  = None
../../../../../../hypothesis/hypothesis-python/src/hypothesis/control.py:157: in prep_args_kwargs_from_strategies
    obj = check(self.data.draw(s, observe_as=f"generate:{k}"))
        arg_labels = {}
        check      = <hypothesis.control._Checker object at 0x4ecdebacc10>
        k          = 'text'
        kwarg_strategies = {'text': from_dtype(dtype('<U'))}
        kwargs     = {}
        s          = from_dtype(dtype('<U'))
        self       = <hypothesis.control.BuildContext object at 0x4ecdeba9910>
        start_idx  = 0
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2387: in draw
    return strategy.do_draw(self)
        at_top_level = True
        key        = 'generate:text'
        label      = 7273923036097914769
        observe_as = 'generate:text'
        self       = ConjectureData(OVERRUN, 0 bytes, frozen)
        start_time = 6066655.102763833
        strategy   = from_dtype(dtype('<U'))
../../../../../../hypothesis/hypothesis-python/src/hypothesis/strategies/_internal/lazy.py:167: in do_draw
    return data.draw(self.wrapped_strategy)
        data       = ConjectureData(OVERRUN, 0 bytes, frozen)
        self       = from_dtype(dtype('<U'))
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2381: in draw
    return strategy.do_draw(self)
        at_top_level = False
        label      = 7273923036097914769
        observe_as = None
        self       = ConjectureData(OVERRUN, 0 bytes, frozen)
        start_time = None
        strategy   = text(alphabet=characters()).filter(lambda b: b[-1:] != "\0").map(str_)
../../../../../../hypothesis/hypothesis-python/src/hypothesis/strategies/_internal/lazy.py:167: in do_draw
    return data.draw(self.wrapped_strategy)
        data       = ConjectureData(OVERRUN, 0 bytes, frozen)
        self       = text(alphabet=characters()).filter(lambda b: b[-1:] != "\0").map(str_)
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2381: in draw
    return strategy.do_draw(self)
        at_top_level = False
        label      = 7273923036097914769
        observe_as = None
        self       = ConjectureData(OVERRUN, 0 bytes, frozen)
        start_time = None
        strategy   = text().filter(lambda b: b[-1:] != "\0").map(str_)
../../../../../../hypothesis/hypothesis-python/src/hypothesis/strategies/_internal/strategies.py:843: in do_draw
    x = data.draw(self.mapped_strategy)
        _          = 0
        data       = ConjectureData(OVERRUN, 0 bytes, frozen)
        self       = text().filter(lambda b: b[-1:] != "\0").map(str_)
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2381: in draw
    return strategy.do_draw(self)
        at_top_level = False
        label      = 10358930435738099914
        observe_as = None
        self       = ConjectureData(OVERRUN, 0 bytes, frozen)
        start_time = None
        strategy   = text().filter(lambda b: b[-1:] != "\0")
../../../../../../hypothesis/hypothesis-python/src/hypothesis/strategies/_internal/strategies.py:1006: in do_draw
    result = self.do_filtered_draw(data)
        data       = ConjectureData(OVERRUN, 0 bytes, frozen)
        self       = text().filter(lambda b: b[-1:] != "\0")
../../../../../../hypothesis/hypothesis-python/src/hypothesis/strategies/_internal/strategies.py:1016: in do_filtered_draw
    value = data.draw(self.filtered_strategy)
        data       = ConjectureData(OVERRUN, 0 bytes, frozen)
        i          = 0
        self       = text().filter(lambda b: b[-1:] != "\0")
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2381: in draw
    return strategy.do_draw(self)
        at_top_level = False
        label      = 13472932985108582247
        observe_as = None
        self       = ConjectureData(OVERRUN, 0 bytes, frozen)
        start_time = None
        strategy   = text()
../../../../../../hypothesis/hypothesis-python/src/hypothesis/strategies/_internal/strings.py:117: in do_draw
    return data.draw_string(
        __class__  = <class 'hypothesis.strategies._internal.strings.TextStrategy'>
        data       = ConjectureData(OVERRUN, 0 bytes, frozen)
        elems      = characters()
        self       = text()
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2162: in draw_string
    value = self.provider.draw_string(
        fake_forced = False
        forced     = None
        intervals  = IntervalSet(((0, 1114111),))
        kwargs     = {'intervals': IntervalSet(((0, 1114111),)), 'max_size': inf, 'min_size': 0}
        max_size   = inf
        min_size   = 0
        observe    = True
        self       = ConjectureData(OVERRUN, 0 bytes, frozen)
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:1562: in draw_string
    while elements.more():
        average_size = 5
        chars      = []
        elements   = <hypothesis.internal.conjecture.utils.many object at 0x4ecdebacd90>
        fake_forced = False
        forced     = None
        intervals  = IntervalSet(((0, 1114111),))
        max_size   = inf
        min_size   = 0
        self       = <hypothesis.internal.conjecture.data.HypothesisProvider object at 0x4ecdf608210>
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/utils.py:283: in more
    should_continue = self.data.draw_boolean(
        forced_result = None
        self       = <hypothesis.internal.conjecture.utils.many object at 0x4ecdebacd90>
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2240: in draw_boolean
    value = self.provider.draw_boolean(
        fake_forced = False
        forced     = None
        kwargs     = {'p': 0.8333333333333334}
        observe    = False
        p          = 0.8333333333333334
        self       = ConjectureData(OVERRUN, 0 bytes, frozen)
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:1326: in draw_boolean
    i = self._cd.draw_bits(
        bits       = 3
        fake_forced = False
        falsey     = 1
        forced     = None
        p          = 0.8333333333333334
        partial    = True
        remainder  = 0.666666666666667
        self       = <hypothesis.internal.conjecture.data.HypothesisProvider object at 0x4ecdf608210>
        size       = 8
        truthy     = 6
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2510: in draw_bits
    self.__check_capacity(n_bytes)
        fake_forced = False
        forced     = None
        n          = 3
        n_bytes    = 1
        self       = ConjectureData(OVERRUN, 0 bytes, frozen)
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2552: in __check_capacity
    self.mark_overrun()
        n          = 1
        self       = ConjectureData(OVERRUN, 0 bytes, frozen)
../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2577: in mark_overrun
    self.conclude_test(Status.OVERRUN)
        self       = ConjectureData(OVERRUN, 0 bytes, frozen)
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

self = ConjectureData(OVERRUN, 0 bytes, frozen), status = Status.OVERRUN, interesting_origin = None

    def conclude_test(
        self,
        status: Status,
        interesting_origin: Optional[InterestingOrigin] = None,
    ) -> NoReturn:
        assert (interesting_origin is None) or (status == Status.INTERESTING)
        self.__assert_not_frozen("conclude_test")
        self.interesting_origin = interesting_origin
        self.status = status
        self.freeze()
>       raise StopTest(self.testcounter)
E       hypothesis.errors.StopTest: 2

interesting_origin = None
self       = ConjectureData(OVERRUN, 0 bytes, frozen)
status     = Status.OVERRUN

../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/conjecture/data.py:2564: StopTest

The above exception was the direct cause of the following exception:

self = <numpy._core.tests.test_arrayprint.TestArray2String object at 0x4ecd0cf0610>

    @given(hynp.from_dtype(np.dtype("U")))
>   def test_any_text(self, text):

f          = <function given.<locals>.run_test_as_given.<locals>.wrapped_test at 0x4ecd3035aa0>
self       = <numpy._core.tests.test_arrayprint.TestArray2String object at 0x4ecd0cf0610>

numpy/_core/tests/test_arrayprint.py:504:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

errors_to_report = [(["\nYou can reproduce this example by temporarily adding @reproduce_failure('6.100.2', b'AA==') as a decorator on your test case"], Flaky('Unreliable assumption: An example which satisfied assumptions on the first run now fails it.'))]
settings = settings(database=None, deadline=None, derandomize=True, max_examples=100, phases=(Phase.explicit, Phase.reuse, Phase.....large_base_example, HealthCheck.function_scoped_fixture, HealthCheck.differing_executors], verbosity=Verbosity.normal)
target_lines = [], trailer = ''

    def _raise_to_user(errors_to_report, settings, target_lines, trailer=""):
        """Helper function for attaching notes and grouping multiple errors."""
        failing_prefix = "Falsifying example: "
        ls = []
        for fragments, err in errors_to_report:
            for note in fragments:
                add_note(err, note)
                if note.startswith(failing_prefix):
                    ls.append(note[len(failing_prefix) :])
        if current_pytest_item.value:
            current_pytest_item.value._hypothesis_failing_examples = ls

        if len(errors_to_report) == 1:
            _, the_error_hypothesis_found = errors_to_report[0]
        else:
            assert errors_to_report
            the_error_hypothesis_found = BaseExceptionGroup(
                f"Hypothesis found {len(errors_to_report)} distinct failures{trailer}.",
                [e for _, e in errors_to_report],
            )

        if settings.verbosity >= Verbosity.normal:
            for line in target_lines:
                add_note(the_error_hypothesis_found, line)
>       raise the_error_hypothesis_found
E       hypothesis.errors.Flaky: Unreliable assumption: An example which satisfied assumptions on the first run now fails it.
E
E       You can reproduce this example by temporarily adding @reproduce_failure('6.100.2', b'AA==') as a decorator on your test case

_          = ["\nYou can reproduce this example by temporarily adding @reproduce_failure('6.100.2', b'AA==') as a decorator on your test case"]
err        = Flaky('Unreliable assumption: An example which satisfied assumptions on the first run now fails it.')
errors_to_report = [(["\nYou can reproduce this example by temporarily adding @reproduce_failure('6.100.2', b'AA==') as a decorator on your test case"], Flaky('Unreliable assumption: An example which satisfied assumptions on the first run now fails it.'))]
failing_prefix = 'Falsifying example: '
fragments  = ["\nYou can reproduce this example by temporarily adding @reproduce_failure('6.100.2', b'AA==') as a decorator on your test case"]
ls         = []
note       = "\nYou can reproduce this example by temporarily adding @reproduce_failure('6.100.2', b'AA==') as a decorator on your test case"
settings   = settings(database=None, deadline=None, derandomize=True, max_examples=100, phases=(Phase.explicit, Phase.reuse, Phase.....large_base_example, HealthCheck.function_scoped_fixture, HealthCheck.differing_executors], verbosity=Verbosity.normal)
target_lines = []
the_error_hypothesis_found = Flaky('Unreliable assumption: An example which satisfied assumptions on the first run now fails it.')
trailer    = ''

../../../../../../hypothesis/hypothesis-python/src/hypothesis/core.py:1286: Flaky

If I add the reproduce_failure decorator suggested by hypothesis, I get:

../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/entropy.py:195: in deterministic_PRNG
    register_random(hypothesis.core._hypothesis_global_random)
        seed       = 0
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

r = <random.Random object at 0x2a09af82810>

        if not (PYPY or GRAALPY):  # pragma: no branch
            # PYPY and GRAALPY do not have `sys.getrefcount`
            gc.collect()
            if not gc.get_referrers(r):
                breakpoint()
                if sys.getrefcount(r) <= _PLATFORM_REF_COUNT:
                    raise ReferenceError(
                        f"`register_random` was passed `r={r}` which will be "
                        "garbage collected immediately after `register_random` creates a "
                        "weakref to it. This will prevent Hypothesis from managing this "
                        "PRNG. See the docs for `register_random` for more "
                        "details."
                    )
                else:
>                   warnings.warn(
                        "It looks like `register_random` was passed an object that could "
                        "be garbage collected immediately after `register_random` creates "
                        "a weakref to it. This will prevent Hypothesis from managing this "
                        "PRNG. See the docs for `register_random` for more details.",
                        HypothesisWarning,
                        stacklevel=2,
                    )
E                   hypothesis.errors.HypothesisWarning: It looks like `register_random` was passed an object that could be garbage collected immediately after `register_random` creates a weakref to it. This will prevent Hypothesis from managing this PRNG. See the docs for `register_random` for more details.

r          = <random.Random object at 0x2a09af82810>

../../../../../../hypothesis/hypothesis-python/src/hypothesis/internal/entropy.py:132: HypothesisWarning

This check in hypothesis uses gc.get_referrers() to avoid adding objects that would be immediately GC'd to a weak value dict.

If I insert a breakpoint right after the gc.get_referrers() call in hypothesis and check sys.getrefcount(r), I get:

(Pdb) sys.getrefcount(r)
4
(Pdb) gc.get_referrers(r)
[{'r': <random.Random object at 0x4487ef82810>}]

And r is a valid random.Random object:

(Pdb) p r
<random.Random object at 0x45c54f82810>
(Pdb) r.randbytes(10)
b'7K\xb3\xb4\xd9\x8d\x10\xb9i\xfa'

Also worth noting: It only happens if I run the full numpy test suite. If I run just this one test or all the tests in test_array_print, it passes.

CPython versions tested on:

CPython main branch

Operating systems tested on:

macOS

[Eclips4]

Hello!
Do I understand correctly, that this only happens in a free-threaded build?

[ngoldbaum]

Yes, that's correct.

[colesbury]

gc.get_referrers returns an empty list for objects that are not tracked by the GC, even if they have references. Immortalizing objects untracks them and we immortalize some functions, type objects, methods, and modules.

I'm having some difficulty understanding the problem. Is this testing spin? Or NumPy?

[ngoldbaum]

If the object is immortal, shouldn't sys.refcount return INT32_MAX instead of 4?

This is a test in numpy that uses hypothesis. The only way I've been able to trigger it is by running the full numpy test suite, which is orchestrated by spin. I'd love to have a simple reproducer for this but I was unable to come up with one.

I'm reporting this because a test in the numpy test suite that used to pass now doesn't due to a CPython change and it wasn't clear to me if this was due to a CPython bug.

It might ultimately be that the check in hypothesis is buggy or needs to be updated.

[colesbury]

If the object is immortal, shouldn't sys.refcount return INT32_MAX instead of 4?

Yes, but I'm a bit confused by what's shown in the issue: it shows a refcount of 4 and that it has one referrer.

We are probably immortalizing the type random.Random, but we shouldn't be immortalizing instances of random.Random.

The only way I've been able to trigger it is by running the full numpy test suite...

Sorry, I bet this is because we only immortalize objects once the first thread is created. So if you run the test in isolation, whatever the problematic object is might not be immortalized.

I'm reporting this because...

It's good that you reported this. To be clear, I'm just confused about what's going other than I'm pretty sure it has do with immortalization.

[ngoldbaum]

Yes, but I'm a bit confused by what's shown in the issue: it shows a refcount of 4 and that it has one referrer.

Here's the relevant code in hypothesis:

https://github.com/HypothesisWorks/hypothesis/blob/8005910d4160778c08abb974f41b52b00e19324b/hypothesis-python/src/hypothesis/internal/entropy.py#L118-L138

I inserted a breakpoint() call at line 122, inside the check for an empty gc.get_referrers() result. The only way the breakpoint can happen is if get_referrers() returns an empty list. I think the one reference you see in the debugger is from pdb's internals.

[colesbury]

Ok, okay -- I think I understand now. gc.get_referrers also will exclude references from immortal objects. In this case, the only other reference is from the module's dictionary, but that was immortalized.

In other words, the issue is not that r is immortal, it's that the module's dictionary that refers to r is immortal.

[ngoldbaum]

I opened HypothesisWorks/hypothesis#3965 to track this in hypothesis. Feel free to close this issue if you don't think this is a problem in CPython.

[ngoldbaum]

I opened HypothesisWorks/hypothesis#3976 with a fix for hypothesis. Going to go ahead and close this since CPython is working as intended.