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