[ty] Return type inference - #29253

Summary

This PR adds return type inference as a new feature to ty. The feature is currently disabled by default. Users can activate the feature by setting analysis.return-type-inference to "always".

In a standalone function, the inferred return type is simply the union of the types of all reachable returned expressions, as shown in the image on the right. If control flow can reach the end of the function scope, we add None to the union. In a (non-final) method on a (non-final) class, we additionally union with Unknown to allow child classes to widen the intended return type. For example, imagine

class TaskBase:
    def compute(self):
        return None

class IntTask(TaskBase):
    def compute(self):
        return 42

Here, we infer a return type of None | Unknown for TaskBase.compute. Otherwise, if we inferred None, we would prohibit child classes from returning something else, which seems undesirable. Another interesting scenario is when the base class method is annotated, but the child class method is not:

class Base:
    def method(self) -> int:
        return 0

class Child(Base):
    def method(self):
        return 1

Here, we respect the base class definition and infer Child.method as returning int, not int | Unknown.

This work is based on #17371 by @mtshiba (thank you!)

There are a few notable things that are not implemented here:

• The type of the function itself currently stays unchanged, that is: we do not infer a signature with the inferred return type. Concretely: my_function() may be inferred as int, but my_function itself would still be inferred as def my_function() -> Unknown. We have existing tests with TODOs for this and I plan to tackle this in a follow up.
• We do not yet have return type inference for generator functions or async functions
• We do not attempt to solve the problem of "escaping" inner types here (see tests with TODOs)
• We do not add LSP/playground features related to this feature, but plan to do so soon (display return type hints).
• There is a limitation around functools.wraps that's present in the ecosystem report. This will hopefully be solved by [functools] Support binding wrapped methods python/typeshed#16515
• There is a limitation around NotImplemented which hasn't been resolved yet. The solution is described here.
• Fixpoint iteration currently uses Divergent as a provisional value. I did think about using the new μ-types, but that currently leaves too many questions unanswered: How would we represent an anonymous μ-type? How would the (provisional) recursive marker R interact with other types during inference (especially since those operations require "closed" recursive types, and R would still be open)?

closes astral-sh/ty#128

Test Plan

• Changed assertions in the previously reviewed & merged mdtests
• Studied the ecosystem impact and addressed many problems