bpo-35810: Incref heap-allocated types in PyObject_Init (GH-11661)

* Incref heap-allocated types in PyObject_Init
* Add documentation and porting notes to What's New
diff --git a/Doc/whatsnew/3.8.rst b/Doc/whatsnew/3.8.rst
index 6ab7991..0ffbcab 100644
--- a/Doc/whatsnew/3.8.rst
+++ b/Doc/whatsnew/3.8.rst
@@ -509,6 +509,12 @@
   ``1`` for objects implementing ``__index__()``.
   (Contributed by Serhiy Storchaka in :issue:`36048`.)
 
+* Heap-allocated type objects will now increase their reference count
+  in :c:func:`PyObject_Init` (and its parallel macro ``PyObject_INIT``)
+  instead of in :c:func:`PyType_GenericAlloc`. Types that modify instance
+  allocation or deallocation may need to be adjusted.
+  (Contributed by Eddie Elizondo in :issue:`35810`.)
+
 
 Deprecated
 ==========
@@ -732,6 +738,67 @@
   (Contributed by Inada Naoki in :issue:`36381`.)
 
 
+Changes in the C API
+--------------------------
+
+* Instances of heap-allocated types (such as those created with
+  :c:func:`PyType_FromSpec`) hold a reference to their type object.
+  Increasing the reference count of these type objects has been moved from
+  :c:func:`PyType_GenericAlloc` to the more low-level functions,
+  :c:func:`PyObject_Init` and :c:func:`PyObject_INIT`.
+  This makes types created through :c:func:`PyType_FromSpec` behave like
+  other classes in managed code.
+
+  Statically allocated types are not affected.
+
+  For the vast majority of cases, there should be no side effect.
+  However, types that manually increase the reference count after allocating
+  an instance (perhaps to work around the bug) may now become immortal.
+  To avoid this, these classes need to call Py_DECREF on the type object
+  during instance deallocation.
+
+  To correctly port these types into 3.8, please apply the following
+  changes:
+
+  * Remove :c:macro:`Py_INCREF` on the type object after allocating an
+    instance - if any.
+    This may happen after calling :c:func:`PyObject_New`,
+    :c:func:`PyObject_NewVar`, :c:func:`PyObject_GC_New`,
+    :c:func:`PyObject_GC_NewVar`, or any other custom allocator that uses
+    :c:func:`PyObject_Init` or :c:func:`PyObject_INIT`.
+
+    Example::
+
+        static foo_struct *
+        foo_new(PyObject *type) {
+            foo_struct *foo = PyObject_GC_New(foo_struct, (PyTypeObject *) type);
+            if (foo == NULL)
+                return NULL;
+        #if PY_VERSION_HEX < 0x03080000
+            // Workaround for Python issue 35810; no longer necessary in Python 3.8
+            PY_INCREF(type)
+        #endif
+            return foo;
+        }
+
+  * Ensure that all custom ``tp_dealloc`` functions of heap-allocated types
+    decrease the type's reference count.
+
+    Example::
+
+        static void
+        foo_dealloc(foo_struct *instance) {
+            PyObject *type = Py_TYPE(instance);
+            PyObject_GC_Del(instance);
+        #if PY_VERSION_HEX >= 0x03080000
+            // This was not needed before Python 3.8 (Python issue 35810)
+            Py_DECREF(type);
+        #endif
+        }
+
+  (Contributed by Eddie Elizondo in :issue:`35810`.)
+
+
 CPython bytecode changes
 ------------------------
 
diff --git a/Include/objimpl.h b/Include/objimpl.h
index f475ed0..2337d8a 100644
--- a/Include/objimpl.h
+++ b/Include/objimpl.h
@@ -138,6 +138,9 @@
 {
     assert(op != NULL);
     Py_TYPE(op) = typeobj;
+    if (PyType_GetFlags(typeobj) & Py_TPFLAGS_HEAPTYPE) {
+        Py_INCREF(typeobj);
+    }
     _Py_NewReference(op);
     return op;
 }
