[mypyc] Fix decorated `__new__` in native classes (#22192)

Fixes mypyc/mypyc#1249.

A decorated method has no entry in `ClassIR.method_decls`, but the
function below the decorators is in `ClassIR.methods`. For `__new__` the
code generator used both, and the result didn't work for any caller:

- The constructor and `tp_new` called the function below the decorators
directly, so a native call skipped the decorators.
- The decorators were applied to the built-in `__new__` function that
calls `tp_new`. Setting the result on the class makes Python replace
`tp_new`, which fails the safety check of that built-in function. Every
call that isn't a native constructor call raised `TypeError:
C.__new__(C) is not safe, use object.__new__()`.
- If `__new__` takes other arguments than `__init__`, the generated C
didn't compile (`too many arguments to function 'CPyDef_C_____new__'`).
- In a class with a built-in base class, `__new__` in the type dict came
from the method table, whose flags don't match the wrapper function of
`__new__`. Instantiating the class crashed.
diff --git a/mypyc/analysis/attrdefined.py b/mypyc/analysis/attrdefined.py
index bfb9e76..394bed4 100644
--- a/mypyc/analysis/attrdefined.py
+++ b/mypyc/analysis/attrdefined.py
@@ -139,6 +139,7 @@
         or cl.children is None
         or cl.is_serializable()
         or cl.has_method("__new__")
+        or cl.has_non_native_new()
     ):
         # Give up -- we can't enforce that attributes are always defined.
         return
diff --git a/mypyc/codegen/emitclass.py b/mypyc/codegen/emitclass.py
index 2e5d601..4281876 100644
--- a/mypyc/codegen/emitclass.py
+++ b/mypyc/codegen/emitclass.py
@@ -322,6 +322,17 @@
     # Fill out slots in the type object from dunder methods.
     fields.update(generate_slots(cl, SLOT_DEFS, emitter))
 
+    if cl.has_non_native_new():
+        # Leave tp_new unset. When a decorated __new__ is set as an attribute of the
+        # class that defines it, Python sets tp_new to a function that calls __new__
+        # from the type dict, and subclasses inherit that. A tp_new of our own would
+        # add a default __new__ to the type dict, which would hide the decorated one.
+        fields.pop("tp_new", None)
+        if init_fn is not None and "tp_init" not in fields:
+            # An inherited tp_init may do nothing, since tp_new of a class without
+            # __new__ calls __init__.
+            fields["tp_init"] = generate_init_for_class(cl, init_fn, emitter)
+
     # Fill out dunder methods that live in tables hanging off the side.
     for table_name, type, slot_defs in SIDE_TABLES:
         slots = generate_slots(cl, slot_defs, emitter)
@@ -684,6 +695,10 @@
     struct_name = cl.struct_name(emitter.names)
     emitter.emit_line(f"{struct_name} *self;")
 
+    if cl.has_non_native_new() and not cl.allow_interpreted_subclasses:
+        # tp_new normally checks this, but this class doesn't have its own.
+        emit_interpreted_subclass_check(cl, emitter)
+
     prefix = cl.name_prefix(emitter.names)
     if cl.reuse_freed_instance:
         # Attempt to use a per-type free list first (a free "list" with up to one object only).
@@ -789,6 +804,31 @@
     emitter.emit_line("    return self;")
 
 
+def emit_interpreted_subclass_check(cl: ClassIR, emitter: Emitter) -> None:
+    """Emit C code to raise an exception unless the C variable "type" is the type object of cl."""
+    emitter.emit_line(f"if (type != {emitter.type_struct_name(cl)}) {{")
+    emitter.emit_line(
+        'PyErr_SetString(PyExc_TypeError, "interpreted classes cannot inherit from compiled");'
+    )
+    emitter.emit_line("return NULL;")
+    emitter.emit_line("}")
+
+
+def emit_type_object_call(cl: ClassIR, fn: FuncDecl, emitter: Emitter) -> None:
+    """Emit C code to return the result of calling the type object of cl.
+
+    The arguments are the arguments of fn, which is the constructor of cl.
+    """
+    type_arg = "(PyObject *)" + emitter.type_struct_name(cl)
+    if fn.sig.args:
+        # The constructor takes *args, **kwargs.
+        assert [arg.kind for arg in fn.sig.args] == [ARG_STAR, ARG_STAR2], fn.sig
+        args = ", ".join(REG_PREFIX + arg.name for arg in fn.sig.args)
+        emitter.emit_line(f"return PyObject_Call({type_arg}, {args});")
+    else:
+        emitter.emit_line(f"return PyObject_CallNoArgs({type_arg});")
+
+
 def generate_constructor_for_class(
     cl: ClassIR,
     fn: FuncDecl,
@@ -801,6 +841,12 @@
     emitter.emit_line(f"{native_function_header(fn, emitter)}")
     emitter.emit_line("{")
 
+    if cl.has_non_native_new():
+        # A decorated __new__ isn't called natively, so call the type object.
+        emit_type_object_call(cl, fn, emitter)
+        emitter.emit_line("}")
+        return
+
     fn_args = [REG_PREFIX + arg.name for arg in fn.sig.args]
     type_arg = "(PyObject *)" + emitter.type_struct_name(cl)
     new_args = ", ".join(fn_args)
@@ -852,7 +898,12 @@
     emitter.emit_line("static int")
     emitter.emit_line(f"{func_name}(PyObject *self, PyObject *args, PyObject *kwds)")
     emitter.emit_line("{")
-    if cl.allow_interpreted_subclasses or cl.builtin_base or cl.has_method("__new__"):
+    if (
+        cl.allow_interpreted_subclasses
+        or cl.builtin_base
+        or cl.has_method("__new__")
+        or cl.has_non_native_new()
+    ):
         emitter.emit_line(
             f"return {emitter.wrapper_function_call(init_fn.decl)}"
             "(self, args, kwds) != NULL ? 0 : -1;"
@@ -872,17 +923,15 @@
     init_fn: FuncIR | None,
     emitter: Emitter,
 ) -> None:
+    if cl.has_non_native_new():
+        # The class doesn't have its own tp_new.
+        return
     emitter.emit_line("static PyObject *")
     emitter.emit_line(f"{func_name}(PyTypeObject *type, PyObject *args, PyObject *kwds)")
     emitter.emit_line("{")
     # TODO: Check and unbox arguments
     if not cl.allow_interpreted_subclasses:
-        emitter.emit_line(f"if (type != {emitter.type_struct_name(cl)}) {{")
-        emitter.emit_line(
-            'PyErr_SetString(PyExc_TypeError, "interpreted classes cannot inherit from compiled");'
-        )
-        emitter.emit_line("return NULL;")
-        emitter.emit_line("}")
+        emit_interpreted_subclass_check(cl, emitter)
 
     type_arg = "(PyObject*)type"
     new_args = "args, kwds"
@@ -1125,7 +1174,13 @@
         emitter.emit_line(f'{{"{fn.name.removeprefix(UNDECORATED_PREFIX)}",')
         emitter.emit_line(f" (PyCFunction){PREFIX}{fn.cname(emitter.names)},")
         flags = ["METH_FASTCALL", "METH_KEYWORDS"]
-        if fn.decl.kind == FUNC_STATICMETHOD:
+        if fn.name == "__new__" and "__new__" not in cl.method_decls:
+            # A decorated __new__. Its decorators get the callable that is in the type
+            # dict. The wrapper takes the class as self, like a class method, and a
+            # class method descriptor that is called with a class as the first argument
+            # binds itself to that class.
+            flags = ["METH_VARARGS", "METH_KEYWORDS", "METH_CLASS"]
+        elif fn.decl.kind == FUNC_STATICMETHOD:
             flags.append("METH_STATIC")
         elif fn.decl.kind == FUNC_CLASSMETHOD:
             flags.append("METH_CLASS")
diff --git a/mypyc/ir/class_ir.py b/mypyc/ir/class_ir.py
index 2f679c0..ee68284 100644
--- a/mypyc/ir/class_ir.py
+++ b/mypyc/ir/class_ir.py
@@ -438,6 +438,17 @@
     def has_method_decl(self, name: str) -> bool:
         return any(name in ir.method_decls for ir in self.mro)
 
+    def has_non_native_new(self) -> bool:
+        """Are instances created by a __new__ method that isn't called natively?
+
+        A decorated __new__ is one. Like any decorated method it has no method
+        declaration, since only the decorated callable in the type dict can be called.
+        Instances are then created like instances of a Python class: tp_new looks up
+        __new__ in the type dict, and tp_init calls __init__.
+        """
+        res = self.get_method_and_class("__new__")
+        return res is not None and "__new__" not in res[1].method_decls
+
     def has_no_subclasses(self) -> bool:
         return self.children == [] and not self.allow_interpreted_subclasses
 
diff --git a/mypyc/irbuild/function.py b/mypyc/irbuild/function.py
index ef30a9c..f242034 100644
--- a/mypyc/irbuild/function.py
+++ b/mypyc/irbuild/function.py
@@ -491,6 +491,10 @@
     builder.functions.append(func_ir)
 
     if is_decorated(builder, fdef):
+        if name == "__new__" and class_ir.is_trait:
+            # A decorated __new__ is called by an inherited tp_new, and a class only
+            # inherits tp_new from its first base class.
+            builder.error('Decorated "__new__" not supported in traits', fdef.line)
         # Obtain the function name in order to construct the name of the helper function.
         _, _, name = fdef.fullname.rpartition(".")
         # Get the callable representing the non-decorated method directly from the type
diff --git a/mypyc/irbuild/prepare.py b/mypyc/irbuild/prepare.py
index 0752df9..318f94a 100644
--- a/mypyc/irbuild/prepare.py
+++ b/mypyc/irbuild/prepare.py
@@ -132,6 +132,14 @@
                     module.path, module.fullname, cdef, errors, mapper, options
                 )
 
+    # Set up constructors. This needs the method declarations of all classes. A class
+    # can be prepared before its base class, since the modules of a compilation group
+    # are prepared in name order.
+    for module, cdef in classes:
+        class_ir = mapper.type_to_ir[cdef.info]
+        if class_ir.is_ext_class:
+            prepare_init_method(cdef, class_ir, module.fullname, mapper)
+
     # Validate cross-class properties after all ClassIR flags are populated.
     for module, cdef in classes:
         with catch_errors(module.path, cdef.line):
@@ -640,7 +648,6 @@
     ir.base_mro = base_mro
 
     prepare_methods_and_attributes(cdef, ir, path, module_name, errors, mapper, options)
-    prepare_init_method(cdef, ir, module_name, mapper)
 
     for base in bases:
         if base.children is not None:
@@ -802,6 +809,23 @@
     return True
 
 
+def has_non_native_new(cdef: ClassDef, mapper: Mapper) -> bool:
+    """Are instances of a class created by a __new__ method that isn't called natively?
+
+    This is ClassIR.has_non_native_new() for use before the methods have been built.
+    The methods of all classes in the MRO must have been declared.
+    """
+    for info in cdef.info.mro:
+        class_ir = mapper.type_to_ir.get(info)
+        symbol = info.names.get("__new__")
+        if class_ir is None or not class_ir.is_ext_class or symbol is None:
+            continue
+        if isinstance(symbol.node, (FuncDef, Decorator, OverloadedFuncDef)):
+            # A decorated method has no method declaration.
+            return "__new__" not in class_ir.method_decls
+    return False
+
+
 def prepare_init_method(cdef: ClassDef, ir: ClassIR, module_name: str, mapper: Mapper) -> None:
     # Set up a constructor decl
     init_node = cdef.info["__init__"].node
@@ -822,6 +846,9 @@
         if isinstance(new_node, FuncDef):
             new_sig = mapper.fdef_to_sig(new_node, True)
             args_match = check_matching_args(init_sig, new_sig)
+        if has_non_native_new(cdef, mapper):
+            # The constructor calls the type object with *args, **kwargs.
+            args_match = False
 
         defining_ir = mapper.type_to_ir.get(init_node.info)
         # If there is a nontrivial __init__ that wasn't defined in an
diff --git a/mypyc/test-data/irbuild-classes.test b/mypyc/test-data/irbuild-classes.test
index 6acfbd0..1d2343c 100644
--- a/mypyc/test-data/irbuild-classes.test
+++ b/mypyc/test-data/irbuild-classes.test
@@ -2409,9 +2409,12 @@
 
 [case testUnsupportedDunderNew]
 from __future__ import annotations
-from mypy_extensions import mypyc_attr
+from mypy_extensions import mypyc_attr, trait
 from typing import Any
 
+def decorator(f: Any) -> Any:
+    return f
+
 @mypyc_attr(native_class=False)
 class NonNative:
     def __new__(cls) -> NonNative:
@@ -2458,6 +2461,175 @@
     def __new__(cls):
         return object.__new__(cls, 1)  # E: "object.__new__()" supported only with 1 argument, got 2
 
+@trait
+class DecoratedInTrait:
+    @decorator
+    def __new__(cls) -> Any:  # E: Decorated "__new__" not supported in traits
+        return super().__new__(cls)
+
+[case testDecoratedDunderNew]
+from typing import Any, Callable, TypeVar
+
+F = TypeVar("F", bound=Callable[..., Any])
+
+def deco(f: F) -> F:
+    return f
+
+class A:
+    @deco
+    def __new__(cls, x: int) -> Any:
+        return super().__new__(cls)
+
+    def __init__(self, x: int) -> None:
+        pass
+
+class B(A):
+    pass
+
+class C:
+    def __new__(cls, x: int) -> Any:
+        return super().__new__(cls)
+
+    def __init__(self, x: int) -> None:
+        pass
+
+def f() -> None:
+    A(1)
+    B(2)
+    C(3)
+[out]
+def deco(f):
+    f :: object
+L0:
+    return f
+def A.__new__(cls, x):
+    cls :: object
+    x :: int
+    r0 :: object
+    r1 :: __main__.A
+L0:
+    r0 = CPy_SetupObject(cls)
+    r1 = cast(__main__.A, r0)
+    return r1
+def A.__init__(self, x):
+    self :: __main__.A
+    x :: int
+L0:
+    return 1
+def C.__new__(cls, x):
+    cls :: object
+    x :: int
+    r0 :: __main__.C
+L0:
+    r0 = __mypyc__C_setup(cls)
+    return r0
+def C.__init__(self, x):
+    self :: __main__.C
+    x :: int
+L0:
+    return 1
+def f():
+    r0 :: object
+    r1 :: tuple
+    r2 :: dict
+    r3 :: __main__.A
+    r4 :: object
+    r5 :: tuple
+    r6 :: dict
+    r7 :: __main__.B
+    r8 :: __main__.C
+L0:
+    r0 = object 1
+    r1 = PyTuple_Pack(1, r0)
+    r2 = PyDict_New()
+    r3 = A(r1, r2)
+    r4 = object 2
+    r5 = PyTuple_Pack(1, r4)
+    r6 = PyDict_New()
+    r7 = B(r5, r6)
+    r8 = C(6)
+    return 1
+
+[case testDunderNewInBaseClassPreparedAfterSubclass]
+from typing import Any, Callable, TypeVar
+
+F = TypeVar("F", bound=Callable[..., Any])
+
+def deco(f: F) -> F:
+    return f
+
+# Classes are prepared in definition order, so these two are prepared before
+# their base classes. This also happens if the base class is in another module
+# of the compilation group that has a later name.
+class A(StaticBase):
+    def __init__(self, x: int) -> None:
+        pass
+
+class B(DecoratedBase):
+    def __init__(self, x: int) -> None:
+        pass
+
+class StaticBase:
+    # mypy removes @staticmethod from the decorators, so this is a native method.
+    @staticmethod
+    def __new__(cls, x: int) -> Any:
+        return super().__new__(cls)
+
+class DecoratedBase:
+    @deco
+    def __new__(cls, x: int) -> Any:
+        return super().__new__(cls)
+
+def f() -> None:
+    A(1)
+    B(2)
+[out]
+def deco(f):
+    f :: object
+L0:
+    return f
+def A.__init__(self, x):
+    self :: __main__.A
+    x :: int
+L0:
+    return 1
+def B.__init__(self, x):
+    self :: __main__.B
+    x :: int
+L0:
+    return 1
+def StaticBase.__new__(cls, x):
+    cls :: object
+    x :: int
+    r0 :: object
+    r1 :: __main__.StaticBase
+L0:
+    r0 = CPy_SetupObject(cls)
+    r1 = cast(__main__.StaticBase, r0)
+    return r1
+def DecoratedBase.__new__(cls, x):
+    cls :: object
+    x :: int
+    r0 :: object
+    r1 :: __main__.DecoratedBase
+L0:
+    r0 = CPy_SetupObject(cls)
+    r1 = cast(__main__.DecoratedBase, r0)
+    return r1
+def f():
+    r0 :: __main__.A
+    r1 :: object
+    r2 :: tuple
+    r3 :: dict
+    r4 :: __main__.B
+L0:
+    r0 = A(2)
+    r1 = object 2
+    r2 = PyTuple_Pack(1, r1)
+    r3 = PyDict_New()
+    r4 = B(r2, r3)
+    return 1
+
 [case testClassWithFreeList]
 from mypy_extensions import mypyc_attr, trait
 
diff --git a/mypyc/test-data/run-classes.test b/mypyc/test-data/run-classes.test
index 160245c..ebeb04c 100644
--- a/mypyc/test-data/run-classes.test
+++ b/mypyc/test-data/run-classes.test
@@ -5480,6 +5480,472 @@
     with assertRaises(TypeError, "str.__new__(int): int is not a subtype of str"):
         k = TestStrInt.factory()
 
+[case testDecoratedDunderNew]
+from __future__ import annotations
+
+from typing import Any, Callable, TypeVar, overload
+
+from mypy_extensions import mypyc_attr
+from testutil import assertRaises
+from typing_extensions import Self
+
+from m import check_interpreted_subclasses
+
+F = TypeVar("F", bound=Callable[..., Any])
+
+log: list[str] = []
+
+def take() -> list[str]:
+    result = list(log)
+    log.clear()
+    return result
+
+def logged(f: F) -> F:
+    def wrapper(cls: Any, *args: Any, **kwargs: Any) -> Any:
+        log.append(f"before {cls.__name__} {args} {kwargs}")
+        obj = f(cls, *args, **kwargs)
+        log.append("after")
+        return obj
+    return wrapper  # type: ignore[return-value]
+
+def tagged(tag: str) -> Callable[[F], F]:
+    def deco(f: F) -> F:
+        def wrapper(*args: Any) -> Any:
+            log.append(tag)
+            return f(*args)
+        return wrapper  # type: ignore[return-value]
+    return deco
+
+def unchanged(f: F) -> F:
+    return f
+
+def non_negative(f: F) -> F:
+    def wrapper(cls: Any, x: int) -> Any:
+        if x < 0:
+            raise ValueError("negative")
+        return f(cls, x)
+    return wrapper  # type: ignore[return-value]
+
+class Point:
+    @logged
+    def __new__(cls, x: int, y: int = 0) -> Self:
+        log.append(f"new {x} {y}")
+        return super().__new__(cls)
+
+    def __init__(self, x: int, y: int = 0) -> None:
+        log.append(f"init {x} {y}")
+        self.x = x
+        self.y = y
+        self.label = f"{x},{y}"
+
+class PointChild(Point):
+    pass
+
+class PointChildWithInit(Point):
+    def __init__(self, x: int, y: int = 0) -> None:
+        super().__init__(x + 10, y + 10)
+        log.append("child init")
+
+def test_new_and_init() -> None:
+    p = Point(1)
+    assert take() == ["before Point (1,) {}", "new 1 0", "after", "init 1 0"]
+    assert (p.x, p.y) == (1, 0)
+    p = Point(2, y=3)
+    assert take() == ["before Point (2,) {'y': 3}", "new 2 3", "after", "init 2 3"]
+    assert (p.x, p.y) == (2, 3)
+
+    # Use Any to get non-native semantics
+    cls: Any = Point
+    p = cls(4, 5)
+    assert take() == ["before Point (4, 5) {}", "new 4 5", "after", "init 4 5"]
+    assert (p.x, p.y) == (4, 5)
+    with assertRaises(TypeError):
+        cls()
+    assert take() == ["before Point () {}"]
+
+def test_inherited_new() -> None:
+    c = PointChild(1, 2)
+    assert take() == ["before PointChild (1, 2) {}", "new 1 2", "after", "init 1 2"]
+    assert type(c) is PointChild
+    assert (c.x, c.y) == (1, 2)
+    d = PointChildWithInit(1, 2)
+    assert take() == [
+        "before PointChildWithInit (1, 2) {}",
+        "new 1 2",
+        "after",
+        "init 11 12",
+        "child init",
+    ]
+    assert type(d) is PointChildWithInit
+    assert (d.x, d.y) == (11, 12)
+
+    cls: Any = PointChild
+    c = cls(3)
+    assert take() == ["before PointChild (3,) {}", "new 3 0", "after", "init 3 0"]
+    assert type(c) is PointChild
+    cls = PointChildWithInit
+    d = cls(3)
+    assert take() == [
+        "before PointChildWithInit (3,) {}",
+        "new 3 0",
+        "after",
+        "init 13 10",
+        "child init",
+    ]
+    assert d.x == 13
+
+def test_explicit_call_does_not_call_init() -> None:
+    p = Point.__new__(Point, 1)
+    assert take() == ["before Point (1,) {}", "new 1 0", "after"]
+    assert type(p) is Point
+    with assertRaises(AttributeError):
+        p.x
+    with assertRaises(AttributeError):
+        p.label
+    c = Point.__new__(PointChild, 2)
+    assert take() == ["before PointChild (2,) {}", "new 2 0", "after"]
+    assert type(c) is PointChild
+
+    cls: Any = Point
+    p = cls.__new__(cls, 3, y=4)
+    assert take() == ["before Point (3,) {'y': 4}", "new 3 4", "after"]
+    with assertRaises(AttributeError):
+        p.label
+    assert type(cls.__dict__["__new__"]) is staticmethod
+
+class Root:
+    def __init__(self, x: int) -> None:
+        log.append(f"init {x}")
+        self.x = x
+
+class Mid(Root):
+    @logged
+    def __new__(cls, x: int) -> Self:
+        log.append("new")
+        return super().__new__(cls)
+
+class Leaf(Mid):
+    pass
+
+def test_init_from_base_class() -> None:
+    # Root doesn't define __new__, so its tp_new calls __init__, and its tp_init
+    # does nothing. The subclasses can't use that tp_init.
+    for cls in Mid, Leaf:
+        any_cls: Any = cls
+        obj = any_cls(1)
+        assert take() == [f"before {cls.__name__} (1,) {{}}", "new", "after", "init 1"]
+        assert obj.x == 1
+    m = Mid(2)
+    assert take() == ["before Mid (2,) {}", "new", "after", "init 2"]
+    assert m.x == 2
+    l = Leaf(3)
+    assert take() == ["before Leaf (3,) {}", "new", "after", "init 3"]
+    assert l.x == 3
+    r = Root(4)
+    assert take() == ["init 4"]
+    assert r.x == 4
+    any_cls = Root
+    r = any_cls(5)
+    assert take() == ["init 5"]
+
+class TwoDecorators:
+    @tagged("outer")
+    @tagged("inner")
+    def __new__(cls) -> Self:
+        log.append("new")
+        return super().__new__(cls)
+
+class Unchanged:
+    @unchanged
+    def __new__(cls) -> Self:
+        log.append("new")
+        return super().__new__(cls)
+
+def test_other_decorators() -> None:
+    TwoDecorators()
+    assert take() == ["outer", "inner", "new"]
+    Unchanged()
+    assert take() == ["new"]
+    cls: Any = TwoDecorators
+    cls()
+    assert take() == ["outer", "inner", "new"]
+    cls = Unchanged
+    cls()
+    cls.__new__(cls)
+    assert take() == ["new", "new"]
+
+class Overloaded:
+    @overload
+    def __new__(cls, x: int) -> Overloaded: ...
+    @overload
+    def __new__(cls, x: str) -> Overloaded: ...
+    @logged
+    def __new__(cls, x: object) -> Overloaded:
+        log.append(f"new {x}")
+        return super().__new__(cls)
+
+    def __init__(self, x: object) -> None:
+        self.x = x
+
+def test_overloaded_new_with_decorated_implementation() -> None:
+    o = Overloaded(1)
+    assert take() == ["before Overloaded (1,) {}", "new 1", "after"]
+    assert o.x == 1
+    cls: Any = Overloaded
+    o = cls("s")
+    assert take() == ["before Overloaded ('s',) {}", "new s", "after"]
+    assert o.x == "s"
+
+class NotAlwaysInstance:
+    @logged
+    def __new__(cls, x: int) -> Any:
+        if x == 0:
+            return "zero"
+        return super().__new__(cls)
+
+    def __init__(self, x: int) -> None:
+        log.append("init")
+        self.x = x
+
+def test_new_returns_instance_of_other_class() -> None:
+    a: Any = NotAlwaysInstance(0)
+    assert a == "zero"
+    assert take() == ["before NotAlwaysInstance (0,) {}", "after"]
+    b: Any = NotAlwaysInstance(1)
+    assert b.x == 1
+    assert take() == ["before NotAlwaysInstance (1,) {}", "after", "init"]
+    cls: Any = NotAlwaysInstance
+    assert cls(0) == "zero"
+    assert take() == ["before NotAlwaysInstance (0,) {}", "after"]
+
+class Checked:
+    @non_negative
+    def __new__(cls, x: int) -> Self:
+        if x == 0:
+            raise RuntimeError("zero")
+        return super().__new__(cls)
+
+    def __init__(self, x: int) -> None:
+        if x == 1:
+            raise KeyError("one")
+        self.x = x
+
+def test_exceptions() -> None:
+    any_cls: Any = Checked
+    for cls in Checked, any_cls:
+        with assertRaises(ValueError, "negative"):
+            cls(-1)
+        with assertRaises(RuntimeError, "zero"):
+            cls(0)
+        with assertRaises(KeyError, "one"):
+            cls(1)
+        assert cls(2).x == 2
+
+@mypyc_attr(allow_interpreted_subclasses=True)
+class Open:
+    @logged
+    def __new__(cls, x: int) -> Self:
+        return super().__new__(cls)
+
+    def __init__(self, x: int) -> None:
+        self.x = x
+
+    def value(self) -> int:
+        return self.x
+
+def call_value(o: Open) -> int:
+    return o.value()
+
+def test_interpreted_subclasses() -> None:
+    o = Open(1)
+    assert take() == ["before Open (1,) {}", "after"]
+    assert call_value(o) == 1
+    check_interpreted_subclasses()
+
+[file m.py]
+from testutil import assertRaises
+
+def check_interpreted_subclasses() -> None:
+    from native import Leaf, Open, Point, PointChild, call_value, take
+
+    class OpenChild(Open):
+        def value(self) -> int:
+            return self.x + 100
+
+    o = OpenChild(1)
+    assert take() == ["before OpenChild (1,) {}", "after"]
+    assert o.x == 1
+    assert call_value(o) == 101
+
+    class OpenChildWithNew(Open):
+        y: int
+
+        def __new__(cls, x):
+            obj = super().__new__(cls, x + 1)
+            obj.y = 5
+            return obj
+
+        def __init__(self, x):
+            super().__init__(x + 2)
+
+    o2 = OpenChildWithNew(1)
+    assert take() == ["before OpenChildWithNew (2,) {}", "after"]
+    assert (o2.x, o2.y) == (3, 5)
+    assert call_value(o2) == 3
+
+    # The other classes don't allow interpreted subclasses.
+    for base in Point, PointChild, Leaf:
+        class Child(base):  # type: ignore[misc, valid-type]
+            pass
+
+        with assertRaises(TypeError, "interpreted classes cannot inherit from compiled"):
+            Child(1)
+        take()
+
+        class ChildWithNew(base):  # type: ignore[misc, valid-type]
+            def __new__(cls, x):
+                return super().__new__(cls, x)
+
+        with assertRaises(TypeError, "interpreted classes cannot inherit from compiled"):
+            ChildWithNew(1)
+        take()
+
+[typing fixtures/typing-full.pyi]
+
+[case testDecoratedDunderNewWithOtherArgumentsThanInit]
+from __future__ import annotations
+
+import functools
+from typing import Any, Callable, TypeVar
+
+from typing_extensions import Self
+
+F = TypeVar("F", bound=Callable[..., Any])
+
+log: list[str] = []
+
+def take() -> list[str]:
+    result = list(log)
+    log.clear()
+    return result
+
+def logged(f: F) -> F:
+    def wrapper(cls: Any, *args: Any, **kwargs: Any) -> Any:
+        log.append(f"before {cls.__name__} {args} {kwargs}")
+        obj = f(cls, *args, **kwargs)
+        log.append("after")
+        return obj
+    return wrapper  # type: ignore[return-value]
+
+class NoInit:
+    x: int
+
+    @logged
+    def __new__(cls, x: int) -> Self:
+        obj = super().__new__(cls)
+        obj.x = x + 1
+        return obj
+
+def test_no_init() -> None:
+    n = NoInit(1)
+    assert take() == ["before NoInit (1,) {}", "after"]
+    assert n.x == 2
+    cls: Any = NoInit
+    n = cls(x=2)
+    assert take() == ["before NoInit () {'x': 2}", "after"]
+    assert n.x == 3
+
+class AnyArguments:
+    @logged
+    def __new__(cls, *args: Any, **kwargs: Any) -> Self:
+        log.append("new")
+        return super().__new__(cls)
+
+    def __init__(self, x: int, y: int = 0) -> None:
+        log.append(f"init {x} {y}")
+        self.x = x
+        self.y = y
+
+class AnyArgumentsChild(AnyArguments):
+    def __init__(self, x: int) -> None:
+        super().__init__(x, 10)
+
+def test_any_arguments() -> None:
+    a = AnyArguments(1, y=2)
+    assert take() == ["before AnyArguments (1,) {'y': 2}", "new", "after", "init 1 2"]
+    assert (a.x, a.y) == (1, 2)
+    c = AnyArgumentsChild(3)
+    assert take() == ["before AnyArgumentsChild (3,) {}", "new", "after", "init 3 10"]
+    assert (c.x, c.y) == (3, 10)
+    cls: Any = AnyArguments
+    a = cls(4)
+    assert take() == ["before AnyArguments (4,) {}", "new", "after", "init 4 0"]
+    assert (a.x, a.y) == (4, 0)
+
+class Interned:
+    name: str
+
+    @functools.cache  # type: ignore[misc]
+    def __new__(cls, name: str) -> Self:
+        log.append(f"new {name}")
+        obj = super().__new__(cls)
+        obj.name = name
+        return obj
+
+def test_cache() -> None:
+    a = Interned("a")
+    b = Interned("b")
+    assert Interned("a") is a
+    cls: Any = Interned
+    assert cls("b") is b
+    assert take() == ["new a", "new b"]
+    assert (a.name, b.name) == ("a", "b")
+    assert cls.__new__.cache_info().hits == 2
+
+[typing fixtures/typing-full.pyi]
+
+[case testDecoratedDunderNewWithBuiltInBaseClass]
+from typing import Any, Callable, TypeVar
+
+F = TypeVar("F", bound=Callable[..., Any])
+
+log: list[str] = []
+
+def logged(f: F) -> F:
+    def wrapper(cls: Any, *args: Any) -> Any:
+        log.append(f"before {cls.__name__} {args}")
+        obj = f(cls, *args)
+        log.append("after")
+        return obj
+    return wrapper  # type: ignore[return-value]
+
+class Table(dict):  # type: ignore[type-arg]
+    @logged
+    def __new__(cls, *args: Any) -> Any:
+        log.append("new")
+        return dict.__new__(cls)
+
+class Error(Exception):
+    @logged
+    def __new__(cls, *args: Any) -> Any:
+        log.append("new")
+        return Exception.__new__(cls, *args)
+
+    def __init__(self, x: int) -> None:
+        log.append("init")
+        super().__init__(str(x + 1))
+
+def test_built_in_base_class() -> None:
+    t = Table({"a": 1})
+    assert log == ["before Table ({'a': 1},)", "new", "after"]
+    assert type(t) is Table
+    assert t == {"a": 1}
+    log.clear()
+    e = Error(1)
+    assert log == ["before Error (1,)", "new", "after", "init"]
+    assert type(e) is Error
+    assert str(e) == "2"
+
 [case testPerTypeFreeList]
 from __future__ import annotations
 
diff --git a/mypyc/test-data/run-multimodule.test b/mypyc/test-data/run-multimodule.test
index 77c89d1..74fcf2e 100644
--- a/mypyc/test-data/run-multimodule.test
+++ b/mypyc/test-data/run-multimodule.test
@@ -2239,6 +2239,131 @@
 empty
 hello
 
+[case testIncrementalCrossGroupDecoratedDunderNew]
+# A class with a decorated __new__ inherits tp_new, and so does a subclass that
+# inherits the __new__. When only the module of the subclass is recompiled, the
+# base class is loaded from the incremental cache, which doesn't have the
+# decorators.
+from typing import Any
+
+from other_a import Child, ChildWithInit
+from other_b import Base, log
+
+def take() -> list[str]:
+    result = list(log)
+    log.clear()
+    return result
+
+def test() -> None:
+    log.clear()
+    any_base: Any = Base
+    for base in Base, any_base:
+        b = base(1)
+        assert take() == ["before Base (1,)", "new", "after", "Root 1"]
+        assert b.x == 1
+    # Use Any to get non-native semantics
+    any_child: Any = Child
+    for child in Child, any_child:
+        c = child(2)
+        assert take() == ["before Child (2,)", "new", "after", "Root 2"]
+        assert type(c) is Child
+        assert c.x == 2
+    any_child = ChildWithInit
+    for child_with_init in ChildWithInit, any_child:
+        d = child_with_init(3)
+        assert take() == ["before ChildWithInit (3,)", "new", "after", "Root 4", "ChildWithInit"]
+        assert d.x == 4
+    e = Base.__new__(Child, 4)
+    assert take() == ["before Child (4,)", "new", "after"]
+    assert type(e) is Child
+
+[file other_a.py]
+from other_b import Base, log
+
+class Child(Base):
+    pass
+
+class ChildWithInit(Base):
+    def __init__(self, x: int) -> None:
+        super().__init__(x + 1)
+        log.append("ChildWithInit")
+
+[file other_a.py.2]
+from other_b import Base, log
+
+class Child(Base):
+    pass
+
+class ChildWithInit(Base):
+    def __init__(self, x: int) -> None:
+        super().__init__(x + 1)
+        log.append("ChildWithInit")
+
+def _force_recompile() -> int:
+    return 1
+
+[file other_b.py]
+from typing import Any, Callable, TypeVar
+
+F = TypeVar("F", bound=Callable[..., Any])
+
+log: list[str] = []
+
+def logged(f: F) -> F:
+    def wrapper(cls: Any, *args: Any) -> Any:
+        log.append(f"before {cls.__name__} {args}")
+        obj = f(cls, *args)
+        log.append("after")
+        return obj
+    return wrapper  # type: ignore[return-value]
+
+class Root:
+    def __init__(self, x: int) -> None:
+        log.append(f"Root {x}")
+        self.x = x
+
+class Base(Root):
+    @logged
+    def __new__(cls, x: int) -> Any:
+        log.append("new")
+        return super().__new__(cls)
+
+[file driver.py]
+from native import test
+test()
+
+[case testDecoratedNewInBaseClassPreparedAfterSubclass]
+# The modules of a compilation group are prepared in name order, so Child is
+# prepared before Base. mypy removes @staticmethod from the decorators of
+# __new__, so it's a native method, and the constructor of Child calls it and
+# __init__ natively.
+from other import Base
+
+class Child(Base):
+    def __init__(self) -> None:
+        raise ValueError("expected init failure")
+
+def construct() -> Child:
+    return Child()
+
+[file other.py]
+from typing import Any
+
+class Base:
+    @staticmethod
+    def __new__(cls) -> Any:
+        return super().__new__(cls)
+
+    def __init__(self) -> None:
+        pass
+
+[file driver.py]
+from native import construct
+from testutil import assertRaises
+
+with assertRaises(ValueError):
+    construct()
+
 [case testIncrementalCrossModuleInheritedAttrDefaultsWithOverride]
 # Regression: same shape as testIncrementalCrossModuleInheritedAttrDefaults,
 # but the subclass adds an attribute of its own, so generate_attr_defaults_init