1// types.GenericAlias -- used to represent e.g. list[int].
2
3#include "Python.h"
4#include "pycore_object.h"
5#include "pycore_unionobject.h"   // _Py_union_type_or, _PyGenericAlias_Check
6#include "structmember.h"         // PyMemberDef
7
8#include <stdbool.h>
9
10typedef struct {
11    PyObject_HEAD
12    PyObject *origin;
13    PyObject *args;
14    PyObject *parameters;
15    PyObject *weakreflist;
16    // Whether we're a starred type, e.g. *tuple[int].
17    bool starred;
18    vectorcallfunc vectorcall;
19} gaobject;
20
21typedef struct {
22    PyObject_HEAD
23    PyObject *obj;  /* Set to NULL when iterator is exhausted */
24} gaiterobject;
25
26static void
27ga_dealloc(PyObject *self)
28{
29    gaobject *alias = (gaobject *)self;
30
31    _PyObject_GC_UNTRACK(self);
32    if (alias->weakreflist != NULL) {
33        PyObject_ClearWeakRefs((PyObject *)alias);
34    }
35    Py_XDECREF(alias->origin);
36    Py_XDECREF(alias->args);
37    Py_XDECREF(alias->parameters);
38    Py_TYPE(self)->tp_free(self);
39}
40
41static int
42ga_traverse(PyObject *self, visitproc visit, void *arg)
43{
44    gaobject *alias = (gaobject *)self;
45    Py_VISIT(alias->origin);
46    Py_VISIT(alias->args);
47    Py_VISIT(alias->parameters);
48    return 0;
49}
50
51static int
52ga_repr_item(_PyUnicodeWriter *writer, PyObject *p)
53{
54    PyObject *qualname = NULL;
55    PyObject *module = NULL;
56    PyObject *r = NULL;
57    PyObject *tmp;
58    int err;
59
60    if (p == Py_Ellipsis) {
61        // The Ellipsis object
62        r = PyUnicode_FromString("...");
63        goto done;
64    }
65
66    if (_PyObject_LookupAttr(p, &_Py_ID(__origin__), &tmp) < 0) {
67        goto done;
68    }
69    if (tmp != NULL) {
70        Py_DECREF(tmp);
71        if (_PyObject_LookupAttr(p, &_Py_ID(__args__), &tmp) < 0) {
72            goto done;
73        }
74        if (tmp != NULL) {
75            Py_DECREF(tmp);
76            // It looks like a GenericAlias
77            goto use_repr;
78        }
79    }
80
81    if (_PyObject_LookupAttr(p, &_Py_ID(__qualname__), &qualname) < 0) {
82        goto done;
83    }
84    if (qualname == NULL) {
85        goto use_repr;
86    }
87    if (_PyObject_LookupAttr(p, &_Py_ID(__module__), &module) < 0) {
88        goto done;
89    }
90    if (module == NULL || module == Py_None) {
91        goto use_repr;
92    }
93
94    // Looks like a class
95    if (PyUnicode_Check(module) &&
96        _PyUnicode_EqualToASCIIString(module, "builtins"))
97    {
98        // builtins don't need a module name
99        r = PyObject_Str(qualname);
100        goto done;
101    }
102    else {
103        r = PyUnicode_FromFormat("%S.%S", module, qualname);
104        goto done;
105    }
106
107use_repr:
108    r = PyObject_Repr(p);
109
110done:
111    Py_XDECREF(qualname);
112    Py_XDECREF(module);
113    if (r == NULL) {
114        // error if any of the above PyObject_Repr/PyUnicode_From* fail
115        err = -1;
116    }
117    else {
118        err = _PyUnicodeWriter_WriteStr(writer, r);
119        Py_DECREF(r);
120    }
121    return err;
122}
123
124static PyObject *
125ga_repr(PyObject *self)
126{
127    gaobject *alias = (gaobject *)self;
128    Py_ssize_t len = PyTuple_GET_SIZE(alias->args);
129
130    _PyUnicodeWriter writer;
131    _PyUnicodeWriter_Init(&writer);
132
133    if (alias->starred) {
134        if (_PyUnicodeWriter_WriteASCIIString(&writer, "*", 1) < 0) {
135            goto error;
136        }
137    }
138    if (ga_repr_item(&writer, alias->origin) < 0) {
139        goto error;
140    }
141    if (_PyUnicodeWriter_WriteASCIIString(&writer, "[", 1) < 0) {
142        goto error;
143    }
144    for (Py_ssize_t i = 0; i < len; i++) {
145        if (i > 0) {
146            if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0) {
147                goto error;
148            }
149        }
150        PyObject *p = PyTuple_GET_ITEM(alias->args, i);
151        if (ga_repr_item(&writer, p) < 0) {
152            goto error;
153        }
154    }
155    if (len == 0) {
156        // for something like tuple[()] we should print a "()"
157        if (_PyUnicodeWriter_WriteASCIIString(&writer, "()", 2) < 0) {
158            goto error;
159        }
160    }
161    if (_PyUnicodeWriter_WriteASCIIString(&writer, "]", 1) < 0) {
162        goto error;
163    }
164    return _PyUnicodeWriter_Finish(&writer);
165error:
166    _PyUnicodeWriter_Dealloc(&writer);
167    return NULL;
168}
169
170// Index of item in self[:len], or -1 if not found (self is a tuple)
171static Py_ssize_t
172tuple_index(PyObject *self, Py_ssize_t len, PyObject *item)
173{
174    for (Py_ssize_t i = 0; i < len; i++) {
175        if (PyTuple_GET_ITEM(self, i) == item) {
176            return i;
177        }
178    }
179    return -1;
180}
181
182static int
183tuple_add(PyObject *self, Py_ssize_t len, PyObject *item)
184{
185    if (tuple_index(self, len, item) < 0) {
186        Py_INCREF(item);
187        PyTuple_SET_ITEM(self, len, item);
188        return 1;
189    }
190    return 0;
191}
192
193static Py_ssize_t
194tuple_extend(PyObject **dst, Py_ssize_t dstindex,
195             PyObject **src, Py_ssize_t count)
196{
197    assert(count >= 0);
198    if (_PyTuple_Resize(dst, PyTuple_GET_SIZE(*dst) + count - 1) != 0) {
199        return -1;
200    }
201    assert(dstindex + count <= PyTuple_GET_SIZE(*dst));
202    for (Py_ssize_t i = 0; i < count; ++i) {
203        PyObject *item = src[i];
204        Py_INCREF(item);
205        PyTuple_SET_ITEM(*dst, dstindex + i, item);
206    }
207    return dstindex + count;
208}
209
210PyObject *
211_Py_make_parameters(PyObject *args)
212{
213    Py_ssize_t nargs = PyTuple_GET_SIZE(args);
214    Py_ssize_t len = nargs;
215    PyObject *parameters = PyTuple_New(len);
216    if (parameters == NULL)
217        return NULL;
218    Py_ssize_t iparam = 0;
219    for (Py_ssize_t iarg = 0; iarg < nargs; iarg++) {
220        PyObject *t = PyTuple_GET_ITEM(args, iarg);
221        PyObject *subst;
222        // We don't want __parameters__ descriptor of a bare Python class.
223        if (PyType_Check(t)) {
224            continue;
225        }
226        if (_PyObject_LookupAttr(t, &_Py_ID(__typing_subst__), &subst) < 0) {
227            Py_DECREF(parameters);
228            return NULL;
229        }
230        if (subst) {
231            iparam += tuple_add(parameters, iparam, t);
232            Py_DECREF(subst);
233        }
234        else {
235            PyObject *subparams;
236            if (_PyObject_LookupAttr(t, &_Py_ID(__parameters__),
237                                     &subparams) < 0) {
238                Py_DECREF(parameters);
239                return NULL;
240            }
241            if (subparams && PyTuple_Check(subparams)) {
242                Py_ssize_t len2 = PyTuple_GET_SIZE(subparams);
243                Py_ssize_t needed = len2 - 1 - (iarg - iparam);
244                if (needed > 0) {
245                    len += needed;
246                    if (_PyTuple_Resize(&parameters, len) < 0) {
247                        Py_DECREF(subparams);
248                        Py_DECREF(parameters);
249                        return NULL;
250                    }
251                }
252                for (Py_ssize_t j = 0; j < len2; j++) {
253                    PyObject *t2 = PyTuple_GET_ITEM(subparams, j);
254                    iparam += tuple_add(parameters, iparam, t2);
255                }
256            }
257            Py_XDECREF(subparams);
258        }
259    }
260    if (iparam < len) {
261        if (_PyTuple_Resize(&parameters, iparam) < 0) {
262            Py_XDECREF(parameters);
263            return NULL;
264        }
265    }
266    return parameters;
267}
268
269/* If obj is a generic alias, substitute type variables params
270   with substitutions argitems.  For example, if obj is list[T],
271   params is (T, S), and argitems is (str, int), return list[str].
272   If obj doesn't have a __parameters__ attribute or that's not
273   a non-empty tuple, return a new reference to obj. */
274static PyObject *
275subs_tvars(PyObject *obj, PyObject *params,
276           PyObject **argitems, Py_ssize_t nargs)
277{
278    PyObject *subparams;
279    if (_PyObject_LookupAttr(obj, &_Py_ID(__parameters__), &subparams) < 0) {
280        return NULL;
281    }
282    if (subparams && PyTuple_Check(subparams) && PyTuple_GET_SIZE(subparams)) {
283        Py_ssize_t nparams = PyTuple_GET_SIZE(params);
284        Py_ssize_t nsubargs = PyTuple_GET_SIZE(subparams);
285        PyObject *subargs = PyTuple_New(nsubargs);
286        if (subargs == NULL) {
287            Py_DECREF(subparams);
288            return NULL;
289        }
290        Py_ssize_t j = 0;
291        for (Py_ssize_t i = 0; i < nsubargs; ++i) {
292            PyObject *arg = PyTuple_GET_ITEM(subparams, i);
293            Py_ssize_t iparam = tuple_index(params, nparams, arg);
294            if (iparam >= 0) {
295                PyObject *param = PyTuple_GET_ITEM(params, iparam);
296                arg = argitems[iparam];
297                if (Py_TYPE(param)->tp_iter && PyTuple_Check(arg)) {  // TypeVarTuple
298                    j = tuple_extend(&subargs, j,
299                                    &PyTuple_GET_ITEM(arg, 0),
300                                    PyTuple_GET_SIZE(arg));
301                    if (j < 0) {
302                        return NULL;
303                    }
304                    continue;
305                }
306            }
307            Py_INCREF(arg);
308            PyTuple_SET_ITEM(subargs, j, arg);
309            j++;
310        }
311        assert(j == PyTuple_GET_SIZE(subargs));
312
313        obj = PyObject_GetItem(obj, subargs);
314
315        Py_DECREF(subargs);
316    }
317    else {
318        Py_INCREF(obj);
319    }
320    Py_XDECREF(subparams);
321    return obj;
322}
323
324static int
325_is_unpacked_typevartuple(PyObject *arg)
326{
327    PyObject *tmp;
328    if (PyType_Check(arg)) { // TODO: Add test
329        return 0;
330    }
331    int res = _PyObject_LookupAttr(arg, &_Py_ID(__typing_is_unpacked_typevartuple__), &tmp);
332    if (res > 0) {
333        res = PyObject_IsTrue(tmp);
334        Py_DECREF(tmp);
335    }
336    return res;
337}
338
339static PyObject *
340_unpacked_tuple_args(PyObject *arg)
341{
342    PyObject *result;
343    assert(!PyType_Check(arg));
344    // Fast path
345    if (_PyGenericAlias_Check(arg) &&
346            ((gaobject *)arg)->starred &&
347            ((gaobject *)arg)->origin == (PyObject *)&PyTuple_Type)
348    {
349        result = ((gaobject *)arg)->args;
350        Py_INCREF(result);
351        return result;
352    }
353
354    if (_PyObject_LookupAttr(arg, &_Py_ID(__typing_unpacked_tuple_args__), &result) > 0) {
355        if (result == Py_None) {
356            Py_DECREF(result);
357            return NULL;
358        }
359        return result;
360    }
361    return NULL;
362}
363
364static PyObject *
365_unpack_args(PyObject *item)
366{
367    PyObject *newargs = PyList_New(0);
368    if (newargs == NULL) {
369        return NULL;
370    }
371    int is_tuple = PyTuple_Check(item);
372    Py_ssize_t nitems = is_tuple ? PyTuple_GET_SIZE(item) : 1;
373    PyObject **argitems = is_tuple ? &PyTuple_GET_ITEM(item, 0) : &item;
374    for (Py_ssize_t i = 0; i < nitems; i++) {
375        item = argitems[i];
376        if (!PyType_Check(item)) {
377            PyObject *subargs = _unpacked_tuple_args(item);
378            if (subargs != NULL &&
379                PyTuple_Check(subargs) &&
380                !(PyTuple_GET_SIZE(subargs) &&
381                  PyTuple_GET_ITEM(subargs, PyTuple_GET_SIZE(subargs)-1) == Py_Ellipsis))
382            {
383                if (PyList_SetSlice(newargs, PY_SSIZE_T_MAX, PY_SSIZE_T_MAX, subargs) < 0) {
384                    Py_DECREF(subargs);
385                    Py_DECREF(newargs);
386                    return NULL;
387                }
388                Py_DECREF(subargs);
389                continue;
390            }
391            Py_XDECREF(subargs);
392            if (PyErr_Occurred()) {
393                Py_DECREF(newargs);
394                return NULL;
395            }
396        }
397        if (PyList_Append(newargs, item) < 0) {
398            Py_DECREF(newargs);
399            return NULL;
400        }
401    }
402    Py_SETREF(newargs, PySequence_Tuple(newargs));
403    return newargs;
404}
405
406PyObject *
407_Py_subs_parameters(PyObject *self, PyObject *args, PyObject *parameters, PyObject *item)
408{
409    Py_ssize_t nparams = PyTuple_GET_SIZE(parameters);
410    if (nparams == 0) {
411        return PyErr_Format(PyExc_TypeError,
412                            "%R is not a generic class",
413                            self);
414    }
415    item = _unpack_args(item);
416    for (Py_ssize_t i = 0; i < nparams; i++) {
417        PyObject *param = PyTuple_GET_ITEM(parameters, i);
418        PyObject *prepare, *tmp;
419        if (_PyObject_LookupAttr(param, &_Py_ID(__typing_prepare_subst__), &prepare) < 0) {
420            Py_DECREF(item);
421            return NULL;
422        }
423        if (prepare && prepare != Py_None) {
424            if (PyTuple_Check(item)) {
425                tmp = PyObject_CallFunction(prepare, "OO", self, item);
426            }
427            else {
428                tmp = PyObject_CallFunction(prepare, "O(O)", self, item);
429            }
430            Py_DECREF(prepare);
431            Py_SETREF(item, tmp);
432            if (item == NULL) {
433                return NULL;
434            }
435        }
436    }
437    int is_tuple = PyTuple_Check(item);
438    Py_ssize_t nitems = is_tuple ? PyTuple_GET_SIZE(item) : 1;
439    PyObject **argitems = is_tuple ? &PyTuple_GET_ITEM(item, 0) : &item;
440    if (nitems != nparams) {
441        Py_DECREF(item);
442        return PyErr_Format(PyExc_TypeError,
443                            "Too %s arguments for %R; actual %zd, expected %zd",
444                            nitems > nparams ? "many" : "few",
445                            self, nitems, nparams);
446    }
447    /* Replace all type variables (specified by parameters)
448       with corresponding values specified by argitems.
449        t = list[T];          t[int]      -> newargs = [int]
450        t = dict[str, T];     t[int]      -> newargs = [str, int]
451        t = dict[T, list[S]]; t[str, int] -> newargs = [str, list[int]]
452     */
453    Py_ssize_t nargs = PyTuple_GET_SIZE(args);
454    PyObject *newargs = PyTuple_New(nargs);
455    if (newargs == NULL) {
456        Py_DECREF(item);
457        return NULL;
458    }
459    for (Py_ssize_t iarg = 0, jarg = 0; iarg < nargs; iarg++) {
460        PyObject *arg = PyTuple_GET_ITEM(args, iarg);
461        if (PyType_Check(arg)) {
462            Py_INCREF(arg);
463            PyTuple_SET_ITEM(newargs, jarg, arg);
464            jarg++;
465            continue;
466        }
467
468        int unpack = _is_unpacked_typevartuple(arg);
469        if (unpack < 0) {
470            Py_DECREF(newargs);
471            Py_DECREF(item);
472            return NULL;
473        }
474        PyObject *subst;
475        if (_PyObject_LookupAttr(arg, &_Py_ID(__typing_subst__), &subst) < 0) {
476            Py_DECREF(newargs);
477            Py_DECREF(item);
478            return NULL;
479        }
480        if (subst) {
481            Py_ssize_t iparam = tuple_index(parameters, nparams, arg);
482            assert(iparam >= 0);
483            arg = PyObject_CallOneArg(subst, argitems[iparam]);
484            Py_DECREF(subst);
485        }
486        else {
487            arg = subs_tvars(arg, parameters, argitems, nitems);
488        }
489        if (arg == NULL) {
490            Py_DECREF(newargs);
491            Py_DECREF(item);
492            return NULL;
493        }
494        if (unpack) {
495            jarg = tuple_extend(&newargs, jarg,
496                    &PyTuple_GET_ITEM(arg, 0), PyTuple_GET_SIZE(arg));
497            Py_DECREF(arg);
498            if (jarg < 0) {
499                Py_DECREF(item);
500                return NULL;
501            }
502        }
503        else {
504            PyTuple_SET_ITEM(newargs, jarg, arg);
505            jarg++;
506        }
507    }
508
509    Py_DECREF(item);
510    return newargs;
511}
512
513PyDoc_STRVAR(genericalias__doc__,
514"Represent a PEP 585 generic type\n"
515"\n"
516"E.g. for t = list[int], t.__origin__ is list and t.__args__ is (int,).");
517
518static PyObject *
519ga_getitem(PyObject *self, PyObject *item)
520{
521    gaobject *alias = (gaobject *)self;
522    // Populate __parameters__ if needed.
523    if (alias->parameters == NULL) {
524        alias->parameters = _Py_make_parameters(alias->args);
525        if (alias->parameters == NULL) {
526            return NULL;
527        }
528    }
529
530    PyObject *newargs = _Py_subs_parameters(self, alias->args, alias->parameters, item);
531    if (newargs == NULL) {
532        return NULL;
533    }
534
535    PyObject *res = Py_GenericAlias(alias->origin, newargs);
536    ((gaobject *)res)->starred = alias->starred;
537
538    Py_DECREF(newargs);
539    return res;
540}
541
542static PyMappingMethods ga_as_mapping = {
543    .mp_subscript = ga_getitem,
544};
545
546static Py_hash_t
547ga_hash(PyObject *self)
548{
549    gaobject *alias = (gaobject *)self;
550    // TODO: Hash in the hash for the origin
551    Py_hash_t h0 = PyObject_Hash(alias->origin);
552    if (h0 == -1) {
553        return -1;
554    }
555    Py_hash_t h1 = PyObject_Hash(alias->args);
556    if (h1 == -1) {
557        return -1;
558    }
559    return h0 ^ h1;
560}
561
562static inline PyObject *
563set_orig_class(PyObject *obj, PyObject *self)
564{
565    if (obj != NULL) {
566        if (PyObject_SetAttr(obj, &_Py_ID(__orig_class__), self) < 0) {
567            if (!PyErr_ExceptionMatches(PyExc_AttributeError) &&
568                !PyErr_ExceptionMatches(PyExc_TypeError))
569            {
570                Py_DECREF(obj);
571                return NULL;
572            }
573            PyErr_Clear();
574        }
575    }
576    return obj;
577}
578
579static PyObject *
580ga_call(PyObject *self, PyObject *args, PyObject *kwds)
581{
582    gaobject *alias = (gaobject *)self;
583    PyObject *obj = PyObject_Call(alias->origin, args, kwds);
584    return set_orig_class(obj, self);
585}
586
587static PyObject *
588ga_vectorcall(PyObject *self, PyObject *const *args,
589              size_t nargsf, PyObject *kwnames)
590{
591    gaobject *alias = (gaobject *) self;
592    PyObject *obj = PyVectorcall_Function(alias->origin)(alias->origin, args, nargsf, kwnames);
593    return set_orig_class(obj, self);
594}
595
596static const char* const attr_exceptions[] = {
597    "__class__",
598    "__origin__",
599    "__args__",
600    "__unpacked__",
601    "__parameters__",
602    "__typing_unpacked_tuple_args__",
603    "__mro_entries__",
604    "__reduce_ex__",  // needed so we don't look up object.__reduce_ex__
605    "__reduce__",
606    "__copy__",
607    "__deepcopy__",
608    NULL,
609};
610
611static PyObject *
612ga_getattro(PyObject *self, PyObject *name)
613{
614    gaobject *alias = (gaobject *)self;
615    if (PyUnicode_Check(name)) {
616        for (const char * const *p = attr_exceptions; ; p++) {
617            if (*p == NULL) {
618                return PyObject_GetAttr(alias->origin, name);
619            }
620            if (_PyUnicode_EqualToASCIIString(name, *p)) {
621                break;
622            }
623        }
624    }
625    return PyObject_GenericGetAttr(self, name);
626}
627
628static PyObject *
629ga_richcompare(PyObject *a, PyObject *b, int op)
630{
631    if (!_PyGenericAlias_Check(b) ||
632        (op != Py_EQ && op != Py_NE))
633    {
634        Py_RETURN_NOTIMPLEMENTED;
635    }
636
637    if (op == Py_NE) {
638        PyObject *eq = ga_richcompare(a, b, Py_EQ);
639        if (eq == NULL)
640            return NULL;
641        Py_DECREF(eq);
642        if (eq == Py_True) {
643            Py_RETURN_FALSE;
644        }
645        else {
646            Py_RETURN_TRUE;
647        }
648    }
649
650    gaobject *aa = (gaobject *)a;
651    gaobject *bb = (gaobject *)b;
652    if (aa->starred != bb->starred) {
653        Py_RETURN_FALSE;
654    }
655    int eq = PyObject_RichCompareBool(aa->origin, bb->origin, Py_EQ);
656    if (eq < 0) {
657        return NULL;
658    }
659    if (!eq) {
660        Py_RETURN_FALSE;
661    }
662    return PyObject_RichCompare(aa->args, bb->args, Py_EQ);
663}
664
665static PyObject *
666ga_mro_entries(PyObject *self, PyObject *args)
667{
668    gaobject *alias = (gaobject *)self;
669    return PyTuple_Pack(1, alias->origin);
670}
671
672static PyObject *
673ga_instancecheck(PyObject *self, PyObject *Py_UNUSED(ignored))
674{
675    PyErr_SetString(PyExc_TypeError,
676                    "isinstance() argument 2 cannot be a parameterized generic");
677    return NULL;
678}
679
680static PyObject *
681ga_subclasscheck(PyObject *self, PyObject *Py_UNUSED(ignored))
682{
683    PyErr_SetString(PyExc_TypeError,
684                    "issubclass() argument 2 cannot be a parameterized generic");
685    return NULL;
686}
687
688static PyObject *
689ga_reduce(PyObject *self, PyObject *Py_UNUSED(ignored))
690{
691    gaobject *alias = (gaobject *)self;
692    if (alias->starred) {
693        PyObject *tmp = Py_GenericAlias(alias->origin, alias->args);
694        if (tmp != NULL) {
695            Py_SETREF(tmp, PyObject_GetIter(tmp));
696        }
697        if (tmp == NULL) {
698            return NULL;
699        }
700        return Py_BuildValue("N(N)", _PyEval_GetBuiltin(&_Py_ID(next)), tmp);
701    }
702    return Py_BuildValue("O(OO)", Py_TYPE(alias),
703                         alias->origin, alias->args);
704}
705
706static PyObject *
707ga_dir(PyObject *self, PyObject *Py_UNUSED(ignored))
708{
709    gaobject *alias = (gaobject *)self;
710    PyObject *dir = PyObject_Dir(alias->origin);
711    if (dir == NULL) {
712        return NULL;
713    }
714
715    PyObject *dir_entry = NULL;
716    for (const char * const *p = attr_exceptions; ; p++) {
717        if (*p == NULL) {
718            break;
719        }
720        else {
721            dir_entry = PyUnicode_FromString(*p);
722            if (dir_entry == NULL) {
723                goto error;
724            }
725            int contains = PySequence_Contains(dir, dir_entry);
726            if (contains < 0) {
727                goto error;
728            }
729            if (contains == 0 && PyList_Append(dir, dir_entry) < 0) {
730                goto error;
731            }
732
733            Py_CLEAR(dir_entry);
734        }
735    }
736    return dir;
737
738error:
739    Py_DECREF(dir);
740    Py_XDECREF(dir_entry);
741    return NULL;
742}
743
744static PyMethodDef ga_methods[] = {
745    {"__mro_entries__", ga_mro_entries, METH_O},
746    {"__instancecheck__", ga_instancecheck, METH_O},
747    {"__subclasscheck__", ga_subclasscheck, METH_O},
748    {"__reduce__", ga_reduce, METH_NOARGS},
749    {"__dir__", ga_dir, METH_NOARGS},
750    {0}
751};
752
753static PyMemberDef ga_members[] = {
754    {"__origin__", T_OBJECT, offsetof(gaobject, origin), READONLY},
755    {"__args__", T_OBJECT, offsetof(gaobject, args), READONLY},
756    {"__unpacked__", T_BOOL, offsetof(gaobject, starred), READONLY},
757    {0}
758};
759
760static PyObject *
761ga_parameters(PyObject *self, void *unused)
762{
763    gaobject *alias = (gaobject *)self;
764    if (alias->parameters == NULL) {
765        alias->parameters = _Py_make_parameters(alias->args);
766        if (alias->parameters == NULL) {
767            return NULL;
768        }
769    }
770    Py_INCREF(alias->parameters);
771    return alias->parameters;
772}
773
774static PyObject *
775ga_unpacked_tuple_args(PyObject *self, void *unused)
776{
777    gaobject *alias = (gaobject *)self;
778    if (alias->starred && alias->origin == (PyObject *)&PyTuple_Type) {
779        Py_INCREF(alias->args);
780        return alias->args;
781    }
782    Py_RETURN_NONE;
783}
784
785static PyGetSetDef ga_properties[] = {
786    {"__parameters__", ga_parameters, (setter)NULL, "Type variables in the GenericAlias.", NULL},
787    {"__typing_unpacked_tuple_args__", ga_unpacked_tuple_args, (setter)NULL, NULL},
788    {0}
789};
790
791/* A helper function to create GenericAlias' args tuple and set its attributes.
792 * Returns 1 on success, 0 on failure.
793 */
794static inline int
795setup_ga(gaobject *alias, PyObject *origin, PyObject *args) {
796    if (!PyTuple_Check(args)) {
797        args = PyTuple_Pack(1, args);
798        if (args == NULL) {
799            return 0;
800        }
801    }
802    else {
803        Py_INCREF(args);
804    }
805
806    Py_INCREF(origin);
807    alias->origin = origin;
808    alias->args = args;
809    alias->parameters = NULL;
810    alias->weakreflist = NULL;
811
812    if (PyVectorcall_Function(origin) != NULL) {
813        alias->vectorcall = ga_vectorcall;
814    }
815    else {
816        alias->vectorcall = NULL;
817    }
818
819    return 1;
820}
821
822static PyObject *
823ga_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
824{
825    if (!_PyArg_NoKeywords("GenericAlias", kwds)) {
826        return NULL;
827    }
828    if (!_PyArg_CheckPositional("GenericAlias", PyTuple_GET_SIZE(args), 2, 2)) {
829        return NULL;
830    }
831    PyObject *origin = PyTuple_GET_ITEM(args, 0);
832    PyObject *arguments = PyTuple_GET_ITEM(args, 1);
833    gaobject *self = (gaobject *)type->tp_alloc(type, 0);
834    if (self == NULL) {
835        return NULL;
836    }
837    if (!setup_ga(self, origin, arguments)) {
838        Py_DECREF(self);
839        return NULL;
840    }
841    return (PyObject *)self;
842}
843
844static PyNumberMethods ga_as_number = {
845        .nb_or = _Py_union_type_or, // Add __or__ function
846};
847
848static PyObject *
849ga_iternext(gaiterobject *gi) {
850    if (gi->obj == NULL) {
851        PyErr_SetNone(PyExc_StopIteration);
852        return NULL;
853    }
854    gaobject *alias = (gaobject *)gi->obj;
855    PyObject *starred_alias = Py_GenericAlias(alias->origin, alias->args);
856    if (starred_alias == NULL) {
857        return NULL;
858    }
859    ((gaobject *)starred_alias)->starred = true;
860    Py_SETREF(gi->obj, NULL);
861    return starred_alias;
862}
863
864static void
865ga_iter_dealloc(gaiterobject *gi) {
866    PyObject_GC_UnTrack(gi);
867    Py_XDECREF(gi->obj);
868    PyObject_GC_Del(gi);
869}
870
871static int
872ga_iter_traverse(gaiterobject *gi, visitproc visit, void *arg)
873{
874    Py_VISIT(gi->obj);
875    return 0;
876}
877
878static int
879ga_iter_clear(PyObject *self) {
880    gaiterobject *gi = (gaiterobject *)self;
881    Py_CLEAR(gi->obj);
882    return 0;
883}
884
885static PyObject *
886ga_iter_reduce(PyObject *self, PyObject *Py_UNUSED(ignored))
887{
888    PyObject *iter = _PyEval_GetBuiltin(&_Py_ID(iter));
889    gaiterobject *gi = (gaiterobject *)self;
890
891    /* _PyEval_GetBuiltin can invoke arbitrary code,
892     * call must be before access of iterator pointers.
893     * see issue #101765 */
894
895    if (gi->obj)
896        return Py_BuildValue("N(O)", iter, gi->obj);
897    else
898        return Py_BuildValue("N(())", iter);
899}
900
901static PyMethodDef ga_iter_methods[] = {
902    {"__reduce__", ga_iter_reduce, METH_NOARGS},
903    {0}
904};
905
906// gh-91632: _Py_GenericAliasIterType is exported  to be cleared
907// in _PyTypes_FiniTypes.
908PyTypeObject _Py_GenericAliasIterType = {
909    PyVarObject_HEAD_INIT(&PyType_Type, 0)
910    .tp_name = "generic_alias_iterator",
911    .tp_basicsize = sizeof(gaiterobject),
912    .tp_iter = PyObject_SelfIter,
913    .tp_iternext = (iternextfunc)ga_iternext,
914    .tp_traverse = (traverseproc)ga_iter_traverse,
915    .tp_methods = ga_iter_methods,
916    .tp_dealloc = (destructor)ga_iter_dealloc,
917    .tp_clear = (inquiry)ga_iter_clear,
918    .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC,
919};
920
921static PyObject *
922ga_iter(PyObject *self) {
923    gaiterobject *gi = PyObject_GC_New(gaiterobject, &_Py_GenericAliasIterType);
924    if (gi == NULL) {
925        return NULL;
926    }
927    gi->obj = Py_NewRef(self);
928    PyObject_GC_Track(gi);
929    return (PyObject *)gi;
930}
931
932// TODO:
933// - argument clinic?
934// - cache?
935PyTypeObject Py_GenericAliasType = {
936    PyVarObject_HEAD_INIT(&PyType_Type, 0)
937    .tp_name = "types.GenericAlias",
938    .tp_doc = genericalias__doc__,
939    .tp_basicsize = sizeof(gaobject),
940    .tp_dealloc = ga_dealloc,
941    .tp_repr = ga_repr,
942    .tp_as_number = &ga_as_number,  // allow X | Y of GenericAlias objs
943    .tp_as_mapping = &ga_as_mapping,
944    .tp_hash = ga_hash,
945    .tp_call = ga_call,
946    .tp_getattro = ga_getattro,
947    .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_VECTORCALL,
948    .tp_traverse = ga_traverse,
949    .tp_richcompare = ga_richcompare,
950    .tp_weaklistoffset = offsetof(gaobject, weakreflist),
951    .tp_methods = ga_methods,
952    .tp_members = ga_members,
953    .tp_alloc = PyType_GenericAlloc,
954    .tp_new = ga_new,
955    .tp_free = PyObject_GC_Del,
956    .tp_getset = ga_properties,
957    .tp_iter = (getiterfunc)ga_iter,
958    .tp_vectorcall_offset = offsetof(gaobject, vectorcall),
959};
960
961PyObject *
962Py_GenericAlias(PyObject *origin, PyObject *args)
963{
964    gaobject *alias = (gaobject*) PyType_GenericAlloc(
965            (PyTypeObject *)&Py_GenericAliasType, 0);
966    if (alias == NULL) {
967        return NULL;
968    }
969    if (!setup_ga(alias, origin, args)) {
970        Py_DECREF(alias);
971        return NULL;
972    }
973    return (PyObject *)alias;
974}
975