1 /* Implementation helper: a struct that looks like a tuple.
2 See timemodule and posixmodule for example uses.
3
4 The structseq helper is considered an internal CPython implementation
5 detail. Docs for modules using structseqs should call them
6 "named tuples" (be sure to include a space between the two
7 words and add a link back to the term in Docs/glossary.rst).
8 */
9
10 #include "Python.h"
11 #include "pycore_tuple.h" // _PyTuple_FromArray()
12 #include "pycore_object.h" // _PyObject_GC_TRACK()
13 #include "structmember.h" // PyMemberDef
14 #include "pycore_structseq.h" // PyStructSequence_InitType()
15 #include "pycore_initconfig.h" // _PyStatus_OK()
16
17 static const char visible_length_key[] = "n_sequence_fields";
18 static const char real_length_key[] = "n_fields";
19 static const char unnamed_fields_key[] = "n_unnamed_fields";
20 static const char match_args_key[] = "__match_args__";
21
22 /* Fields with this name have only a field index, not a field name.
23 They are only allowed for indices < n_visible_fields. */
24 const char * const PyStructSequence_UnnamedField = "unnamed field";
25
26 static Py_ssize_t
27 get_type_attr_as_size(PyTypeObject *tp, PyObject *name)
28 {
29 PyObject *v = PyDict_GetItemWithError(_PyType_GetDict(tp), name);
30 if (v == NULL && !PyErr_Occurred()) {
31 PyErr_Format(PyExc_TypeError,
32 "Missed attribute '%U' of type %s",
33 name, tp->tp_name);
34 return -1;
35 }
36 return PyLong_AsSsize_t(v);
37 }
38
39 #define VISIBLE_SIZE(op) Py_SIZE(op)
40 #define VISIBLE_SIZE_TP(tp) \
41 get_type_attr_as_size(tp, &_Py_ID(n_sequence_fields))
42 #define REAL_SIZE_TP(tp) \
43 get_type_attr_as_size(tp, &_Py_ID(n_fields))
44 #define REAL_SIZE(op) REAL_SIZE_TP(Py_TYPE(op))
45
46 #define UNNAMED_FIELDS_TP(tp) \
47 get_type_attr_as_size(tp, &_Py_ID(n_unnamed_fields))
48 #define UNNAMED_FIELDS(op) UNNAMED_FIELDS_TP(Py_TYPE(op))
49
50
51 PyObject *
52 PyStructSequence_New(PyTypeObject *type)
53 {
54 PyStructSequence *obj;
55 Py_ssize_t size = REAL_SIZE_TP(type), i;
56 if (size < 0) {
57 return NULL;
58 }
59 Py_ssize_t vsize = VISIBLE_SIZE_TP(type);
60 if (vsize < 0) {
61 return NULL;
62 }
63
64 obj = PyObject_GC_NewVar(PyStructSequence, type, size);
65 if (obj == NULL)
66 return NULL;
67 /* Hack the size of the variable object, so invisible fields don't appear
68 to Python code. */
69 Py_SET_SIZE(obj, vsize);
70 for (i = 0; i < size; i++)
71 obj->ob_item[i] = NULL;
72
73 return (PyObject*)obj;
74 }
75
76 void
77 PyStructSequence_SetItem(PyObject* op, Py_ssize_t i, PyObject* v)
78 {
79 PyStructSequence_SET_ITEM(op, i, v);
80 }
81
82 PyObject*
83 PyStructSequence_GetItem(PyObject* op, Py_ssize_t i)
84 {
85 return PyStructSequence_GET_ITEM(op, i);
86 }
87
88
89 static int
90 structseq_traverse(PyStructSequence *obj, visitproc visit, void *arg)
91 {
92 if (Py_TYPE(obj)->tp_flags & Py_TPFLAGS_HEAPTYPE) {
93 Py_VISIT(Py_TYPE(obj));
94 }
95 Py_ssize_t i, size;
96 size = REAL_SIZE(obj);
97 for (i = 0; i < size; ++i) {
98 Py_VISIT(obj->ob_item[i]);
99 }
100 return 0;
101 }
102
103 static void
104 structseq_dealloc(PyStructSequence *obj)
105 {
106 Py_ssize_t i, size;
107 PyObject_GC_UnTrack(obj);
108
109 PyTypeObject *tp = Py_TYPE(obj);
110 size = REAL_SIZE(obj);
111 for (i = 0; i < size; ++i) {
112 Py_XDECREF(obj->ob_item[i]);
113 }
114 PyObject_GC_Del(obj);
115 if (_PyType_HasFeature(tp, Py_TPFLAGS_HEAPTYPE)) {
116 Py_DECREF(tp);
117 }
118 }
119
120 /*[clinic input]
121 class structseq "PyStructSequence *" "NULL"
122 [clinic start generated code]*/
123 /*[clinic end generated code: output=da39a3ee5e6b4b0d input=9d781c6922c77752]*/
124
125 #include "clinic/structseq.c.h"
126
127 /*[clinic input]
128 @classmethod
129 structseq.__new__ as structseq_new
130 sequence as arg: object
131 dict: object(c_default="NULL") = {}
132 [clinic start generated code]*/
133
134 static PyObject *
135 structseq_new_impl(PyTypeObject *type, PyObject *arg, PyObject *dict)
136 /*[clinic end generated code: output=baa082e788b171da input=90532511101aa3fb]*/
137 {
138 PyObject *ob;
139 PyStructSequence *res = NULL;
140 Py_ssize_t len, min_len, max_len, i, n_unnamed_fields;
141
142 min_len = VISIBLE_SIZE_TP(type);
143 if (min_len < 0) {
144 return NULL;
145 }
146 max_len = REAL_SIZE_TP(type);
147 if (max_len < 0) {
148 return NULL;
149 }
150 n_unnamed_fields = UNNAMED_FIELDS_TP(type);
151 if (n_unnamed_fields < 0) {
152 return NULL;
153 }
154
155 arg = PySequence_Fast(arg, "constructor requires a sequence");
156
157 if (!arg) {
158 return NULL;
159 }
160
161 if (dict && !PyDict_Check(dict)) {
162 PyErr_Format(PyExc_TypeError,
163 "%.500s() takes a dict as second arg, if any",
164 type->tp_name);
165 Py_DECREF(arg);
166 return NULL;
167 }
168
169 len = PySequence_Fast_GET_SIZE(arg);
170 if (min_len != max_len) {
171 if (len < min_len) {
172 PyErr_Format(PyExc_TypeError,
173 "%.500s() takes an at least %zd-sequence (%zd-sequence given)",
174 type->tp_name, min_len, len);
175 Py_DECREF(arg);
176 return NULL;
177 }
178
179 if (len > max_len) {
180 PyErr_Format(PyExc_TypeError,
181 "%.500s() takes an at most %zd-sequence (%zd-sequence given)",
182 type->tp_name, max_len, len);
183 Py_DECREF(arg);
184 return NULL;
185 }
186 }
187 else {
188 if (len != min_len) {
189 PyErr_Format(PyExc_TypeError,
190 "%.500s() takes a %zd-sequence (%zd-sequence given)",
191 type->tp_name, min_len, len);
192 Py_DECREF(arg);
193 return NULL;
194 }
195 }
196
197 res = (PyStructSequence*) PyStructSequence_New(type);
198 if (res == NULL) {
199 Py_DECREF(arg);
200 return NULL;
201 }
202 for (i = 0; i < len; ++i) {
203 PyObject *v = PySequence_Fast_GET_ITEM(arg, i);
204 res->ob_item[i] = Py_NewRef(v);
205 }
206 Py_DECREF(arg);
207 for (; i < max_len; ++i) {
208 if (dict == NULL) {
209 ob = Py_None;
210 }
211 else {
212 ob = _PyDict_GetItemStringWithError(dict,
213 type->tp_members[i-n_unnamed_fields].name);
214 if (ob == NULL) {
215 if (PyErr_Occurred()) {
216 Py_DECREF(res);
217 return NULL;
218 }
219 ob = Py_None;
220 }
221 }
222 res->ob_item[i] = Py_NewRef(ob);
223 }
224
225 _PyObject_GC_TRACK(res);
226 return (PyObject*) res;
227 }
228
229
230 static PyObject *
231 structseq_repr(PyStructSequence *obj)
232 {
233 PyTypeObject *typ = Py_TYPE(obj);
234 _PyUnicodeWriter writer;
235
236 /* Write "typename(" */
237 PyObject *type_name = PyUnicode_DecodeUTF8(typ->tp_name,
238 strlen(typ->tp_name),
239 NULL);
240 if (type_name == NULL) {
241 return NULL;
242 }
243
244 _PyUnicodeWriter_Init(&writer);
245 writer.overallocate = 1;
246 /* count 5 characters per item: "x=1, " */
247 writer.min_length = (PyUnicode_GET_LENGTH(type_name) + 1
248 + VISIBLE_SIZE(obj) * 5 + 1);
249
250 if (_PyUnicodeWriter_WriteStr(&writer, type_name) < 0) {
251 Py_DECREF(type_name);
252 goto error;
253 }
254 Py_DECREF(type_name);
255
256 if (_PyUnicodeWriter_WriteChar(&writer, '(') < 0) {
257 goto error;
258 }
259
260 for (Py_ssize_t i=0; i < VISIBLE_SIZE(obj); i++) {
261 if (i > 0) {
262 /* Write ", " */
263 if (_PyUnicodeWriter_WriteASCIIString(&writer, ", ", 2) < 0) {
264 goto error;
265 }
266 }
267
268 /* Write "name=repr" */
269 const char *name_utf8 = typ->tp_members[i].name;
270 if (name_utf8 == NULL) {
271 PyErr_Format(PyExc_SystemError, "In structseq_repr(), member %zd name is NULL"
272 " for type %.500s", i, typ->tp_name);
273 goto error;
274 }
275
276 PyObject *name = PyUnicode_DecodeUTF8(name_utf8, strlen(name_utf8), NULL);
277 if (name == NULL) {
278 goto error;
279 }
280 if (_PyUnicodeWriter_WriteStr(&writer, name) < 0) {
281 Py_DECREF(name);
282 goto error;
283 }
284 Py_DECREF(name);
285
286 if (_PyUnicodeWriter_WriteChar(&writer, '=') < 0) {
287 goto error;
288 }
289
290 PyObject *value = PyStructSequence_GET_ITEM(obj, i);
291 assert(value != NULL);
292 PyObject *repr = PyObject_Repr(value);
293 if (repr == NULL) {
294 goto error;
295 }
296 if (_PyUnicodeWriter_WriteStr(&writer, repr) < 0) {
297 Py_DECREF(repr);
298 goto error;
299 }
300 Py_DECREF(repr);
301 }
302
303 if (_PyUnicodeWriter_WriteChar(&writer, ')') < 0) {
304 goto error;
305 }
306
307 return _PyUnicodeWriter_Finish(&writer);
308
309 error:
310 _PyUnicodeWriter_Dealloc(&writer);
311 return NULL;
312 }
313
314
315 static PyObject *
316 structseq_reduce(PyStructSequence* self, PyObject *Py_UNUSED(ignored))
317 {
318 PyObject* tup = NULL;
319 PyObject* dict = NULL;
320 PyObject* result;
321 Py_ssize_t n_fields, n_visible_fields, n_unnamed_fields, i;
322
323 n_fields = REAL_SIZE(self);
324 if (n_fields < 0) {
325 return NULL;
326 }
327 n_visible_fields = VISIBLE_SIZE(self);
328 n_unnamed_fields = UNNAMED_FIELDS(self);
329 if (n_unnamed_fields < 0) {
330 return NULL;
331 }
332 tup = _PyTuple_FromArray(self->ob_item, n_visible_fields);
333 if (!tup)
334 goto error;
335
336 dict = PyDict_New();
337 if (!dict)
338 goto error;
339
340 for (i = n_visible_fields; i < n_fields; i++) {
341 const char *n = Py_TYPE(self)->tp_members[i-n_unnamed_fields].name;
342 if (PyDict_SetItemString(dict, n, self->ob_item[i]) < 0)
343 goto error;
344 }
345
346 result = Py_BuildValue("(O(OO))", Py_TYPE(self), tup, dict);
347
348 Py_DECREF(tup);
349 Py_DECREF(dict);
350
351 return result;
352
353 error:
354 Py_XDECREF(tup);
355 Py_XDECREF(dict);
356 return NULL;
357 }
358
359 static PyMethodDef structseq_methods[] = {
360 {"__reduce__", (PyCFunction)structseq_reduce, METH_NOARGS, NULL},
361 {NULL, NULL}
362 };
363
364 static Py_ssize_t
365 count_members(PyStructSequence_Desc *desc, Py_ssize_t *n_unnamed_members) {
366 Py_ssize_t i;
367
368 *n_unnamed_members = 0;
369 for (i = 0; desc->fields[i].name != NULL; ++i) {
370 if (desc->fields[i].name == PyStructSequence_UnnamedField) {
371 (*n_unnamed_members)++;
372 }
373 }
374 return i;
375 }
376
377 static int
378 initialize_structseq_dict(PyStructSequence_Desc *desc, PyObject* dict,
379 Py_ssize_t n_members, Py_ssize_t n_unnamed_members) {
380 PyObject *v;
381
382 #define SET_DICT_FROM_SIZE(key, value) \
383 do { \
384 v = PyLong_FromSsize_t(value); \
385 if (v == NULL) { \
386 return -1; \
387 } \
388 if (PyDict_SetItemString(dict, key, v) < 0) { \
389 Py_DECREF(v); \
390 return -1; \
391 } \
392 Py_DECREF(v); \
393 } while (0)
394
395 SET_DICT_FROM_SIZE(visible_length_key, desc->n_in_sequence);
396 SET_DICT_FROM_SIZE(real_length_key, n_members);
397 SET_DICT_FROM_SIZE(unnamed_fields_key, n_unnamed_members);
398
399 // Prepare and set __match_args__
400 Py_ssize_t i, k;
401 PyObject* keys = PyTuple_New(desc->n_in_sequence);
402 if (keys == NULL) {
403 return -1;
404 }
405
406 for (i = k = 0; i < desc->n_in_sequence; ++i) {
407 if (desc->fields[i].name == PyStructSequence_UnnamedField) {
408 continue;
409 }
410 PyObject* new_member = PyUnicode_FromString(desc->fields[i].name);
411 if (new_member == NULL) {
412 goto error;
413 }
414 PyTuple_SET_ITEM(keys, k, new_member);
415 k++;
416 }
417
418 if (_PyTuple_Resize(&keys, k) == -1) {
419 goto error;
420 }
421
422 if (PyDict_SetItemString(dict, match_args_key, keys) < 0) {
423 goto error;
424 }
425
426 Py_DECREF(keys);
427 return 0;
428
429 error:
430 Py_DECREF(keys);
431 return -1;
432 }
433
434 static PyMemberDef *
435 initialize_members(PyStructSequence_Desc *desc,
436 Py_ssize_t n_members, Py_ssize_t n_unnamed_members)
437 {
438 PyMemberDef *members;
439
440 members = PyMem_NEW(PyMemberDef, n_members - n_unnamed_members + 1);
441 if (members == NULL) {
442 PyErr_NoMemory();
443 return NULL;
444 }
445
446 Py_ssize_t i, k;
447 for (i = k = 0; i < n_members; ++i) {
448 if (desc->fields[i].name == PyStructSequence_UnnamedField) {
449 continue;
450 }
451
452 /* The names and docstrings in these MemberDefs are statically */
453 /* allocated so it is expected that they'll outlive the MemberDef */
454 members[k].name = desc->fields[i].name;
455 members[k].type = T_OBJECT;
456 members[k].offset = offsetof(PyStructSequence, ob_item)
457 + i * sizeof(PyObject*);
458 members[k].flags = READONLY;
459 members[k].doc = desc->fields[i].doc;
460 k++;
461 }
462 members[k].name = NULL;
463
464 return members;
465 }
466
467
468 static void
469 initialize_static_fields(PyTypeObject *type, PyStructSequence_Desc *desc,
470 PyMemberDef *tp_members, unsigned long tp_flags)
471 {
472 type->tp_name = desc->name;
473 type->tp_basicsize = sizeof(PyStructSequence) - sizeof(PyObject *);
474 type->tp_itemsize = sizeof(PyObject *);
475 type->tp_dealloc = (destructor)structseq_dealloc;
476 type->tp_repr = (reprfunc)structseq_repr;
477 type->tp_doc = desc->doc;
478 type->tp_base = &PyTuple_Type;
479 type->tp_methods = structseq_methods;
480 type->tp_new = structseq_new;
481 type->tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | tp_flags;
482 type->tp_traverse = (traverseproc) structseq_traverse;
483 type->tp_members = tp_members;
484 }
485
486 static int
487 initialize_static_type(PyTypeObject *type, PyStructSequence_Desc *desc,
488 Py_ssize_t n_members, Py_ssize_t n_unnamed_members) {
489 /* initialize_static_fields() should have been called already. */
490 if (PyType_Ready(type) < 0) {
491 return -1;
492 }
493 Py_INCREF(type);
494
495 if (initialize_structseq_dict(
496 desc, _PyType_GetDict(type), n_members, n_unnamed_members) < 0) {
497 Py_DECREF(type);
498 return -1;
499 }
500
501 return 0;
502 }
503
504 int
505 _PyStructSequence_InitBuiltinWithFlags(PyInterpreterState *interp,
506 PyTypeObject *type,
507 PyStructSequence_Desc *desc,
508 unsigned long tp_flags)
509 {
510 Py_ssize_t n_unnamed_members;
511 Py_ssize_t n_members = count_members(desc, &n_unnamed_members);
512 PyMemberDef *members = NULL;
513
514 if ((type->tp_flags & Py_TPFLAGS_READY) == 0) {
515 assert(type->tp_name == NULL);
516 assert(type->tp_members == NULL);
517 assert(type->tp_base == NULL);
518
519 members = initialize_members(desc, n_members, n_unnamed_members);
520 if (members == NULL) {
521 goto error;
522 }
523 initialize_static_fields(type, desc, members, tp_flags);
524
525 _Py_SetImmortal(type);
526 }
527 #ifndef NDEBUG
528 else {
529 // Ensure that the type was initialized.
530 assert(type->tp_name != NULL);
531 assert(type->tp_members != NULL);
532 assert(type->tp_base == &PyTuple_Type);
533 assert((type->tp_flags & _Py_TPFLAGS_STATIC_BUILTIN));
534 assert(_Py_IsImmortal(type));
535 }
536 #endif
537
538 if (_PyStaticType_InitBuiltin(interp, type) < 0) {
539 PyErr_Format(PyExc_RuntimeError,
540 "Can't initialize builtin type %s",
541 desc->name);
542 goto error;
543 }
544
545 if (initialize_structseq_dict(
546 desc, _PyType_GetDict(type), n_members, n_unnamed_members) < 0)
547 {
548 goto error;
549 }
550
551 return 0;
552
553 error:
554 if (members != NULL) {
555 PyMem_Free(members);
556 }
557 return -1;
558 }
559
560 int
561 PyStructSequence_InitType2(PyTypeObject *type, PyStructSequence_Desc *desc)
562 {
563 PyMemberDef *members;
564 Py_ssize_t n_members, n_unnamed_members;
565
566 #ifdef Py_TRACE_REFS
567 /* if the type object was chained, unchain it first
568 before overwriting its storage */
569 if (type->ob_base.ob_base._ob_next) {
570 _Py_ForgetReference((PyObject *)type);
571 }
572 #endif
573
574 /* PyTypeObject has already been initialized */
575 if (Py_REFCNT(type) != 0) {
576 PyErr_BadInternalCall();
577 return -1;
578 }
579
580 n_members = count_members(desc, &n_unnamed_members);
581 members = initialize_members(desc, n_members, n_unnamed_members);
582 if (members == NULL) {
583 return -1;
584 }
585 initialize_static_fields(type, desc, members, 0);
586 if (initialize_static_type(type, desc, n_members, n_unnamed_members) < 0) {
587 PyMem_Free(members);
588 return -1;
589 }
590 return 0;
591 }
592
593 void
594 PyStructSequence_InitType(PyTypeObject *type, PyStructSequence_Desc *desc)
595 {
596 (void)PyStructSequence_InitType2(type, desc);
597 }
598
599
600 /* This is exposed in the internal API, not the public API.
601 It is only called on builtin static types, which are all
602 initialized via _PyStructSequence_InitBuiltinWithFlags(). */
603
604 void
605 _PyStructSequence_FiniBuiltin(PyInterpreterState *interp, PyTypeObject *type)
606 {
607 // Ensure that the type is initialized
608 assert(type->tp_name != NULL);
609 assert(type->tp_base == &PyTuple_Type);
610 assert((type->tp_flags & _Py_TPFLAGS_STATIC_BUILTIN));
611 assert(_Py_IsImmortal(type));
612
613 // Cannot delete a type if it still has subclasses
614 if (_PyType_HasSubclasses(type)) {
615 // XXX Shouldn't this be an error?
616 return;
617 }
618
619 _PyStaticType_Dealloc(interp, type);
620
621 if (_Py_IsMainInterpreter(interp)) {
622 // Undo _PyStructSequence_InitBuiltinWithFlags().
623 type->tp_name = NULL;
624 PyMem_Free(type->tp_members);
625 type->tp_members = NULL;
626 type->tp_base = NULL;
627 }
628 }
629
630
631 PyTypeObject *
632 _PyStructSequence_NewType(PyStructSequence_Desc *desc, unsigned long tp_flags)
633 {
634 PyMemberDef *members;
635 PyTypeObject *type;
636 PyType_Slot slots[8];
637 PyType_Spec spec;
638 Py_ssize_t n_members, n_unnamed_members;
639
640 /* Initialize MemberDefs */
641 n_members = count_members(desc, &n_unnamed_members);
642 members = initialize_members(desc, n_members, n_unnamed_members);
643 if (members == NULL) {
644 return NULL;
645 }
646
647 /* Initialize Slots */
648 slots[0] = (PyType_Slot){Py_tp_dealloc, (destructor)structseq_dealloc};
649 slots[1] = (PyType_Slot){Py_tp_repr, (reprfunc)structseq_repr};
650 slots[2] = (PyType_Slot){Py_tp_doc, (void *)desc->doc};
651 slots[3] = (PyType_Slot){Py_tp_methods, structseq_methods};
652 slots[4] = (PyType_Slot){Py_tp_new, structseq_new};
653 slots[5] = (PyType_Slot){Py_tp_members, members};
654 slots[6] = (PyType_Slot){Py_tp_traverse, (traverseproc)structseq_traverse};
655 slots[7] = (PyType_Slot){0, 0};
656
657 /* Initialize Spec */
658 /* The name in this PyType_Spec is statically allocated so it is */
659 /* expected that it'll outlive the PyType_Spec */
660 spec.name = desc->name;
661 spec.basicsize = sizeof(PyStructSequence) - sizeof(PyObject *);
662 spec.itemsize = sizeof(PyObject *);
663 spec.flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | tp_flags;
664 spec.slots = slots;
665
666 type = (PyTypeObject *)PyType_FromSpecWithBases(&spec, (PyObject *)&PyTuple_Type);
667 PyMem_Free(members);
668 if (type == NULL) {
669 return NULL;
670 }
671
672 if (initialize_structseq_dict(
673 desc, _PyType_GetDict(type), n_members, n_unnamed_members) < 0) {
674 Py_DECREF(type);
675 return NULL;
676 }
677
678 return type;
679 }
680
681
682 PyTypeObject *
683 PyStructSequence_NewType(PyStructSequence_Desc *desc)
684 {
685 return _PyStructSequence_NewType(desc, 0);
686 }