I could be missing something, but it looks like PyStructSequence_NewType is guaranteed broken. Specifically, it allocates the memory with PyType_GenericAlloc (use PyType_Type as the base), and PyType declares itself to have garbage collected instances, so the memory is allocated with _PyObject_GC_Malloc and added to GC tracking just before PyType_GenericAlloc returns.

Problem is, PyStructSequence_Init2 copies from a template struct which sets Py_TPFLAGS_DEFAULT. So even though the new struct sequence is GC allocated and managed, it doesn't set Py_TPFLAGS_HEAPTYPE, which means when GC tries to traverse it, type's type_traverse errors out with:

Fatal Python error: type_traverse() called for non-heap type 'NameOfStructSequence'

It's possible I'm missing something here, so I've attached simple test code for others to confirm (it omits most error checking for simplicity/readability).

Just compile the extension module, then run (with the module in the working directory):

    python -c "import testnewtype; Foo = testnewtype.makeseq('Foo', ['x', 'y'])"

There is a commented out line in the test code that explicitly sets the HEAPTYPE flag after type construction (no idea if that's supposed to be supported), and uncommenting it seems to fix the crash (though again, if retroactively flagging as HEAPTYPE is unsupported, something else may break here).

I can't find any actual use of PyStructSequence_NewType in the CPython code base, which probably explains why this hasn't been seen; odds are, most extensions using struct sequences are using Init, not NewType, and I only ran into this because I was experimenting with a struct sequence based replacement for collections.namedtuple (to end the start up time objections to using namedtuple in the built-in modules, e.g. #28638).