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
8typedef struct {
9 PyObject_HEAD
10 PyObject *origin;
11 PyObject *args;
12 PyObject *parameters;
13 PyObject* weakreflist;
14} gaobject;
15
16static void
17ga_dealloc(PyObject *self)
18{
19 gaobject *alias = (gaobject *)self;
20
21 _PyObject_GC_UNTRACK(self);
22 if (alias->weakreflist != NULL) {
23 PyObject_ClearWeakRefs((PyObject *)alias);
24 }
25 Py_XDECREF(alias->origin);
26 Py_XDECREF(alias->args);
27 Py_XDECREF(alias->parameters);
28 Py_TYPE(self)->tp_free(self);
29}
30
31static int
32ga_traverse(PyObject *self, visitproc visit, void *arg)
33{
34 gaobject *alias = (gaobject *)self;
35 Py_VISIT(alias->origin);
36 Py_VISIT(alias->args);
37 Py_VISIT(alias->parameters);
38 return 0;
39}
40
41static int
42ga_repr_item(_PyUnicodeWriter *writer, PyObject *p)
43{
44 _Py_IDENTIFIER(__module__);
45 _Py_IDENTIFIER(__qualname__);
46 _Py_IDENTIFIER(__origin__);
47 _Py_IDENTIFIER(__args__);
48 PyObject *qualname = NULL;
49 PyObject *module = NULL;
50 PyObject *r = NULL;
51 PyObject *tmp;
52 int err;
53
54 if (p == Py_Ellipsis) {
55 // The Ellipsis object
56 r = PyUnicode_FromString("...");
57 goto done;
58 }
59
60 if (_PyObject_LookupAttrId(p, &PyId___origin__, &tmp) < 0) {
61 goto done;
62 }
63 if (tmp != NULL) {
64 Py_DECREF(tmp);
65 if (_PyObject_LookupAttrId(p, &PyId___args__, &tmp) < 0) {
66 goto done;
67 }
68 if (tmp != NULL) {
69 Py_DECREF(tmp);
70 // It looks like a GenericAlias
71 goto use_repr;
72 }
73 }
74
75 if (_PyObject_LookupAttrId(p, &PyId___qualname__, &qualname) < 0) {
76 goto done;
77 }
78 if (qualname == NULL) {
79 goto use_repr;
80 }
81 if (_PyObject_LookupAttrId(p, &PyId___module__, &module) < 0) {
82 goto done;
83 }
84 if (module == NULL || module == Py_None) {
85 goto use_repr;
86 }
87
88 // Looks like a class
89 if (PyUnicode_Check(module) &&
90 _PyUnicode_EqualToASCIIString(module, "builtins"))
91 {
92 // builtins don't need a module name
93 r = PyObject_Str(qualname);
94 goto done;
95 }
96 else {
97 r = PyUnicode_FromFormat("%S.%S", module, qualname);
98 goto done;
99 }
100
101use_repr:
102 r = PyObject_Repr(p);
103
104done:
105 Py_XDECREF(qualname);
106 Py_XDECREF(module);
107 if (r == NULL) {
108 // error if any of the above PyObject_Repr/PyUnicode_From* fail
109 err = -1;
110 }
111 else {
112 err = _PyUnicodeWriter_WriteStr(writer, r);
113 Py_DECREF(r);
114 }
115 return err;
116}
117
118static PyObject *
119ga_repr(PyObject *self)
120{
121 gaobject *alias = (gaobject *)self;
122 Py_ssize_t len = PyTuple_GET_SIZE(alias->args);
123
124 _PyUnicodeWriter writer;
125 _PyUnicodeWriter_Init(&writer);
126
127 if (ga_repr_item(&writer, alias->origin) < 0) {
128 goto error;
129 }
130 if (_PyUnicodeWriter_WriteASCIIString(&writer, "[", 1) < 0) {
131 goto error;
132 }
133 for (Py_ssize_t i = 0; i < len; i++) {
134 if (i > 0) {
135 if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0) {
136 goto error;
137 }
138 }
139 PyObject *p = PyTuple_GET_ITEM(alias->args, i);
140 if (ga_repr_item(&writer, p) < 0) {
141 goto error;
142 }
143 }
144 if (len == 0) {
145 // for something like tuple[()] we should print a "()"
146 if (_PyUnicodeWriter_WriteASCIIString(&writer, "()", 2) < 0) {
147 goto error;
148 }
149 }
150 if (_PyUnicodeWriter_WriteASCIIString(&writer, "]", 1) < 0) {
151 goto error;
152 }
153 return _PyUnicodeWriter_Finish(&writer);
154error:
155 _PyUnicodeWriter_Dealloc(&writer);
156 return NULL;
157}
158
159// isinstance(obj, TypeVar) without importing typing.py.
160// Returns -1 for errors.
161static int
162is_typevar(PyObject *obj)
163{
164 PyTypeObject *type = Py_TYPE(obj);
165 if (strcmp(type->tp_name, "TypeVar") != 0) {
166 return 0;
167 }
168 PyObject *module = PyObject_GetAttrString((PyObject *)type, "__module__");
169 if (module == NULL) {
170 return -1;
171 }
172 int res = PyUnicode_Check(module)
173 && _PyUnicode_EqualToASCIIString(module, "typing");
174 Py_DECREF(module);
175 return res;
176}
177
178// Index of item in self[:len], or -1 if not found (self is a tuple)
179static Py_ssize_t
180tuple_index(PyObject *self, Py_ssize_t len, PyObject *item)
181{
182 for (Py_ssize_t i = 0; i < len; i++) {
183 if (PyTuple_GET_ITEM(self, i) == item) {
184 return i;
185 }
186 }
187 return -1;
188}
189
190static int
191tuple_add(PyObject *self, Py_ssize_t len, PyObject *item)
192{
193 if (tuple_index(self, len, item) < 0) {
194 Py_INCREF(item);
195 PyTuple_SET_ITEM(self, len, item);
196 return 1;
197 }
198 return 0;
199}
200
201PyObject *
202_Py_make_parameters(PyObject *args)
203{
204 Py_ssize_t nargs = PyTuple_GET_SIZE(args);
205 Py_ssize_t len = nargs;
206 PyObject *parameters = PyTuple_New(len);
207 if (parameters == NULL)
208 return NULL;
209 Py_ssize_t iparam = 0;
210 for (Py_ssize_t iarg = 0; iarg < nargs; iarg++) {
211 PyObject *t = PyTuple_GET_ITEM(args, iarg);
212 int typevar = is_typevar(t);
213 if (typevar < 0) {
214 Py_DECREF(parameters);
215 return NULL;
216 }
217 if (typevar) {
218 iparam += tuple_add(parameters, iparam, t);
219 }
220 else {
221 _Py_IDENTIFIER(__parameters__);
222 PyObject *subparams;
223 if (_PyObject_LookupAttrId(t, &PyId___parameters__, &subparams) < 0) {
224 Py_DECREF(parameters);
225 return NULL;
226 }
227 if (subparams && PyTuple_Check(subparams)) {
228 Py_ssize_t len2 = PyTuple_GET_SIZE(subparams);
229 Py_ssize_t needed = len2 - 1 - (iarg - iparam);
230 if (needed > 0) {
231 len += needed;
232 if (_PyTuple_Resize(&parameters, len) < 0) {
233 Py_DECREF(subparams);
234 Py_DECREF(parameters);
235 return NULL;
236 }
237 }
238 for (Py_ssize_t j = 0; j < len2; j++) {
239 PyObject *t2 = PyTuple_GET_ITEM(subparams, j);
240 iparam += tuple_add(parameters, iparam, t2);
241 }
242 }
243 Py_XDECREF(subparams);
244 }
245 }
246 if (iparam < len) {
247 if (_PyTuple_Resize(&parameters, iparam) < 0) {
248 Py_XDECREF(parameters);
249 return NULL;
250 }
251 }
252 return parameters;
253}
254
255/* If obj is a generic alias, substitute type variables params
256 with substitutions argitems. For example, if obj is list[T],
257 params is (T, S), and argitems is (str, int), return list[str].
258 If obj doesn't have a __parameters__ attribute or that's not
259 a non-empty tuple, return a new reference to obj. */
260static PyObject *
261subs_tvars(PyObject *obj, PyObject *params, PyObject **argitems)
262{
263 _Py_IDENTIFIER(__parameters__);
264 PyObject *subparams;
265 if (_PyObject_LookupAttrId(obj, &PyId___parameters__, &subparams) < 0) {
266 return NULL;
267 }
268 if (subparams && PyTuple_Check(subparams) && PyTuple_GET_SIZE(subparams)) {
269 Py_ssize_t nparams = PyTuple_GET_SIZE(params);
270 Py_ssize_t nsubargs = PyTuple_GET_SIZE(subparams);
271 PyObject *subargs = PyTuple_New(nsubargs);
272 if (subargs == NULL) {
273 Py_DECREF(subparams);
274 return NULL;
275 }
276 for (Py_ssize_t i = 0; i < nsubargs; ++i) {
277 PyObject *arg = PyTuple_GET_ITEM(subparams, i);
278 Py_ssize_t iparam = tuple_index(params, nparams, arg);
279 if (iparam >= 0) {
280 arg = argitems[iparam];
281 }
282 Py_INCREF(arg);
283 PyTuple_SET_ITEM(subargs, i, arg);
284 }
285
286 obj = PyObject_GetItem(obj, subargs);
287
288 Py_DECREF(subargs);
289 }
290 else {
291 Py_INCREF(obj);
292 }
293 Py_XDECREF(subparams);
294 return obj;
295}
296
297PyObject *
298_Py_subs_parameters(PyObject *self, PyObject *args, PyObject *parameters, PyObject *item)
299{
300 Py_ssize_t nparams = PyTuple_GET_SIZE(parameters);
301 if (nparams == 0) {
302 return PyErr_Format(PyExc_TypeError,
303 "There are no type variables left in %R",
304 self);
305 }
306 int is_tuple = PyTuple_Check(item);
307 Py_ssize_t nitems = is_tuple ? PyTuple_GET_SIZE(item) : 1;
308 PyObject **argitems = is_tuple ? &PyTuple_GET_ITEM(item, 0) : &item;
309 if (nitems != nparams) {
310 return PyErr_Format(PyExc_TypeError,
311 "Too %s arguments for %R",
312 nitems > nparams ? "many" : "few",
313 self);
314 }
315 /* Replace all type variables (specified by parameters)
316 with corresponding values specified by argitems.
317 t = list[T]; t[int] -> newargs = [int]
318 t = dict[str, T]; t[int] -> newargs = [str, int]
319 t = dict[T, list[S]]; t[str, int] -> newargs = [str, list[int]]
320 */
321 Py_ssize_t nargs = PyTuple_GET_SIZE(args);
322 PyObject *newargs = PyTuple_New(nargs);
323 if (newargs == NULL) {
324 return NULL;
325 }
326 for (Py_ssize_t iarg = 0; iarg < nargs; iarg++) {
327 PyObject *arg = PyTuple_GET_ITEM(args, iarg);
328 int typevar = is_typevar(arg);
329 if (typevar < 0) {
330 Py_DECREF(newargs);
331 return NULL;
332 }
333 if (typevar) {
334 Py_ssize_t iparam = tuple_index(parameters, nparams, arg);
335 assert(iparam >= 0);
336 arg = argitems[iparam];
337 Py_INCREF(arg);
338 }
339 else {
340 arg = subs_tvars(arg, parameters, argitems);
341 if (arg == NULL) {
342 Py_DECREF(newargs);
343 return NULL;
344 }
345 }
346 PyTuple_SET_ITEM(newargs, iarg, arg);
347 }
348
349 return newargs;
350}
351
352PyDoc_STRVAR(genericalias__doc__,
353"Represent a PEP 585 generic type\n"
354"\n"
355"E.g. for t = list[int], t.__origin__ is list and t.__args__ is (int,).");
356
357static PyObject *
358ga_getitem(PyObject *self, PyObject *item)
359{
360 gaobject *alias = (gaobject *)self;
361 // Populate __parameters__ if needed.
362 if (alias->parameters == NULL) {
363 alias->parameters = _Py_make_parameters(alias->args);
364 if (alias->parameters == NULL) {
365 return NULL;
366 }
367 }
368
369 PyObject *newargs = _Py_subs_parameters(self, alias->args, alias->parameters, item);
370 if (newargs == NULL) {
371 return NULL;
372 }
373
374 PyObject *res = Py_GenericAlias(alias->origin, newargs);
375
376 Py_DECREF(newargs);
377 return res;
378}
379
380static PyMappingMethods ga_as_mapping = {
381 .mp_subscript = ga_getitem,
382};
383
384static Py_hash_t
385ga_hash(PyObject *self)
386{
387 gaobject *alias = (gaobject *)self;
388 // TODO: Hash in the hash for the origin
389 Py_hash_t h0 = PyObject_Hash(alias->origin);
390 if (h0 == -1) {
391 return -1;
392 }
393 Py_hash_t h1 = PyObject_Hash(alias->args);
394 if (h1 == -1) {
395 return -1;
396 }
397 return h0 ^ h1;
398}
399
400static PyObject *
401ga_call(PyObject *self, PyObject *args, PyObject *kwds)
402{
403 gaobject *alias = (gaobject *)self;
404 PyObject *obj = PyObject_Call(alias->origin, args, kwds);
405 if (obj != NULL) {
406 if (PyObject_SetAttrString(obj, "__orig_class__", self) < 0) {
407 if (!PyErr_ExceptionMatches(PyExc_AttributeError) &&
408 !PyErr_ExceptionMatches(PyExc_TypeError))
409 {
410 Py_DECREF(obj);
411 return NULL;
412 }
413 PyErr_Clear();
414 }
415 }
416 return obj;
417}
418
419static const char* const attr_exceptions[] = {
420 "__origin__",
421 "__args__",
422 "__parameters__",
423 "__mro_entries__",
424 "__reduce_ex__", // needed so we don't look up object.__reduce_ex__
425 "__reduce__",
426 "__copy__",
427 "__deepcopy__",
428 NULL,
429};
430
431static PyObject *
432ga_getattro(PyObject *self, PyObject *name)
433{
434 gaobject *alias = (gaobject *)self;
435 if (PyUnicode_Check(name)) {
436 for (const char * const *p = attr_exceptions; ; p++) {
437 if (*p == NULL) {
438 return PyObject_GetAttr(alias->origin, name);
439 }
440 if (_PyUnicode_EqualToASCIIString(name, *p)) {
441 break;
442 }
443 }
444 }
445 return PyObject_GenericGetAttr(self, name);
446}
447
448static PyObject *
449ga_richcompare(PyObject *a, PyObject *b, int op)
450{
451 if (!_PyGenericAlias_Check(b) ||
452 (op != Py_EQ && op != Py_NE))
453 {
454 Py_RETURN_NOTIMPLEMENTED;
455 }
456
457 if (op == Py_NE) {
458 PyObject *eq = ga_richcompare(a, b, Py_EQ);
459 if (eq == NULL)
460 return NULL;
461 Py_DECREF(eq);
462 if (eq == Py_True) {
463 Py_RETURN_FALSE;
464 }
465 else {
466 Py_RETURN_TRUE;
467 }
468 }
469
470 gaobject *aa = (gaobject *)a;
471 gaobject *bb = (gaobject *)b;
472 int eq = PyObject_RichCompareBool(aa->origin, bb->origin, Py_EQ);
473 if (eq < 0) {
474 return NULL;
475 }
476 if (!eq) {
477 Py_RETURN_FALSE;
478 }
479 return PyObject_RichCompare(aa->args, bb->args, Py_EQ);
480}
481
482static PyObject *
483ga_mro_entries(PyObject *self, PyObject *args)
484{
485 gaobject *alias = (gaobject *)self;
486 return PyTuple_Pack(1, alias->origin);
487}
488
489static PyObject *
490ga_instancecheck(PyObject *self, PyObject *Py_UNUSED(ignored))
491{
492 PyErr_SetString(PyExc_TypeError,
493 "isinstance() argument 2 cannot be a parameterized generic");
494 return NULL;
495}
496
497static PyObject *
498ga_subclasscheck(PyObject *self, PyObject *Py_UNUSED(ignored))
499{
500 PyErr_SetString(PyExc_TypeError,
501 "issubclass() argument 2 cannot be a parameterized generic");
502 return NULL;
503}
504
505static PyObject *
506ga_reduce(PyObject *self, PyObject *Py_UNUSED(ignored))
507{
508 gaobject *alias = (gaobject *)self;
509 return Py_BuildValue("O(OO)", Py_TYPE(alias),
510 alias->origin, alias->args);
511}
512
513static PyObject *
514ga_dir(PyObject *self, PyObject *Py_UNUSED(ignored))
515{
516 gaobject *alias = (gaobject *)self;
517 PyObject *dir = PyObject_Dir(alias->origin);
518 if (dir == NULL) {
519 return NULL;
520 }
521
522 PyObject *dir_entry = NULL;
523 for (const char * const *p = attr_exceptions; ; p++) {
524 if (*p == NULL) {
525 break;
526 }
527 else {
528 dir_entry = PyUnicode_FromString(*p);
529 if (dir_entry == NULL) {
530 goto error;
531 }
532 int contains = PySequence_Contains(dir, dir_entry);
533 if (contains < 0) {
534 goto error;
535 }
536 if (contains == 0 && PyList_Append(dir, dir_entry) < 0) {
537 goto error;
538 }
539
540 Py_CLEAR(dir_entry);
541 }
542 }
543 return dir;
544
545error:
546 Py_DECREF(dir);
547 Py_XDECREF(dir_entry);
548 return NULL;
549}
550
551static PyMethodDef ga_methods[] = {
552 {"__mro_entries__", ga_mro_entries, METH_O},
553 {"__instancecheck__", ga_instancecheck, METH_O},
554 {"__subclasscheck__", ga_subclasscheck, METH_O},
555 {"__reduce__", ga_reduce, METH_NOARGS},
556 {"__dir__", ga_dir, METH_NOARGS},
557 {0}
558};
559
560static PyMemberDef ga_members[] = {
561 {"__origin__", T_OBJECT, offsetof(gaobject, origin), READONLY},
562 {"__args__", T_OBJECT, offsetof(gaobject, args), READONLY},
563 {0}
564};
565
566static PyObject *
567ga_parameters(PyObject *self, void *unused)
568{
569 gaobject *alias = (gaobject *)self;
570 if (alias->parameters == NULL) {
571 alias->parameters = _Py_make_parameters(alias->args);
572 if (alias->parameters == NULL) {
573 return NULL;
574 }
575 }
576 Py_INCREF(alias->parameters);
577 return alias->parameters;
578}
579
580static PyGetSetDef ga_properties[] = {
581 {"__parameters__", ga_parameters, (setter)NULL, "Type variables in the GenericAlias.", NULL},
582 {0}
583};
584
585/* A helper function to create GenericAlias' args tuple and set its attributes.
586 * Returns 1 on success, 0 on failure.
587 */
588static inline int
589setup_ga(gaobject *alias, PyObject *origin, PyObject *args) {
590 if (!PyTuple_Check(args)) {
591 args = PyTuple_Pack(1, args);
592 if (args == NULL) {
593 return 0;
594 }
595 }
596 else {
597 Py_INCREF(args);
598 }
599
600 Py_INCREF(origin);
601 alias->origin = origin;
602 alias->args = args;
603 alias->parameters = NULL;
604 alias->weakreflist = NULL;
605 return 1;
606}
607
608static PyObject *
609ga_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
610{
611 if (!_PyArg_NoKeywords("GenericAlias", kwds)) {
612 return NULL;
613 }
614 if (!_PyArg_CheckPositional("GenericAlias", PyTuple_GET_SIZE(args), 2, 2)) {
615 return NULL;
616 }
617 PyObject *origin = PyTuple_GET_ITEM(args, 0);
618 PyObject *arguments = PyTuple_GET_ITEM(args, 1);
619 gaobject *self = (gaobject *)type->tp_alloc(type, 0);
620 if (self == NULL) {
621 return NULL;
622 }
623 if (!setup_ga(self, origin, arguments)) {
624 Py_DECREF(self);
625 return NULL;
626 }
627 return (PyObject *)self;
628}
629
630static PyNumberMethods ga_as_number = {
631 .nb_or = _Py_union_type_or, // Add __or__ function
632};
633
634// TODO:
635// - argument clinic?
636// - cache?
637PyTypeObject Py_GenericAliasType = {
638 PyVarObject_HEAD_INIT(&PyType_Type, 0)
639 .tp_name = "types.GenericAlias",
640 .tp_doc = genericalias__doc__,
641 .tp_basicsize = sizeof(gaobject),
642 .tp_dealloc = ga_dealloc,
643 .tp_repr = ga_repr,
644 .tp_as_number = &ga_as_number, // allow X | Y of GenericAlias objs
645 .tp_as_mapping = &ga_as_mapping,
646 .tp_hash = ga_hash,
647 .tp_call = ga_call,
648 .tp_getattro = ga_getattro,
649 .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_BASETYPE,
650 .tp_traverse = ga_traverse,
651 .tp_richcompare = ga_richcompare,
652 .tp_weaklistoffset = offsetof(gaobject, weakreflist),
653 .tp_methods = ga_methods,
654 .tp_members = ga_members,
655 .tp_alloc = PyType_GenericAlloc,
656 .tp_new = ga_new,
657 .tp_free = PyObject_GC_Del,
658 .tp_getset = ga_properties,
659};
660
661PyObject *
662Py_GenericAlias(PyObject *origin, PyObject *args)
663{
664 gaobject *alias = (gaobject*) PyType_GenericAlloc(
665 (PyTypeObject *)&Py_GenericAliasType, 0);
666 if (alias == NULL) {
667 return NULL;
668 }
669 if (!setup_ga(alias, origin, args)) {
670 Py_DECREF(alias);
671 return NULL;
672 }
673 return (PyObject *)alias;
674}
675