diff --git a/Misc/NEWS.d/next/C API/2019-01-23-12-38-11.bpo-35810.wpbWeb.rst b/Misc/NEWS.d/next/C API/2019-01-23-12-38-11.bpo-35810.wpbWeb.rst
new file mode 100644
index 0000000..47d25a5
--- /dev/null
+++ b/Misc/NEWS.d/next/C API/2019-01-23-12-38-11.bpo-35810.wpbWeb.rst
@@ -0,0 +1,4 @@
+Modify ``PyObject_Init`` to correctly increase the refcount of heap-
+allocated Type objects. Also fix the refcounts of the heap-allocated types
+that were either doing this manually or not decreasing the type's refcount
+in tp_dealloc
diff --git a/Modules/_curses_panel.c b/Modules/_curses_panel.c
index e7bbefd..53849e3 100644
--- a/Modules/_curses_panel.c
+++ b/Modules/_curses_panel.c
@@ -250,7 +250,10 @@
 static void
 PyCursesPanel_Dealloc(PyCursesPanelObject *po)
 {
-    PyObject *obj = (PyObject *) panel_userptr(po->pan);
+    PyObject *tp, *obj;
+
+    tp = (PyObject *) Py_TYPE(po);
+    obj = (PyObject *) panel_userptr(po->pan);
     if (obj) {
         (void)set_panel_userptr(po->pan, NULL);
         Py_DECREF(obj);
@@ -261,6 +264,7 @@
         remove_lop(po);
     }
     PyObject_DEL(po);
+    Py_DECREF(tp);
 }
 
 /* panel_above(NULL) returns the bottom panel in the stack. To get
diff --git a/Modules/_tkinter.c b/Modules/_tkinter.c
index a96924c..613a95b 100644
--- a/Modules/_tkinter.c
+++ b/Modules/_tkinter.c
@@ -617,7 +617,6 @@
     v = PyObject_New(TkappObject, (PyTypeObject *) Tkapp_Type);
     if (v == NULL)
         return NULL;
-    Py_INCREF(Tkapp_Type);
 
     v->interp = Tcl_CreateInterp();
     v->wantobjects = wantobjects;
@@ -802,7 +801,6 @@
     self = PyObject_New(PyTclObject, (PyTypeObject *) PyTclObject_Type);
     if (self == NULL)
         return NULL;
-    Py_INCREF(PyTclObject_Type);
     Tcl_IncrRefCount(arg);
     self->value = arg;
     self->string = NULL;
@@ -2722,7 +2720,6 @@
     v = PyObject_New(TkttObject, (PyTypeObject *) Tktt_Type);
     if (v == NULL)
         return NULL;
-    Py_INCREF(Tktt_Type);
 
     Py_INCREF(func);
     v->token = NULL;
diff --git a/Objects/object.c b/Objects/object.c
index b446d59..bd44aca 100644
--- a/Objects/object.c
+++ b/Objects/object.c
@@ -230,6 +230,9 @@
         return PyErr_NoMemory();
     /* Any changes should be reflected in PyObject_INIT (objimpl.h) */
     Py_TYPE(op) = tp;
+    if (PyType_GetFlags(tp) & Py_TPFLAGS_HEAPTYPE) {
+        Py_INCREF(tp);
+    }
     _Py_NewReference(op);
     return op;
 }
@@ -240,9 +243,8 @@
     if (op == NULL)
         return (PyVarObject *) PyErr_NoMemory();
     /* Any changes should be reflected in PyObject_INIT_VAR */
-    op->ob_size = size;
-    Py_TYPE(op) = tp;
-    _Py_NewReference((PyObject *)op);
+    Py_SIZE(op) = size;
+    PyObject_Init((PyObject *)op, tp);
     return op;
 }
 
diff --git a/Objects/structseq.c b/Objects/structseq.c
index cf36fa7..a5046c4 100644
--- a/Objects/structseq.c
+++ b/Objects/structseq.c
@@ -63,12 +63,17 @@
 structseq_dealloc(PyStructSequence *obj)
 {
     Py_ssize_t i, size;
+    PyTypeObject *tp;
 
+    tp = (PyTypeObject *) Py_TYPE(obj);
     size = REAL_SIZE(obj);
     for (i = 0; i < size; ++i) {
         Py_XDECREF(obj->ob_item[i]);
     }
     PyObject_GC_Del(obj);
+    if (PyType_GetFlags(tp) & Py_TPFLAGS_HEAPTYPE) {
+        Py_DECREF(tp);
+    }
 }
 
 /*[clinic input]
diff --git a/Objects/typeobject.c b/Objects/typeobject.c
index 403f3ca..4c3909c 100644
--- a/Objects/typeobject.c
+++ b/Objects/typeobject.c
@@ -987,9 +987,6 @@
 
     memset(obj, '\0', size);
 
-    if (type->tp_flags & Py_TPFLAGS_HEAPTYPE)
-        Py_INCREF(type);
-
     if (type->tp_itemsize == 0)
         (void)PyObject_INIT(obj, type);
     else